# Greetings from The On-Line Encyclopedia of Integer Sequences! http://oeis.org/
Search: id:a001177
Showing 1-1 of 1
%I A001177 M2314 N0914 #210 Jan 23 2024 16:30:16
%S A001177 1,3,4,6,5,12,8,6,12,15,10,12,7,24,20,12,9,12,18,30,8,30,24,12,25,21,
%T A001177 36,24,14,60,30,24,20,9,40,12,19,18,28,30,20,24,44,30,60,24,16,12,56,
%U A001177 75,36,42,27,36,10,24,36,42,58,60,15,30,24,48,35,60,68,18,24,120
%N A001177 Fibonacci entry points: a(n) = least k >= 1 such that n divides Fibonacci number F_k (=A000045(k)).
%C A001177 In the formula, the relation a(p^e) = p^(e-1)*a(p) is called Wall's conjecture, which has been verified for primes up to 10^14. See A060305. Primes for which this relation fails are called Wall-Sun-Sun primes. - _T. D. Noe_, Mar 03 2009
%C A001177 All solutions to F_m == 0 (mod n) are given by m == 0 (mod a(n)). For a proof see, e.g., Vajda, p. 73. [Old comment changed by _Wolfdieter Lang_, Jan 19 2015]
%C A001177 If p is a prime of the form 10n +- 1 then a(p) is a divisor of p-1. If q is a prime of the form 10n +- 3 then a(q) is a divisor of q+1. - _Robert G. Wilson v_, Jul 07 2007
%C A001177 Definition 1 in Riasat (2011) calls this k(n), or sometimes just k. Corollary 1 in the same paper, "every positive integer divides infinitely many Fibonacci numbers," demonstrates that this sequence is infinite. - _Alonso del Arte_, Jul 27 2013
%C A001177 If p is a prime then a(p) <= p+1. This is because if p is a prime then exactly one of the following Fibonacci numbers is a multiple of p: F(p-1), F(p) or F(p+1). - _Dmitry Kamenetsky_, Jul 23 2015
%C A001177 From Renault 1996:
%C A001177 1. a(lcm(n,m)) = lcm(a(n), a(m)).
%C A001177 2. if n|m then a(n)|a(m).
%C A001177 3. if m has prime factorization m=p1^e1 * p2^e2 * ... * pn^en then a(m) = lcm(a(p1^e1), a(p2^e2), ..., a(pn^en)). - _Dmitry Kamenetsky_, Jul 23 2015
%C A001177 a(n)=n if and only if n=5^k or n=12*5^k for some k >= 0 (see Marques 2012). - _Dmitry Kamenetsky_, Aug 08 2015
%C A001177 Every positive integer (except 2) eventually appears in this sequence. This is because every Fibonacci number bigger than 1 (except Fibonacci(6)=8 and Fibonacci(12)=144) has at least one prime factor that is not a factor of any earlier Fibonacci number (see Knott reference). Let f(n) be such a prime factor for Fibonacci(n); then a(f(n))=n. - _Dmitry Kamenetsky_, Aug 08 2015
%C A001177 We can reconstruct the Fibonacci numbers from this sequence using the formula Fibonacci(n+2) = 1 + Sum_{i: a(i) <= n} phi(i)*floor(n/a(i)), where phi(n) is Euler's totient function A000010 (see the Stroinski link). For example F(6) = 1 + phi(1)*floor(4/a(1)) + phi(2)*floor(4/a(2)) + phi(3)*floor(4/a(4)) = 1 + 1*4 + 1*1 + 2*1 = 8. - _Peter Bala_, Sep 10 2015
%C A001177 Conjecture: Sum_{d|n} phi(d)*a(d) = A232656(n). - _Logan J. Kleinwaks_, Oct 28 2017
%C A001177 a(F_m) = m for all m > 1. Indeed, let (b(j)) be defined by b(1)=b(2)=1, and b(j+2) = (b(j) + b(j+1)) mod n. Then a(n) equals the index of the first occurrence of 0 in (b(j)). Example: if n=4 then b = A079343 = 1,1,2,3,1,0,1,1,..., so a(4)=6. If n is a Fibonacci number n=F_m, then obviously a(n)=m. Note that this gives a simple proof of the fact that all integers larger than 2 occur in (a(n)). - _Michel Dekking_, Nov 10 2017
%D A001177 A. Brousseau, Fibonacci and Related Number Theoretic Tables. Fibonacci Association, San Jose, CA, 1972, p. 25.
%D A001177 B. H. Hannon and W. L. Morris, Tables of Arithmetical Functions Related to the Fibonacci Numbers. Report ORNL-4261, Oak Ridge National Laboratory, Oak Ridge, Tennessee, June 1968.
%D A001177 Alfred S. Posamentier & Ingmar Lehmann, The (Fabulous) Fibonacci Numbers, Afterword by Herbert A. Hauptman, Nobel Laureate, 2. 'The Minor Modulus m(n)', Prometheus Books, NY, 2007, page 329-342.
%D A001177 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D A001177 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%D A001177 S. Vajda, Fibonacci and Lucas numbers and the Golden Section, Ellis Horwood Ltd., Chichester, 1989.
%D A001177 N. N. Vorob'ev, Fibonacci numbers, Blaisdell, NY, 1961.
%H A001177 T. D. Noe, Table of n, a(n) for n = 1..10000
%H A001177 A. Allard and P. Lecomte, Periods and entry points in Fibonacci sequence, Fib. Quart. 17 (1) (1979) 51-57.
%H A001177 R. C. Archibald (?), Review of B. H. Hannon and W. L. Morris, Tables of arithmetical functions related to the Fibonacci numbers, Math. Comp., 23 (1969), 459-460.
%H A001177 B. Avila and T. Khovanova, Free Fibonacci Sequences, arXiv preprint arXiv:1403.4614 [math.NT], 2014 and J. Int. Seq. 17 (2014) # 14.8.5.
%H A001177 Alfred Brousseau, Fibonacci and Related Number Theoretic Tables, Fibonacci Association, San Jose, CA, 1972. See p. 25.
%H A001177 J. D. Fulton and W. L. Morris, On arithmetical functions related to the Fibonacci numbers, Acta Arithmetica, 16 (1969), 105-110.
%H A001177 Molly FitzGibbons, Steven J. Miller, and Amanda Verga, Dynamics of the Fibonacci Order of Appearance Map, arXiv:2309.14501 [math.NT], 2023.
%H A001177 Ramon Glez-Regueral, An entry-point algorithm for high-speed factorization, Thirteenth Internat. Conf. Fibonacci Numbers Applications, Patras, Greece, 2008.
%H A001177 B. H. Hannon and W. L. Morris, Tables of Arithmetical Functions Related to the Fibonacci Numbers [Annotated and scanned copy]
%H A001177 Ron Knott, The first 300 Fibonacci numbers factorized
%H A001177 Paolo Leonetti and Carlo Sanna, On the greatest common divisor of n and the nth Fibonacci number, arXiv:1704.00151 [math.NT], 2017. See z(n).
%H A001177 Diego Marques, Fixed points of the order of appearance in the Fibonacci sequence, Fibonacci Quart. 50:4 (2012), pp. 346-352.
%H A001177 Diego Marques, The order of appearance of the product of consecutive Lucas numbers, Fibonacci Quarterly, 51 (2013), 38-43.
%H A001177 Diego Marques, Sharper upper bounds for the order of appearance in the fibonacci sequence, Fibonacci Quarterly, 51 (2013), pp. 233-238.
%H A001177 Zuzana Masáková and Edita Pelantová, Midy's Theorem in non-integer bases and divisibility of Fibonacci numbers, arXiv:2401.03874 [math.NT], 2024. See page 9.
%H A001177 Renault, The Fibonacci sequence under various moduli, Masters Thesis, Wake Forest University, 1996.
%H A001177 Samin Riasat, Z[phi] and the Fibonacci Sequence Modulo n, Mathematical Reflections 1 (2011): 1 - 7.
%H A001177 H. J. A. Salle, Maximum value for the rank of apparition of integers in recursive sequences, Fibonacci Quart. 13.2 (1975) 159-161.
%H A001177 U. Stroinski, Connection between Euler's totient function and Fibonacci numbers, Mathematics Stack Exchange, Feb 17 2015.
%H A001177 D. D. Wall, Fibonacci series modulo m, Am. Math. Monthly 67 (6) (1960) 525-532.
%H A001177 Eric Weisstein, MathWorld: Wall-Sun-Sun Prime
%F A001177 A001175(n) = A001176(n) * a(n) for n >= 1.
%F A001177 a(n) = n if and only if n is of form 5^k or 12*5^k (proved in Marques paper), a(n) = n - 1 if and only if n is in A106535, a(n) = n + 1 if and only if n is in A000057, a(n) = n + 5 if and only if n is in 5*A000057, ... - _Benoit Cloitre_, Feb 10 2007
%F A001177 a(1) = 1, a(2) = 3, a(4) = 6 and for e > 2, a(2^e) = 3*2^(e-2); a(5^e) = 5^e; and if p is an odd prime not 5, then a(p^e) = p^max(0, e-s)*a(p) where s = valuation(A000045(a(p)), p) (Wall's conjecture states that s = 1 for all p). If (m, n) = 1 then a(m*n) = lcm(a(m), a(n)). See Posamentier & Lahmann. - _Robert G. Wilson v_, Jul 07 2007; corrected by _Max Alekseyev_, Oct 19 2007, Jun 24 2011
%F A001177 Apparently a(n) = A213648(n) + 1 for n >= 2. - _Art DuPre_, Jul 01 2012
%F A001177 a(n) < n^2. [Vorob'ev]. - _Zak Seidov_, Jan 07 2016
%F A001177 a(n) < n^2 - 3n + 6. - _Jinyuan Wang_, Oct 13 2018
%F A001177 a(n) <= 2n [Salle]. - _Jon Maiga_, Apr 25 2019
%e A001177 a(4) = 6 because the smallest Fibonacci number that 4 divides is F(6) = 8.
%e A001177 a(5) = 5 because the smallest Fibonacci number that 5 divides is F(5) = 5.
%e A001177 a(6) = 12 because the smallest Fibonacci number that 6 divides is F(12) = 144.
%e A001177 From _Wolfdieter Lang_, Jan 19 2015: (Start)
%e A001177 a(2) = 3, hence 2 | F(m) iff m = 2*k, for k >= 0;
%e A001177 a(3) = 4, hence 3 | F(m) iff m = 4*k, for k >= 0;
%e A001177 etc. See a comment above with the Vajda reference.
%e A001177 (End)
%p A001177 A001177 := proc(n)
%p A001177 for k from 1 do
%p A001177 if combinat[fibonacci](k) mod n = 0 then
%p A001177 return k;
%p A001177 end if;
%p A001177 end do:
%p A001177 end proc: # _R. J. Mathar_, Jul 09 2012
%p A001177 N:= 1000: # to get a(1) to a(N)
%p A001177 L:= ilcm($1..N):
%p A001177 count:= 0:
%p A001177 for n from 1 while count < N do
%p A001177 fn:= igcd(L,combinat:-fibonacci(n));
%p A001177 divs:= select(`<=`,numtheory:-divisors(fn),N);
%p A001177 for d in divs do if not assigned(A[d]) then count:= count+1; A[d]:= n fi od:
%p A001177 od:
%p A001177 seq(A[n],n=1..N); # _Robert Israel_, Oct 14 2015
%t A001177 fibEntry[n_] := Block[{k = 1}, While[ Mod[ Fibonacci@k, n] != 0, k++ ]; k]; Array[fibEntry, 74] (* _Robert G. Wilson v_, Jul 04 2007 *)
%o A001177 (PARI) a(n)=if(n<0,0,s=1;while(fibonacci(s)%n>0,s++);s) \\ _Benoit Cloitre_, Feb 10 2007
%o A001177 (PARI) ap(p)=my(k=p+[0, -1, 1, 1, -1][p%5+1], f=factor(k)); for(i=1, #f[, 1], for(j=1, f[i, 2], if((Mod([1, 1; 1, 0], p)^(k/f[i, 1]))[1, 2], break); k/=f[i, 1])); k
%o A001177 a(n)=if(n==1,return(1)); my(f=factor(n), v); v=vector(#f~, i, if(f[i,1]>1e14,ap(f[i,1]^f[i,2]), ap(f[i,1])*f[i,1]^(f[i,2]-1))); if(f[1,1]==2&&f[1,2]>1, v[1]=3<