cp's OEIS Frontend

A001602 Fibonacci entry points: a(n) = smallest m > 0 such that the n-th prime divides Fibonacci(m).

%I A001602 M2310 N0912 #163 Apr 21 2025 23:26:29
%S A001602 3,4,5,8,10,7,9,18,24,14,30,19,20,44,16,27,58,15,68,70,37,78,84,11,49,
%T A001602 50,104,36,27,19,128,130,69,46,37,50,79,164,168,87,178,90,190,97,99,
%U A001602 22,42,224,228,114,13,238,120,250,129,88,67,270,139,28,284,147,44,310
%N A001602 Fibonacci entry points: a(n) = smallest m > 0 such that the n-th prime divides Fibonacci(m).
%C A001602 "[a(n)] is called by Lucas the rank of apparition of p and we know it is a divisor of, or equal to prime(n)-1 or prime(n)+1" - Vajda, p. 84. (Note that a(3)=5. This is the only exception.) - _Chris K. Caldwell_, Nov 03 2008
%C A001602 Every number except 1, 2, 6 and 12 eventually occurs in this sequence. See also A086597(n), the number of primitive prime factors of Fibonacci(n). - _T. D. Noe_, Jun 13 2008
%C A001602 For each prime p we have an infinite sequence of integers, F(i*a(n))/p, i=1,2,... See also A236479. For primes p >= 3 and exponents j >= 2, with k = a(n) and p = p(n), it appears that F(k*i*p^(j-1))/p^j is an integer, for i >= 0. For p = 2, F(k*i*p^(j-1))/p^(j+1) = integer. - _Richard R. Forberg_, Jan 26-29 2014 [Comments revised by _N. J. A. Sloane_, Sep 24 2015]
%C A001602 Let p=prime(n). a(n) is also a divisor of (p-1)/2 (if p mod 5 == 1 or 4) or (p+1)/2 (if p mod 5 == 2 or 3) if and only if p mod 4 = 1. - _Seiichi Azuma_, Jul 29 2014
%D A001602 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D A001602 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%D A001602 S. Vajda, Fibonacci and Lucas numbers and the Golden Section, Ellis Horwood Ltd., Chichester, 1989.
%H A001602 T. D. Noe, <a href="/A001602/b001602.txt">Table of n, a(n) for n = 1..10000</a>
%H A001602 U. Alfred, M. Wunderlich, <a href="https://web.archive.org/web/2024*/https://www.fq.math.ca/entrypoints1.html">Tables of Fibonacci Entry Points, Part I</a>, (1965).
%H A001602 Miho Aoki and Yuho Sakai, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL19/Aoki/aoki4.html">On Equivalence Classes of Generalized Fibonacci Sequences</a>, JIS vol 19 (2016) # 16.2.6
%H A001602 B. Avila, T. Khovanova, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL17/Avila/avila4.html">Free Fibonacci Sequences</a>J. Int. Seq. 17 (2014) # 14.8.5.
%H A001602 Alfred Brousseau, <a href="https://web.archive.org/web/2024*/https://www.fq.math.ca/fibonacci-tables.html">Fibonacci and Related Number Theoretic Tables</a>, Fibonacci Association, San Jose, CA, 1972. See p. 25.
%H A001602 Paul Cubre and Jeremy Rouse, <a href="http://arxiv.org/abs/1212.6221">Divisibility properties of the Fibonacci entry point</a>, arXiv:1212.6221 [math.NT], 2012.
%H A001602 D. E. Daykin and L. A. G. Dresel, <a href="https://web.archive.org/web/2024*/https://www.fq.math.ca/Scanned/8-1/daykin-a.pdf">Factorization of Fibonacci Numbers</a> <a href="https://web.archive.org/web/2024*/https://www.fq.math.ca/Scanned/8-1/daykin-b.pdf">part 2</a>, Fibonacci Quarterly, vol 8 (1970), pages 23 - 30 and 82.
%H A001602 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 A001602 R. K. Guy, <a href="/A005347/a005347.pdf">The Second Strong Law of Small Numbers</a>, Math. Mag, 63 (1990), no. 1, 3-20. [Annotated scanned copy]
%H A001602 Dov Jarden, <a href="/A001602/a001602.pdf">Recurring Sequences</a>, Riveon Lematematika, Jerusalem, 1966. [Annotated scanned copy, pp. 2-3 missing] See p. 7.
%H A001602 D. Lind et al., Tables of Fibonacci entry points, part 2, <a href="http://dx.doi.org/10.1090/S0025-5718-66-99914-5">reviewed in</a>, Math. Comp., 20 (1966), 618-619.
%H A001602 Patrick McKinley, <a href="/A001602/a001602.txt">Table of a(n) for n=1..678921</a>
%H A001602 Daniel Yaqubi, Amirali Fatehizadeh, <a href="https://arxiv.org/abs/2001.11839">Some results on average of Fibonacci and Lucas sequences</a>, arXiv:2001.11839 [math.CO], 2020.
%F A001602 a(n) = A001177(prime(n)).
%F A001602 a(n) <= prime(n) + 1. - _Charles R Greathouse IV_, Jan 02 2013
%e A001602 The 5th prime is 11 and 11 first divides Fib(10)=55, so a(5) = 10.
%p A001602 A001602 := proc(n)
%p A001602     local i,p;
%p A001602     p := ithprime(n);
%p A001602     for i from 1 do
%p A001602         if modp(combinat[fibonacci](i),p) = 0 then
%p A001602             return i;
%p A001602         end if;
%p A001602     end do:
%p A001602 end proc: # _R. J. Mathar_, Oct 31 2015
%t A001602 Table[k=1;While[!Divisible[Fibonacci[k],Prime[n]],k++];k,{n,70}] (* _Harvey P. Dale_, Feb 15 2012 *)
%t A001602 (* a fast, but more complicated method *) MatrixPowerMod[mat_, n_, m_Integer] := Mod[Fold[Mod[If[#2 == 1, #1.#1.mat, #1.#1], m] &, mat, Rest[IntegerDigits[n, 2]]], m]; FibMatrix[n_Integer, m_Integer] := MatrixPowerMod[{{0, 1}, {1, 1}}, n, m]; FibEntryPointPrime[p_Integer] := Module[{n, d, k}, If[PrimeQ[p], n = p - JacobiSymbol[p, 5]; d = Divisors[n]; k = 1; While[FibMatrix[d[[k]], p][[1, 2]] > 0, k++]; d[[k]]]]; SetAttributes[FibEntryPointPrime, Listable]; FibEntryPointPrime[Prime[Range[10000]]] (* _T. D. Noe_, Jan 03 2013 *)
%t A001602 With[{nn=70,t=Table[{n,Fibonacci[n]},{n,500}]},Transpose[ Flatten[ Table[ Select[t,Divisible[#[[2]],Prime[i]]&,1],{i,nn}],1]][[1]]] (* _Harvey P. Dale_, May 31 2014 *)
%o A001602 (Haskell)
%o A001602 import Data.List (findIndex)
%o A001602 import Data.Maybe (fromJust)
%o A001602 a001602 n = (+ 1) $ fromJust $
%o A001602             findIndex ((== 0) . (`mod` a000040 n)) $ tail a000045_list
%o A001602 -- _Reinhard Zumkeller_, Apr 08 2012
%o A001602 (PARI) a(n)=if(n==3,5,my(p=prime(n));fordiv(p^2-1,d,if(fibonacci(d)%p==0, return(d)))) \\ _Charles R Greathouse IV_, Jul 17 2012
%o A001602 (PARI) do(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 A001602 a(n)=do(prime(n))
%o A001602 apply(do, primes(100)) \\ _Charles R Greathouse IV_, Jan 03 2013
%o A001602 (Python)
%o A001602 from sympy.ntheory.generate import prime
%o A001602 def A001602(n):
%o A001602     a, b, i, p = 0, 1, 1, prime(n)
%o A001602     while b % p:
%o A001602         a, b, i = b, (a+b) % p, i+1
%o A001602     return i # _Chai Wah Wu_, Nov 03 2015, revised Apr 04 2016.
%Y A001602 Cf. A051694, A001177, A086597, A194363 (entries Lucas).
%K A001602 nonn,nice
%O A001602 1,1
%A A001602 _N. J. A. Sloane_
%E A001602 More terms from _Jud McCranie_