OFFSET

1,4

COMMENTS

Primes p such that p * 2^m + 1 is composite for all m are called Sierpiński numbers. The smallest known prime Sierpiński number is 271129. Currently, 10223 is the smallest prime whose status is unknown.

With the discovery of the primality of 10223 * 2^31172165 + 1 on November 6, 2016, we now know that 10223 is not a Sierpiński number. The smallest prime of unknown status is thus now 21181. The smallest confirmed instance of a(n) = -1 is for n = 78557. - Alonso del Arte, Dec 16 2016 [Since we only care about prime Sierpiński numbers in this sequence, 78557 should be replaced by primepi(271129) = 23738. - Jianing Song, Dec 15 2021]

Aguirre conjectured that, for every n > 1, a(n) is even if and only if prime(n) mod 3 = 1 (see the MathStackExchange link below). - Lorenzo Sauras Altuzarra, Feb 12 2021

If prime(n) is not a Fermat prime, then a(n) is also the least m such that prime(n)*2^m is a totient number, or -1 if no such m exists. If prime(n) = 2^2^e + 1 is a Fermat prime, then the least m such that prime(n)*2^m is a totient number is min{2^e, a(n)} if a(n) != -1 or 2^e if a(n) = -1, since 2^2^e * (2^2^e + 1) = phi((2^2^e+1)^2) is a totient number. For example, the least m such that 257*2^m is a totient number is m = 8, rather than a(primepi(257)) = 279; the least m such that 65537*2^m is a totient number is m = 16, rather than a(primepi(65537)) = 287. - Jianing Song, Dec 15 2021

REFERENCES

See A046067.

LINKS

T. D. Noe, Table of n, a(n) for n = 1..1000

Ray Ballinger and Wilfrid Keller, Sierpiński Problem

Timothy Revell, "Crowdsourced prime number could help solve a 50-year-old problem", New Scientist, November 18, 2016.

Tejas R. Rao, Effective primality test for p*2^n+1, p prime, n>1, arXiv:1811.06070 [math.NT], 2018.

Seventeen or Bust, A Distributed Attack on the Sierpinski problem

EXAMPLE

a(8) = 6 because prime(8) = 19 and the first prime in the sequence 1 + 19 * {2, 4, 8,1 6, 32, 64} = {39, 77, 153, 305, 609, 1217} is 1217 = 1 + 19 * 2^6.

MAPLE

a := proc(n)

local m:

m := 0:

while not isprime(1+ithprime(n)*2^m) do m := m+1: od:

m:

end: # Lorenzo Sauras Altuzarra, Feb 12 2021

MATHEMATICA

Table[p = Prime[n]; k = 0; While[Not[PrimeQ[1 + p * 2^k]], k++]; k, {n, 100}] (* T. D. Noe *)

PROG

(PARI) a(n) = my(m=0, p=prime(n)); while (!isprime(1+p*2^m), m++); m; \\ Michel Marcus, Feb 12 2021

CROSSREFS

KEYWORD

sign

AUTHOR

Labos Elemer, Jan 10 2001

EXTENSIONS

Corrected by T. D. Noe, Aug 03 2005

STATUS

approved