login
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.
1

%I #139 Apr 03 2023 10:36:13

%S 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

%N 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.

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

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

%C 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, ...}

%C 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)

%C 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, ...}.

%H Eric Chen, <a href="/A253242/a253242_1.txt">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)</a>

%H Gary Barnes, <a href="http://www.noprimeleftbehind.net/crus/GFN-primes.htm">List of generalized Fermat primes in even bases up to 1030</a>

%H Eric Chen, <a href="/A253242/a253242.txt">List of generalized Fermat primes in bases up to 1000</a>

%H Chris Caldwell, <a href="https://t5k.org/glossary/page.php?sort=GeneralizedFermatNumber">Generalized Fermat number</a>

%H Richard Fischer, <a href="http://www.fermatquotient.com/PrimSerien/GenFermOdd.txt">List of generalized Fermat primes in odd bases</a>

%H Yves Gallot, <a href="http://pagesperso-orange.fr/yves.gallot/primes/index.html">Generalized Fermat prime search</a>

%H Wilfrid Keller, <a href="http://www.prothsearch.com/fermat.html">Factorization of GFN(n,2)</a>

%H Wilfrid Keller, <a href="http://www.prothsearch.com/GFN03.html">Factorization of GFN(n,3)</a>

%H Wilfrid Keller, <a href="http://www.prothsearch.com/GFN05.html">Factorization of GFN(n,5)</a>

%H Wilfrid Keller, <a href="http://www.prothsearch.com/GFN06.html">Factorization of GFN(n,6)</a>

%H Wilfrid Keller, <a href="http://www.prothsearch.com/GFN10.html">Factorization of GFN(n,10)</a>

%H Wilfrid Keller, <a href="http://www.prothsearch.com/GFN12.html">Factorization of GFN(n,12)</a>

%H Jeppe Stig Salling Nielsen, <a href="http://jeppesn.dk/generalized-fermat.html">List of generalized Fermat primes in even bases up to 1000</a>

%H MathWorld, <a href="http://mathworld.wolfram.com/GeneralizedFermatNumber.html">Generalized Fermat number</a>

%H OEIS wiki, <a href="https://oeis.org/wiki/Generalized_Fermat_numbers">Generalized Fermat number</a>

%H Wikipedia, <a href="http://en.wikipedia.org/wiki/Fermat_number#Generalized_Fermat_numbers">Generalized Fermat number</a>

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

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

%e 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.

%e a(14) = 1 since 14^(2^0)+1 is not prime, but 14^(2^1)+1 = 197 is prime.

%t 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}]

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

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

%o a(n) = if(n%2==0, f(n), g(n))

%o (PARI) f(n,k)=if(n%2, (n^(2^k)+1)/2, n^(2^k)+1)

%o a(n)=if(ispower(-n), -1, my(k); while(!ispseudoprime(f(n,k)), k++); k) \\ _Charles R Greathouse IV_, Apr 20 2015

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

%K sign,more,hard

%O 2,6

%A _Eric Chen_, Apr 19 2015