login
This site is supported by donations 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)
48
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

A. Brousseau, Fibonacci and Related Number Theoretic Tables. Fibonacci Association, San Jose, CA, 1972, p. 25.

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

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.

Dov Jarden, Recurring Sequences, Riveon Lematematika, Jerusalem, 1966. [Annotated scanned copy] 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

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.

Sequence in context: A050590 A066906 A125884 * A087012 A047366 A184776

Adjacent sequences:  A001599 A001600 A001601 * A001603 A001604 A001605

KEYWORD

nonn,nice

AUTHOR

N. J. A. Sloane

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 | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified March 25 01:30 EDT 2017. Contains 284036 sequences.