A001602 - OEIS

%I M2310 N0912 #160 Jan 05 2025 19:51:32

%S 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 50,104,36,27,19,128,130,69,46,37,50,79,164,168,87,178,90,190,97,99,

%U 22,42,224,228,114,13,238,120,250,129,88,67,270,139,28,284,147,44,310

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

%C "[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 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 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 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. - _Azuma Seiichi_, Jul 29 2014

%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.

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

%H 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 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 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 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 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 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 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 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 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 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 Patrick McKinley, <a href="/A001602/a001602.txt">Table of a(n) for n=1..678921</a>

%H 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 a(n) = A001177(prime(n)).

%F a(n) <= prime(n) + 1. - _Charles R Greathouse IV_, Jan 02 2013

%e The 5th prime is 11 and 11 first divides Fib(10)=55, so a(5) = 10.

%p A001602 := proc(n)

%p     local i,p;

%p     p := ithprime(n);

%p     for i from 1 do

%p         if modp(combinat[fibonacci](i),p) = 0 then

%p             return i;

%p         end if;

%p     end do:

%p end proc: # _R. J. Mathar_, Oct 31 2015

%t Table[k=1;While[!Divisible[Fibonacci[k],Prime[n]],k++];k,{n,70}] (* _Harvey P. Dale_, Feb 15 2012 *)

%t (* 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 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 (Haskell)

%o import Data.List (findIndex)

%o import Data.Maybe (fromJust)

%o a001602 n = (+ 1) $ fromJust $

%o             findIndex ((== 0) . (`mod` a000040 n)) $ tail a000045_list

%o -- _Reinhard Zumkeller_, Apr 08 2012

%o (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 (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 a(n)=do(prime(n))

%o apply(do, primes(100)) \\ _Charles R Greathouse IV_, Jan 03 2013

%o (Python)

%o from sympy.ntheory.generate import prime

%o def A001602(n):

%o     a, b, i, p = 0, 1, 1, prime(n)

%o     while b % p:

%o         a, b, i = b, (a+b) % p, i+1

%o     return i # _Chai Wah Wu_, Nov 03 2015, revised Apr 04 2016.

%Y Cf. A051694, A001177, A086597, A194363 (entries Lucas).

%K nonn,nice

%O 1,1

%A _N. J. A. Sloane_

%E More terms from _Jud McCranie_