A073936 Numbers k such that 2^k + 1 is the product of two distinct primes.

5, 6, 7, 11, 12, 13, 17, 19, 20, 23, 28, 31, 32, 40, 43, 61, 64, 79, 92, 101, 104, 127, 128, 148, 167, 191, 199, 256, 313, 347, 356, 596, 692, 701, 1004, 1228, 1268, 1709, 2617, 3539, 3824, 5807, 10501, 10691, 11279, 12391, 14479, 42737, 83339, 95369, 117239

Offset

1,1

Comments

Original name: "2^n + 1 is squarefree and has exactly 2 prime factors."

From Giuseppe Coppoletta, May 08 2017: (Start)

As 3 divides 2^a(n) + 1 for any odd term a(n), all odd terms are prime and exactly the Wagstaff primes (A000978), at the exclusion of 3 (which gives 2^3 + 1 = 3^2 not squarefree).

For the even terms, let a(n) = d * 2^j with d odd integer and j > 0. If d > 1, as (2^2^j)^q + 1 divides 2^a(n) + 1 for any odd prime q dividing d, then d must be prime.

So the even terms are all given by the following two class:

a) (d = 1) a(n) = 2^j such that Fj is a semiprime Fermat number. Up to now, only j = 5, 6, 7, 8 are known to give a Fermat semiprime, giving the even terms 32, 64, 128 and 256. We are also assured that 2^j is not a term for j = 9..19 because Fj is not a semiprime for those value of j (see Wagstaf's link). F20 is the first composite Fermat number which could give another even term (it would be 2^20 = 1048576). However, it seems highly unlikely that other Fermat semiprimes could exist.

b) (d = p odd prime) a(n) = p * 2^j with j such that Fj is a Fermat prime and p a prime verifying ((Fj - 1)^p + 1)/Fj is a prime.

Exemplifying that, we have:

for j = 1 this gives only the even term a(2) = 2 * 3 = 6 (see Jack Brennen's result in ref),

for j = 2 we have all the terms of type 2^2 * A057182.

for j = 3 the even terms are of type 2^3 * A127317.

For j = 4 at least up to 200000, there is only the term a(41) = 2^4 * 239 = 3824 (see comment in A127317).

All terms after a(50) refer to probabilistic primality tests for 2^a(n) + 1 (see Caldwell's link for the list of the largest certified Wagstaff primes).

After a(56), from the above, the primes 267017, 269987, 374321, 986191, 4031399 and the even value 4101572 are also terms, but still remains the (remote) possibility of some gaps in between. In addition, 13347311 and 13372531 are also terms, but possibly much further in the numbering (see comments in A000978).

(End)

Intersection of A092559 and A066263. - Eric Chen, Jun 13 2018

Links

Giuseppe Coppoletta, Table of n, a(n) for n = 1..56

AMS Books Online, Factorizations of b^n = +-1, b=2,3,5,6,7,10,11,12 Up to High Powers, Third Edition.

Arjen Bot, Factors for 2^n-1 and 2^n+1 for 1200 < n < 10000.

Jack Brennen, Primes of the form (4^p+1)/5^t, Seqfan (Mar 15 2017).

C. Caldwell's The Top Twenty Wagstaff primes.

Mersennewiki, Factorizations Of Cunningham Numbers C+(2,n) (tables).

Samuel S. Wagstaff, The Cunningham Project.

Formula

Solutions to A000005[A000051(x)]=4 or A046798[x]=4

Example

11 is a member because 1 + 2^11 = 2049 = 3 * 683.
9 is not a term because 1 + 2^9 = 513 = 3^3 * 19

Mathematica

Do[ If[ Length[ Divisors[1 + 2^n]] == 4, Print[n]], {n, 1, 200}]
(* Second program: *)
Select[Range@ 200, DivisorSigma[0, 2^# + 1] == 4 &] (* Michael De Vlieger, May 09 2017 *)

Prog

(Sage) [n for n in xsrange(3, 200) if sigma(2^n+1, 0)==4]
# Second program (faster):
(Sage) v=[]; N=2000
for n in xsrange(4, N):
    j=valuation(n, 2)
    if j<5:
        Fj=2^2^j+1; p=ZZ(n/2^j); q=ZZ((2^n+1)/Fj)
        if p.is_prime() and q.is_prime(proof=false): v.append(n)
    elif j<9 and n.is_power_of(2): v.append(n)
print(v) # Giuseppe Coppoletta, May 11 2017

Crossrefs

Cf. A000005, A000051, A046798, A092559, A000978. Different from A066263.

Sequence in context: A131503 A047266 A026309 * A184811 A230995 A362929

Adjacent sequences: A073933 A073934 A073935 * A073937 A073938 A073939

Keyword

nonn

Author

Labos Elemer, Aug 13 2002

Extensions

Edited by Robert G. Wilson v, Aug 19 2002

a(28)-a(51) by Giuseppe Coppoletta, May 02 2017

Name reworded by Jon E. Schoenfield, Jun 15 2018

Status

approved