login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A001602 Fibonacci entry points: a(n) = smallest m > 0 such that the n-th prime divides Fibonacci(m).
(Formerly M2310 N0912)
51
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 (list; graph; refs; listen; history; text; internal format)
OFFSET
1,1
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. - Azuma Seiichi, Jul 29 2014
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
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.
Daniel Yaqubi, Amirali Fatehizadeh, Some results on average of Fibonacci and Lucas sequences, arXiv:2001.11839 [math.CO], 2020.
FORMULA
a(n) = A001177(prime(n)).
a(n) <= prime(n) + 1. - Charles R Greathouse IV, Jan 02 2013
EXAMPLE
The 5th prime is 11 and 11 first divides Fib(10)=55, so a(5) = 10.
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 *)
PROG
(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
(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.
CROSSREFS
Cf. A051694, A001177, A086597, A194363 (entries Lucas).
Sequence in context: A066906 A125884 A346456 * A308197 A087012 A047366
KEYWORD
nonn,nice
AUTHOR
EXTENSIONS
More terms from Jud McCranie
STATUS
approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 28 12:59 EDT 2024. Contains 371254 sequences. (Running on oeis4.)