A001177 - OEIS

%I M2314 N0914 #210 Jan 23 2024 16:30:16

%S 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 36,24,14,60,30,24,20,9,40,12,19,18,28,30,20,24,44,30,60,24,16,12,56,

%U 75,36,42,27,36,10,24,36,42,58,60,15,30,24,48,35,60,68,18,24,120

%N Fibonacci entry points: a(n) = least k >= 1 such that n divides Fibonacci number F_k (=A000045(k)).

%C 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 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 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 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 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 From Renault 1996:

%C   1. a(lcm(n,m)) = lcm(a(n), a(m)).

%C   2. if n|m then a(n)|a(m).

%C   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 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 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 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 Conjecture: Sum_{d|n} phi(d)*a(d) = A232656(n). - _Logan J. Kleinwaks_, Oct 28 2017

%C 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 A. Brousseau, Fibonacci and Related Number Theoretic Tables. Fibonacci Association, San Jose, CA, 1972, p. 25.

%D 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 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 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%D S. Vajda, Fibonacci and Lucas numbers and the Golden Section, Ellis Horwood Ltd., Chichester, 1989.

%D N. N. Vorob'ev, Fibonacci numbers, Blaisdell, NY, 1961.

%H T. D. Noe, <a href="/A001177/b001177.txt">Table of n, a(n) for n = 1..10000</a>

%H A. Allard and P. Lecomte, <a href="http://www.fq.math.ca/Scanned/17-1/allard.pdf">Periods and entry points in Fibonacci sequence</a>, Fib. Quart. 17 (1) (1979) 51-57.

%H R. C. Archibald (?), Review of B. H. Hannon and W. L. Morris, <a href="http://www.jstor.org/stable/2004461">Tables of arithmetical functions related to the Fibonacci numbers</a>, Math. Comp., 23 (1969), 459-460.

%H B. Avila and T. Khovanova, <a href="http://arxiv.org/abs/1403.4614">Free Fibonacci Sequences</a>, arXiv preprint arXiv:1403.4614 [math.NT], 2014 and <a href="https://cs.uwaterloo.ca/journals/JIS/VOL17/Avila/avila4.html">J. Int. Seq. 17 (2014) # 14.8.5</a>.

%H Alfred Brousseau, <a href="http://www.fq.math.ca/fibonacci-tables.html">Fibonacci and Related Number Theoretic Tables</a>, Fibonacci Association, San Jose, CA, 1972. See p. 25.

%H J. D. Fulton and W. L. Morris, <a href="http://matwbn.icm.edu.pl/ksiazki/aa/aa16/aa1621.pdf">On arithmetical functions related to the Fibonacci numbers</a>, Acta Arithmetica, 16 (1969), 105-110.

%H Molly FitzGibbons, Steven J. Miller, and Amanda Verga, <a href="https://arxiv.org/abs/2309.14501">Dynamics of the Fibonacci Order of Appearance Map</a>, arXiv:2309.14501 [math.NT], 2023.

%H Ramon Glez-Regueral, <a href="http://www.mscs.dal.ca/fibonacci/abstracts.pdf">An entry-point algorithm for high-speed factorization</a>, Thirteenth Internat. Conf. Fibonacci Numbers Applications, Patras, Greece, 2008.

%H B. H. Hannon and W. L. Morris, <a href="/A001175/a001175.pdf">Tables of Arithmetical Functions Related to the Fibonacci Numbers</a> [Annotated and scanned copy]

%H Ron Knott, <a href="http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/fibtable.html">The first 300 Fibonacci numbers factorized</a>

%H Paolo Leonetti and Carlo Sanna, <a href="https://arxiv.org/abs/1704.00151">On the greatest common divisor of n and the nth Fibonacci number</a>, arXiv:1704.00151 [math.NT], 2017. See z(n).

%H Diego Marques, <a href="https://www.fq.math.ca/Papers1/50-4/MarquesFixedPoint.pdf">Fixed points of the order of appearance in the Fibonacci sequence</a>, Fibonacci Quart. 50:4 (2012), pp. 346-352.

%H Diego Marques, <a href="https://www.fq.math.ca/Papers1/51-1/MarquesOrderConsecLucas.pdf">The order of appearance of the product of consecutive Lucas numbers</a>, Fibonacci Quarterly, 51 (2013), 38-43.

%H Diego Marques, <a href="http://diego.mat.unb.br/doc/upperFQ.pdf">Sharper upper bounds for the order of appearance in the fibonacci sequence</a>, Fibonacci Quarterly, 51 (2013), pp. 233-238.

%H Zuzana Masáková and Edita Pelantová, <a href="https://arxiv.org/abs/2401.03874">Midy's Theorem in non-integer bases and divisibility of Fibonacci numbers</a>, arXiv:2401.03874 [math.NT], 2024. See page 9.

%H Renault, <a href="http://webspace.ship.edu/msrenault/fibonacci/fib.htm">The Fibonacci sequence under various moduli</a>, Masters Thesis, Wake Forest University, 1996.

