A302990 - OEIS

%I #63 Aug 28 2023 19:50:07

%S 0,0,4,6,9,10,40,14,17,19,361,23,90,26,373,47,288,34,75,38,251,43,67,

%T 47,74,310,511,151534,57,20608,1146,62,197,94246,9974,287,271172,758

%N a(n) = index of first odd prime number in the (n-th)-order Fibonacci sequence Fn, or 0 if no such index exists.

%C Fn is defined by: Fn(0) = Fn(1) = ... = Fn(n-2) = 0, Fn(n-1) = 1, and Fn(k+1) = Fn(k) + Fn(k-1) + ... + Fn(k-n+1).

%C In general, Fn(k) is odd iff k == -1 or -2 (mod n+1), therefore a(n) = k*(n+1) - (1 or 2) for all n. Since Fn(n-1) = F(n) = 1, we must have a(n) >= 2n. Since Fn(k) = 2^(k-n) for n <= k < 2n, Fn(2n) = 2^n-1, so a(n) = 2n exactly for the Mersenne prime exponents A000043, while a(n) = 2n+1 when n is not in A000043 but n+1 is in A050414. - _M. F. Hasler_, Apr 18 2018

%C Further terms of the sequence: a(38) > 62000, a(39) > 72000, a(40) = 285, a(41) > 178000, a(42) = 558, a(44) = 19529, a(46) = 33369, a(47) = 239, a(48) = 6368, a(53) = 2860, a(54) = 2418, a(58) = 176, a(59) = 18418, a(60) = 1463, a(61) = 122, a(62) = 8755, a(63) = 5118,  a(64) = 25089, a(65) = 988, a(66) = 333, a(67) = 406, a(70) = 1632, a(74) = 374, a(76) = 13704, a(77) = 4991, a(86) = 347, a(89) = 178, a(92) = 1114, a(93) = 187, a(98) = 395, a(100) > 80000; a(n) > 10^4 for all other n up to 100. - _Jacques Tramu_ and _M. F. Hasler_, Apr 18 2018

%F a(n) == -1 or -2 (mod n+1). a(n) >= 2n, with equality iff n is in A000043. a(n) <= 2n+1 for n+1 in A050414. - _M. F. Hasler_, Apr 18 2018

%e a(2) = 4 because F2 (Fibonacci) = 0, 1, 1, 2, 3, 5, 8, ... and F2(4) = 3 is prime.

%e a(3) = 6 because F3 (tribonacci) = 0, 0, 1, 1, 2, 4, 7, 13, ... and F3(6) = 7 is prime.

%e a(4) = 9 because F4 (tetranacci) = 0, 0, 0, 1, 1, 2, 4, 8, 15, 29, 56, ...  and F4(9) = 29 is prime.

%e From _M. F. Hasler_, Apr 18 2018: (Start)

%e We see that Fn(k) = 2^(k-n) for n <= k < 2n and thus Fn(2n) = 2^n-1, so a(n) = 2n exactly for the Mersenne prime exponents A000043.

%e a(n) = 2n + 1 when 2^(n+1) - 3 is prime (n+1 in A050414) but 2^n-1 is not, i.e., n = 4, 8, 9, 11, 21, 23, 28, 93, 115, 121, 149, 173, 212, 220, 232, 265, 335, 451, 544, 688, 693, 849, 1735, ...

%e For other primes we have: a(29) = 687*30 - 2, a(37) = 20*38 - 2, a(41) > 10^4, a(43) > 10^4, a(47) = 5*48 - 1, a(53) = 53*54 - 2, a(59) = 307*60 - 2, a(67) = 6*67 - 1. (End)

%o (PARI) A302990(n,L=oo,a=vector(n+1,i,if(i<n,2^i,1)))={n>1 && for(i=-2+2*n+=1,L, ispseudoprime(a[i%n+1]=2*a[(i-1)%n+1]-a[i%n+1]) && return(i))} \\ Testing primality only for i%n>n-3 is not faster, even for large n. - _M. F. Hasler_, Apr 17 2018; improved Apr 18 2018

%Y Cf. A000045 (F2), A000073 (F3), A000078 (F4), A001591 (F5), A001592 (F6), A122189(F7), A079262 (F8), A104144 (F9), A122265 (F10).

%Y (According to the definition, F0 = A000004 and F1 = A000012.)

%Y Cf. A001605 (indices of prime numbers in F2).

%Y Cf. A000043, A050414.

%K nonn,more

%O 0,3

%A _Jacques Tramu_, Apr 17 2018

%E a(29) from _Jacques Tramu_, Apr 19 2018

%E a(33) from _Daniel Suteu_, Apr 20 2018

%E a(36) from _Jacques Tramu_, Apr 25 2018