cp's OEIS Frontend

A341211 Smallest prime p such that (p^(2^n) + 1)/2 is prime.

%I A341211 #37 Jul 08 2023 20:58:13
%S A341211 3,3,3,13,3,3,3,113,331,3631,827,3109,4253,7487,71
%N A341211 Smallest prime p such that (p^(2^n) + 1)/2 is prime.
%C A341211 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.
%C A341211 a(12) <= 4253, a(13) <= 7487, a(14) <= 71. - _Daniel Suteu_, Feb 07 2021
%C A341211 a(13) > 2500 and a(14) = 71. - _Jinyuan Wang_, Feb 07 2021
%H A341211 Dario Alpern, <a href="https://www.alpertron.com.ar/ECM.HTM">Integer factorization calculator</a>
%e A341211 No term is smaller than 3 (since 2 is the only smaller prime, and (2^(2^n) + 1)/2 is not an integer).
%e A341211 (3^(2^0) + 1)/2 = (3^1 + 1)/2 = (3 + 1)/2 = 4/2 = 2 is prime, so a(0)=3.
%e A341211 (3^(2^1) + 1)/2 = (3^2 + 1)/2 = 5 is prime, so a(1)=3.
%e A341211 (3^(2^2) + 1)/2 = (3^4 + 1)/2 = 41 is prime, so a(2)=3.
%e A341211 (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.
%o A341211 (PARI) a(n) = my(p=3); while (!isprime((p^(2^n) + 1)/2), p=nextprime(p+1)); p; \\ _Michel Marcus_, Feb 07 2021
%o A341211 (Alpertron) x=3;x=N(x);NOT IsPrime((x^8192+1)/2);N(x)
%o A341211 # _Martin Ehrenstein_, Feb 08 2021
%o A341211 (Python)
%o A341211 from sympy import isprime, nextprime
%o A341211 def a(n):
%o A341211   p, pow2 = 3, 2**n
%o A341211   while True:
%o A341211     if isprime((p**pow2 + 1)//2): return p
%o A341211     p = nextprime(p)
%o A341211 print([a(n) for n in range(9)]) # _Michael S. Branicky_, Mar 03 2021
%Y A341211 Cf. A005383, A048161, A176116, A340480.
%Y A341211 Cf. A093625 and A171381 (both for when p=3).
%K A341211 nonn,hard,more
%O A341211 0,1
%A A341211 _Jon E. Schoenfield_, Feb 06 2021
%E A341211 a(11) from _Daniel Suteu_, Feb 07 2021
%E A341211 a(12) from _Jinyuan Wang_, Feb 07 2021
%E A341211 a(13)-a(14), using Dario Alpern's integer factorization calculator and prior bounds, from _Martin Ehrenstein_, Feb 08 2021