A056993 a(n) is the smallest k >= 2 such that k^(2^n)+1 is prime, or -1 if no such k exists.

2, 2, 2, 2, 2, 30, 102, 120, 278, 46, 824, 150, 1534, 30406, 67234, 70906, 48594, 62722, 24518, 75898, 919444

Offset: 0

Author

Robert G. Wilson v, Sep 06 2000

Keywords

• hard
• more
• nonn

Comments

Smallest base value yielding generalized Fermat primes. - Hugo Pfoertner, Jul 01 2003

The first 5 terms correspond with the known (ordinary) Fermat primes. A probable candidate for the next entry is 62722^131072+1, discovered by Michael Angel in 2003. It has 628808 decimal digits. - Hugo Pfoertner, Jul 01 2003

For any n, a(n+1) >= sqrt(a(n)), because k^(2^(n+1))+1 = (k^2)^(2^n)+1. - Jeppe Stig Nielsen, Sep 16 2015

Does the sequence contain any perfect squares? If a(n) is a perfect square, then a(n+1) = sqrt(a(n)). - Jeppe Stig Nielsen, Sep 16 2015

If for a particular n, a(n) exists, then a(i) exist for all i=0,1,2,...,n. No proof is known that this sequence is infinite. Such a result would clearly imply the infinitude of A002496. - Jeppe Stig Nielsen, Sep 18 2015

919444 is a candidate for a(20). See Zimmermann link. - Serge Batalov, Sep 02 2017

Now PrimeGrid has tested and double checked all b^(2^20) + 1 with b < 919444, so we have proof that a(20) = 919444. - Jeppe Stig Nielsen, Dec 30 2017

Examples

			The primes are 2^(2^0) + 1 = 3, 2^(2^1) + 1 = 5, 2^(2^2) + 1 = 17, 2^(2^3) + 1 = 257, 2^(2^4) + 1 = 65537, 30^(2^5) + 1, 102^(2^6) + 1, ....
		

Links

• Yves Gallot, Generalized Fermat Prime Search
• Lucile and Yves Gallot, Generalized Fermat Prime Search
• Michael Goetz, id=103235 of Top 5000 Primes
• Luke Harmon, Gaetan Delavignette, Arnab Roy, and David Silva, PIE: p-adic Encoding for High-Precision Arithmetic in Homomorphic Encryption, Cryptology ePrint Archive 2023/700.
• Stephen Scott, id=84401 of Top 5000 Primes
• Sylvanus A. Zimmerman, PrimeGrid’s Generalized Fermat Prime Search

Crossrefs

Cf. A006093, A005574, A000068, A006314, A006313, A006315, A006316, A056994, A056995, A057465, A057002, A088361, A088362, A226528, A226529, A226530, A251597, A253854, A244150, A243959, A321323.

Cf. A019434 (Fermat primes).

Programs

Mathematica

f[n_] := (p = 2^n; k = 2; While[cp = k^p + 1; !PrimeQ@cp, k++ ]; k); Do[ Print[{n, f@n}], {n, 0, 17}] (* Lei Zhou, Feb 21 2005 *)

PARI

a(n)=my(k=2);while(!isprime(k^(2^n)+1),k++);k \\ Anders Hellström, Sep 16 2015

Formula

a(n) = A085398(2^(n+1)). - Jianing Song, Jun 13 2022

Extensions

1534 from Robert G. Wilson v, Oct 30 2000

62722 from Jeppe Stig Nielsen, Aug 07 2005

24518 and 75898 from Lei Zhou, Feb 01 2012

919444 from Jeppe Stig Nielsen, Dec 30 2017