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

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, 50, 104, 36, 27, 19, 128, 130, 69, 46, 37, 50, 79, 164, 168, 87, 178, 90, 190, 97, 99, 22, 42, 224, 228, 114, 13, 238, 120, 250, 129, 88, 67, 270, 139, 28, 284, 147, 44, 310

Offset: 1

Author

N. J. A. Sloane

Keywords

• nonn
• nice

Comments

"[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

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

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]

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

Examples

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

References

• N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
• N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
• S. Vajda, Fibonacci and Lucas numbers and the Golden Section, Ellis Horwood Ltd., Chichester, 1989.

Links

• T. D. Noe, Table of n, a(n) for n = 1..10000
• U. Alfred, M. Wunderlich, Tables of Fibonacci Entry Points, Part I, (1965).
• Miho Aoki and Yuho Sakai, On Equivalence Classes of Generalized Fibonacci Sequences, JIS vol 19 (2016) # 16.2.6
• B. Avila, T. Khovanova, Free Fibonacci SequencesJ. Int. Seq. 17 (2014) # 14.8.5.
• Alfred Brousseau, Fibonacci and Related Number Theoretic Tables, Fibonacci Association, San Jose, CA, 1972. See p. 25.
• Paul Cubre and Jeremy Rouse, Divisibility properties of the Fibonacci entry point, arXiv:1212.6221 [math.NT], 2012.
• D. E. Daykin and L. A. G. Dresel, Factorization of Fibonacci Numbers part 2, Fibonacci Quarterly, vol 8 (1970), pages 23 - 30 and 82.
• Ramon Glez-Regueral, An entry-point algorithm for high-speed factorization, Thirteenth Internat. Conf. Fibonacci Numbers Applications, Patras, Greece, 2008.
• R. K. Guy, The Second Strong Law of Small Numbers, Math. Mag, 63 (1990), no. 1, 3-20. [Annotated scanned copy]
• Dov Jarden, Recurring Sequences, Riveon Lematematika, Jerusalem, 1966. [Annotated scanned copy, pp. 2-3 missing] See p. 7.
• D. Lind et al., Tables of Fibonacci entry points, part 2, reviewed in, Math. Comp., 20 (1966), 618-619.
• Patrick McKinley, Table of a(n) for n=1..678921
• Daniel Yaqubi, Amirali Fatehizadeh, Some results on average of Fibonacci and Lucas sequences, arXiv:2001.11839 [math.CO], 2020.

Crossrefs

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

Programs

Haskell

import Data.List (findIndex)
import Data.Maybe (fromJust)
a001602 n = (+ 1) $ fromJust $
            findIndex ((== 0) . (`mod` a000040 n)) $ tail a000045_list
-- Reinhard Zumkeller, Apr 08 2012

Maple

A001602 := proc(n)
    local i,p;
    p := ithprime(n);
    for i from 1 do
        if modp(combinat[fibonacci](i),p) = 0 then
            return i;
        end if;
    end do:
end proc: # R. J. Mathar, Oct 31 2015

Mathematica

Table[k=1;While[!Divisible[Fibonacci[k],Prime[n]],k++];k,{n,70}] (* Harvey P. Dale, Feb 15 2012 *)
(* 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 *)
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 *)

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

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
a(n)=do(prime(n))
apply(do, primes(100)) \\ Charles R Greathouse IV, Jan 03 2013

Python

from sympy.ntheory.generate import prime
def A001602(n):
    a, b, i, p = 0, 1, 1, prime(n)
    while b % p:
        a, b, i = b, (a+b) % p, i+1
    return i # Chai Wah Wu, Nov 03 2015, revised Apr 04 2016.

Formula

a(n) = A001177(prime(n)).

a(n) <= prime(n) + 1. - Charles R Greathouse IV, Jan 02 2013

Extensions

More terms from Jud McCranie