login

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

A341211
Smallest prime p such that (p^(2^n) + 1)/2 is prime.
4
3, 3, 3, 13, 3, 3, 3, 113, 331, 3631, 827, 3109, 4253, 7487, 71
OFFSET
0,1
COMMENTS
Expressions of the form m^j + 1 can be factored (e.g., m^3 + 1 = (m + 1)*(m^2 - m + 1)) for any positive integer j except when j is a power of 2, so (p^j + 1)/2 for prime p cannot be prime unless j is a power of 2.
a(12) <= 4253, a(13) <= 7487, a(14) <= 71. - Daniel Suteu, Feb 07 2021
a(13) > 2500 and a(14) = 71. - Jinyuan Wang, Feb 07 2021
EXAMPLE
No term is smaller than 3 (since 2 is the only smaller prime, and (2^(2^n) + 1)/2 is not an integer).
(3^(2^0) + 1)/2 = (3^1 + 1)/2 = (3 + 1)/2 = 4/2 = 2 is prime, so a(0)=3.
(3^(2^1) + 1)/2 = (3^2 + 1)/2 = 5 is prime, so a(1)=3.
(3^(2^2) + 1)/2 = (3^4 + 1)/2 = 41 is prime, so a(2)=3.
(3^(2^3) + 1)/2 = (3^8 + 1)/2 = 3281 = 17*193 is not prime, nor is (p^8 + 1)/2 for any other prime < 13, but (13^8 + 1)/2 = 407865361 is prime, so a(3)=13.
PROG
(PARI) a(n) = my(p=3); while (!isprime((p^(2^n) + 1)/2), p=nextprime(p+1)); p; \\ Michel Marcus, Feb 07 2021
(Alpertron) x=3; x=N(x); NOT IsPrime((x^8192+1)/2); N(x)
# Martin Ehrenstein, Feb 08 2021
(Python)
from sympy import isprime, nextprime
def a(n):
p, pow2 = 3, 2**n
while True:
if isprime((p**pow2 + 1)//2): return p
p = nextprime(p)
print([a(n) for n in range(9)]) # Michael S. Branicky, Mar 03 2021
CROSSREFS
Cf. A093625 and A171381 (both for when p=3).
Sequence in context: A291407 A378153 A147823 * A335518 A269347 A183554
KEYWORD
nonn,hard,more
AUTHOR
Jon E. Schoenfield, Feb 06 2021
EXTENSIONS
a(11) from Daniel Suteu, Feb 07 2021
a(12) from Jinyuan Wang, Feb 07 2021
a(13)-a(14), using Dario Alpern's integer factorization calculator and prior bounds, from Martin Ehrenstein, Feb 08 2021
STATUS
approved