A253242 Least k>=0 such that n^(2^k)+1 is prime (for even n), or (n^(2^k)+1)/2 is prime (for odd n); -1 if no such k exists.

0, 0, 0, 0, 0, 2, -1, 0, 0, 1, 0, 0, 1, 1, 0, 2, 0, 1, 1, 0, 0, 2, 1, 0, 1, -1, 0, 1, 0

Offset: 2

Author

Eric Chen, Apr 19 2015

Keywords

• sign
• more
• hard

Comments

Least k such that the generalized Fermat number in base n (GFN(k,n)) is prime.

a(n) = -1 if n is in A070265 (perfect powers with an odd exponent).

a(n) is currently unknown for n = {31, 38, 50, 55, 62, 63, 67, 68, 77, 83, 86, 89, 91, 92, 97, 98, 99, 104, 107, 109, 122, 123, 127, 135, 137, ...}

Corresponding primes are {3, 2, 5, 3, 7, 1201, 0, 5, 11, 61, 13, 7, 197, 113, 17, 41761, 19, 181, 401, 11, 23, 139921, 577, 13, 677, 0, 29, 421, 31, ...}. (use 0 if a(n) = -1)

All 2 <= n <= 1500 and 0 <= k <= 14 are checked, the first occurrence of k (start with k = 0) in a(n) are {2, 11, 7, 43, 41, 75, 274, 234, 331, 1342, 824, ...}.

Examples

			a(7) = 2 since (7^(2^0)+1)/2 and (7^(2^1)+1)/2 are not primes, but (7^(2^2)+1)/2 = 1201 is prime.
a(14) = 1 since 14^(2^0)+1 is not prime, but 14^(2^1)+1 = 197 is prime.
		

Links

• Eric Chen, Table of n, a(n) for n = 2..1500 status (for the -1s, only a(n) for n in A070265 are proved, all other -1s are only conjectured)
• Gary Barnes, List of generalized Fermat primes in even bases up to 1030
• Eric Chen, List of generalized Fermat primes in bases up to 1000
• Chris Caldwell, Generalized Fermat number
• Richard Fischer, List of generalized Fermat primes in odd bases
• Yves Gallot, Generalized Fermat prime search
• Wilfrid Keller, Factorization of GFN(n,2)
• Wilfrid Keller, Factorization of GFN(n,3)
• Wilfrid Keller, Factorization of GFN(n,5)
• Wilfrid Keller, Factorization of GFN(n,6)
• Wilfrid Keller, Factorization of GFN(n,10)
• Wilfrid Keller, Factorization of GFN(n,12)
• Jeppe Stig Salling Nielsen, List of generalized Fermat primes in even bases up to 1000
• MathWorld, Generalized Fermat number
• OEIS wiki, Generalized Fermat number
• Wikipedia, Generalized Fermat number

Crossrefs

Cf. A079706, A228101, A084712, A123669, A058064, A057856, A130536, A080121, A077659, A122900.

Programs

Mathematica

Table[k=0; While[p=If[EvenQ[n], (2n)^(2^k)+1, ((2n)^(2^k)+1)/2]; k<12 && !PrimeQ[p], k=k+1]; If[k==12, -1, k], {n, 2, 1500}]

PARI

f(n) = for(k=0, 11, if(ispseudoprime(n^(2^k)+1), return(k))); -1
g(n) = for(k=0, 11, if(ispseudoprime((n^(2^k)+1)/2), return(k))); -1
a(n) = if(n%2==0, f(n), g(n))

PARI

f(n,k)=if(n%2, (n^(2^k)+1)/2, n^(2^k)+1)
a(n)=if(ispower(-n), -1, my(k); while(!ispseudoprime(f(n,k)), k++); k) \\ Charles R Greathouse IV, Apr 20 2015

Formula

a(2n) = A228101(n) = log_2(A079706(n)).

a(A006093(n)) = 0, a(A076274(n)) = 0, a(A070265(n)) = -1.