cp's OEIS Frontend

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

%I A073936 #66 Dec 23 2024 14:53:42
%S A073936 5,6,7,11,12,13,17,19,20,23,28,31,32,40,43,61,64,79,92,101,104,127,
%T A073936 128,148,167,191,199,256,313,347,356,596,692,701,1004,1228,1268,1709,
%U A073936 2617,3539,3824,5807,10501,10691,11279,12391,14479,42737,83339,95369,117239
%N A073936 Numbers k such that 2^k + 1 is the product of two distinct primes.
%C A073936 Original name: "2^n + 1 is squarefree and has exactly 2 prime factors."
%C A073936 From _Giuseppe Coppoletta_, May 08 2017: (Start)
%C A073936 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).
%C A073936 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.
%C A073936 So the even terms are all given by the following two class:
%C A073936 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.
%C A073936 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.
%C A073936 Exemplifying that, we have:
%C A073936 for j = 1 this gives only the even term a(2) = 2 * 3 = 6  (see Jack Brennen's result in ref),
%C A073936 for j = 2 we have all the terms of type 2^2 * A057182.
%C A073936 for j = 3 the even terms are of type 2^3 * A127317.
%C A073936 For j = 4 at least up to 200000, there is only the term a(41) = 2^4 * 239 = 3824 (see comment in A127317).
%C A073936 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).
%C A073936 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).
%C A073936 (End)
%C A073936 Intersection of A092559 and A066263. - _Eric Chen_, Jun 13 2018
%H A073936 Giuseppe Coppoletta, <a href="/A073936/b073936.txt">Table of n, a(n) for n = 1..56</a>
%H A073936 AMS Books Online, <a href="http://dx.doi.org/10.1090/conm/022">Factorizations of b^n = +-1, b=2,3,5,6,7,10,11,12 Up to High Powers, Third Edition</a>.
%H A073936 Arjen Bot, <a href="http://www.euronet.nl/users/bota/medium-p.htm">Factors for 2^n-1 and 2^n+1 for 1200 < n < 10000</a>.
%H A073936 Jack Brennen, <a href="https://web.archive.org/web/*/http://list.seqfan.eu/oldermail/seqfan/2017-March/017363.html">Primes of the form (4^p+1)/5^t, Seqfan (Mar 15 2017)</a>.
%H A073936 C. Caldwell's The Top Twenty <a href="https://t5k.org/top20/page.php?id=67">Wagstaff primes</a>.
%H A073936 Mersennewiki, <a href="http://mersennewiki.org/index.php/2_Plus_Tables">Factorizations Of Cunningham Numbers C+(2,n) (tables)</a>.
%H A073936 Samuel S. Wagstaff, <a href="http://www.cerias.purdue.edu/homes/ssw/cun/index.html">The Cunningham Project</a>.
%F A073936 Solutions to A000005[A000051(x)]=4 or A046798[x]=4
%e A073936 11 is a member because 1 + 2^11 = 2049 = 3 * 683.
%e A073936 9 is not a term because 1 + 2^9 = 513 = 3^3 * 19
%t A073936 Do[ If[ Length[ Divisors[1 + 2^n]] == 4, Print[n]], {n, 1, 200}]
%t A073936 (* Second program: *)
%t A073936 Select[Range@ 200, DivisorSigma[0, 2^# + 1] == 4 &] (* _Michael De Vlieger_, May 09 2017 *)
%o A073936 (Sage) [n for n in xsrange(3,200) if sigma(2^n+1,0)==4]
%o A073936 # Second program (faster):
%o A073936 (Sage) v=[]; N=2000
%o A073936 for n in xsrange(4,N):
%o A073936     j=valuation(n,2)
%o A073936     if j<5:
%o A073936         Fj=2^2^j+1; p=ZZ(n/2^j); q=ZZ((2^n+1)/Fj)
%o A073936         if p.is_prime() and q.is_prime(proof=false): v.append(n)
%o A073936     elif j<9 and n.is_power_of(2): v.append(n)
%o A073936 print(v) # _Giuseppe Coppoletta_, May 11 2017
%Y A073936 Cf. A000005, A000051, A046798, A092559, A000978. Different from A066263.
%K A073936 nonn
%O A073936 1,1
%A A073936 _Labos Elemer_, Aug 13 2002
%E A073936 Edited by _Robert G. Wilson v_, Aug 19 2002
%E A073936 a(28)-a(51) by _Giuseppe Coppoletta_, May 02 2017
%E A073936 Name reworded by _Jon E. Schoenfield_, Jun 15 2018