cp's OEIS Frontend

A075702 Numbers k such that the k-th prime divides the k-th Fibonacci number.

%I A075702 #24 Mar 03 2025 21:39:40
%S A075702 2160,3048,27094,251712,505768,936240,2182656,2582372,487568736,
%T A075702 1261336587,1424530096
%N A075702 Numbers k such that the k-th prime divides the k-th Fibonacci number.
%C A075702 a(12) > 2*10^9. - _Giovanni Resta_, Jul 20 2013
%C A075702 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 A075702 f:= proc(n)
%p A075702   local p, m, r, t, F;
%p A075702   p:= ithprime(n);
%p A075702   if member(p mod 5, {1,4}) then
%p A075702   m:= igcd(n,p-1);
%p A075702     r:= (numtheory:-msqrt(5,p)-3)/2 mod p;
%p A075702     r &^ m mod p = 1
%p A075702   else
%p A075702     F:= GF(p,2,t^2+3*t+1);
%p A075702     m:= igcd(n,p^2-1);
%p A075702     r:= F:-ConvertIn(t);
%p A075702     F:-ConvertOut(F:-`^`(r,m)) = 1
%p A075702   fi
%p A075702 end proc:
%p A075702 select(f, [$4 .. 10^5]); # _Robert Israel_, Dec 24 2014
%t A075702 (* 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 A075702 (PARI) v=0; w=1; for(n=2,m,f=v+w; if(f%prime(n)==0,print1(n,",")); v=w; w=f)
%Y A075702 Cf. A000040, A000045, A072123.
%K A075702 nonn,more
%O A075702 1,1
%A A075702 _Joseph L. Pe_, Oct 02 2002
%E A075702 a(4)-a(6) from _Klaus Brockhaus_, Oct 04 2002
%E A075702 a(7)-a(8) from _Zak Seidov_, Nov 03 2009
%E A075702 a(9)-a(11) from _Giovanni Resta_, Jul 20 2013