%H Samin Riasat, <a href="https://www.awesomemath.org/wp-content/uploads/reflections/2011_1/fibonacci1.pdf">Z[phi] and the Fibonacci Sequence Modulo n</a>, Mathematical Reflections 1 (2011): 1 - 7.

%H H. J. A. Salle, <a href="https://www.fq.math.ca/Scanned/13-2/salle.pdf">Maximum value for the rank of apparition of integers in recursive sequences</a>, Fibonacci Quart. 13.2 (1975) 159-161.

%H U. Stroinski, <a href="http://math.stackexchange.com/questions/1151893/">Connection between Euler's totient function and Fibonacci numbers</a>, Mathematics Stack Exchange, Feb 17 2015.

%H D. D. Wall, <a href="http://www.jstor.org/stable/2309169">Fibonacci series modulo m</a>, Am. Math. Monthly 67 (6) (1960) 525-532.

%H Eric Weisstein, <a href="http://mathworld.wolfram.com/Wall-Sun-SunPrime.html">MathWorld: Wall-Sun-Sun Prime</a>

%F A001175(n) = A001176(n) * a(n) for n >= 1.

%F 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 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 Apparently a(n) = A213648(n) + 1 for n >= 2. - _Art DuPre_, Jul 01 2012

%F a(n) < n^2. [Vorob'ev]. - _Zak Seidov_, Jan 07 2016

%F a(n) < n^2 - 3n + 6. - _Jinyuan Wang_, Oct 13 2018

%F a(n) <= 2n [Salle]. - _Jon Maiga_, Apr 25 2019

%e a(4) = 6 because the smallest Fibonacci number that 4 divides is F(6) = 8.

%e a(5) = 5 because the smallest Fibonacci number that 5 divides is F(5) = 5.

%e a(6) = 12 because the smallest Fibonacci number that 6 divides is F(12) = 144.

%e From _Wolfdieter Lang_, Jan 19 2015: (Start)

%e a(2) = 3, hence 2 | F(m) iff m = 2*k, for k >= 0;

%e a(3) = 4, hence 3 | F(m) iff m = 4*k, for k >= 0;

%e etc. See a comment above with the Vajda reference.

%e (End)

%p A001177 := proc(n)

%p         for k from 1 do

%p                 if combinat[fibonacci](k) mod n = 0 then

%p                         return k;

%p                 end if;

%p         end do:

%p end proc: # _R. J. Mathar_, Jul 09 2012

%p N:= 1000: # to get a(1) to a(N)

%p L:= ilcm($1..N):

%p count:= 0:

%p for n from 1 while count < N do

%p   fn:= igcd(L,combinat:-fibonacci(n));

%p   divs:= select(`<=`,numtheory:-divisors(fn),N);

%p   for d in divs do if not assigned(A[d]) then count:= count+1; A[d]:= n fi od:

%p od:

%p seq(A[n],n=1..N); # _Robert Israel_, Oct 14 2015

%t fibEntry[n_] := Block[{k = 1}, While[ Mod[ Fibonacci@k, n] != 0, k++ ]; k]; Array[fibEntry, 74] (* _Robert G. Wilson v_, Jul 04 2007 *)

%o (PARI) a(n)=if(n<0,0,s=1;while(fibonacci(s)%n>0,s++);s) \\ _Benoit Cloitre_, Feb 10 2007

%o (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 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<<max(f[1,2]-2,1)); lcm(v) \\ _Charles R Greathouse IV_, May 08 2017

%o (Scheme) (define (A001177 n) (let loop ((k 1)) (cond ((zero? (modulo (A000045 k) n)) k) (else (loop (+ k 1)))))) ;; _Antti Karttunen_, Dec 21 2013

%o (Haskell)

%o a001177 n = head [k | k <- [1..], a000045 k `mod` n == 0]

%o -- _Reinhard Zumkeller_, Jan 15 2014

%Y Cf. A000045, A001175, A001176, A060383, A001602. First occurrence of k is given in A131401. A233281 gives such k that a(k) is a prime.

%Y From _Antti Karttunen_, Dec 21 2013: (Start)

%Y Various derived sequences:

%Y A047930(n) = A000045(a(n)).

%Y A037943(n) = A000045(a(n))/n.

%Y A217036(n) = A000045(a(n)-1) mod n.

%Y A132632(n) = a(n^2).

%Y A132633(n) = a(n^3).

%Y A214528(n) = a(n!).

%Y A215011(n) = a(A000217(n)).

%Y A215453(n) = a(n^n).

%Y Analogous sequence for the tribonacci numbers: A046737, for Lucas numbers: A223486, for Pell numbers: A214028.

%Y Cf. also A000057, A106535, A120255, A120256, A175026, A213648, A214031, A214781, A214783, A230359, A233283, A233285, A233287. (End)

%K nonn

%O 1,2

%A _N. J. A. Sloane_

%E Definition corrected by _Wolfdieter Lang_, Jan 19 2015