login

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

n-th prime divides the n-th Fibonacci number.
5

%I #22 Dec 25 2014 03:58:01

%S 2160,3048,27094,251712,505768,936240,2182656,2582372,487568736,

%T 1261336587,1424530096

%N n-th prime divides the n-th Fibonacci number.

%C a(12) > 2*10^9. - _Giovanni Resta_, Jul 20 2013

%C Let r be a root of X^2 + 3*X + 1 in GF(prime(n)^2). Then n is in the sequence if and only if r^n = 1. - _Robert Israel_, Dec 24 2014

%p f:= proc(n)

%p local p, m, r, t, F;

%p p:= ithprime(n);

%p if member(p mod 5, {1,4}) then

%p m:= igcd(n,p-1);

%p r:= (numtheory:-msqrt(5,p)-3)/2 mod p;

%p r &^ m mod p = 1

%p else

%p F:= GF(p,2,t^2+3*t+1);

%p m:= igcd(n,p^2-1);

%p r:= F:-ConvertIn(t);

%p F:-ConvertOut(F:-`^`(r,m)) = 1

%p fi

%p end proc:

%p select(f, [$4 .. 10^5]); # _Robert Israel_, Dec 24 2014

%t (* Mathematica's Fibonacci function is not used so as to speed up the search. *) fibo = {1, 1}; divFiboNPrimes = {}; Do[len = Length[fibo]; n = fibo[[len]] + fibo[[len - 1]]; fibo = Append[fibo, n]; If[Mod[n, Prime[i]] == 0, divFiboNPrimes = Append[divFiboNPrimes, i]], {i, 3, 10^7}]; divFiboNPrimes

%o (PARI) v=0; w=1; for(n=2,m,f=v+w; if(f%prime(n)==0,print1(n,",")); v=w; w=f)

%Y Cf. A000040, A000045, A072123.

%K nonn

%O 1,1

%A _Joseph L. Pe_, Oct 02 2002

%E Three more terms from _Klaus Brockhaus_, Oct 04 2002

%E a(7,8) = 2182656, 2582372 from _Zak Seidov_, Nov 03 2009

%E a(9)-a(11) from _Giovanni Resta_, Jul 20 2013