A073936 -id:A073936 - cp's OEIS frontend

A092559 Numbers k such that 2^k + 1 is a semiprime.

3, 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

Zak Seidov, Feb 27 2004

nonn

Thanks to the recently found factor of F_14 (see A093179), we know that 16384 is not in the sequence. First unknown: 16768. - Don Reble, Mar 28 2010
The big prime factors for "5807" and all smaller entries have been proved prime; the rest (as far as I know) are probable primes. - Don Reble, Mar 28 2010
From Giuseppe Coppoletta, May 09 2017: (Start)
As 3 divides 2^a(n) + 1 for any odd a(n), all odd terms are prime and they are exactly the Wagstaff numbers (A000978) or also the prime Jacobsthal indices (A107036).
All terms from a(51) onwards refer to probabilistic primality tests for 2^a(n) + 1 (see Caldwell's link for the list of the largest certified Wagstaff primes).
For the close relationship between this sequence and the Fermat numbers, see comments in A073936. The only difference is that here a term can be the square of a prime p, and by the Mihăilescu Theorem (also known as Catalan's conjecture, see link) that implies p = a(n) = 3. So, excluding a(1) = 3, they must coincide.
As for A073936, after a(57), the values 267017, 269987, 374321, 986191, 4031399 and 4101572 are also terms, but there still remains the remote possibility of some gaps in between. In addition, 13347311 and 13372531 are also terms, but are possibly much further along in the numbering (see comments in A000978).
(End).
The powers of 2 in this sequence (that correspond to semiprime Fermat numbers) are k = 2^m with m = 5, 6, 7, 8, and no more below 20. - Amiram Eldar, Jun 18 2022

			11 is a term because 2^11 + 1 = 3 * 683.
3 is a term because 2^3 + 1 = 3^2.
10 is not a term because 2^10 + 1 = 5^2 * 41.

Giuseppe Coppoletta, Table of n, a(n) for n = 1..57
C. Caldwell's The Top Twenty Wagstaff primes.
S. S. Wagstaff, Jr., The Cunningham Project.
Eric W. Weisstein, MathWorld: Catalan's Conjecture.

Cf. A085724, A092558, A092561, A092562, A000978, A107036, A066263.

Cf. A073936. - R. J. Mathar, Sep 08 2008

Select[Range@ 200, PrimeOmega[2^# + 1] == 2 &] (* Michael De Vlieger, May 09 2017 *)

isok(n) = bigomega(2^n+1) == 2; \\ Michel Marcus, Oct 05 2013

More terms from Cunningham project, Mar 23 2004
More terms from Don Reble, Mar 28 2010
a(49)-a(52) from Giuseppe Coppoletta, May 08 2017

A066263 Numbers k such that 2^k + 1 has just two distinct prime factors.

Original entry on oeis.org

5, 6, 7, 9, 10, 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

Offset: 1

Benoit Cloitre, Dec 31 2001

nonn

From Giuseppe Coppoletta, May 16 2017: (Start)
All terms after a(52) 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(58), 267017, 269987, 374321, 986191, 4031399 and 4101572 are also terms, but there still remains the remote possibility of some gaps in between. In addition, 13347311 and 13372531 are also terms, but possibly much farther in the numbering (see comments in A000978).
For the relation with Fermat numbers and for the primality of odd terms, see comments in A073936. The terms 9 and 10 give a value of 2^n + 1 which is not squarefree, so they are not in A073936. For the rest, the actually known terms of the two sequences coincide. In order to verify if any other term could be found hereafter that is not in A073936, all we have to do is to examine the terms for which 2^n + 1 is not squarefree. Considering that 3 divides 2^a(n) + 1 for any odd term a(n) and using Zsigmondy's and Mihăilescu-Catalan's theorems (see links), one can verify that any nonsquarefree term greater than 9 has to be of the form a(n) = 2^j * Fj, where Fj is the Fermat prime 2^2^j + 1. So basically we have to see if ((Fj-1)^Fj + 1)/(Fj)^2 is a prime or the power of a prime for any Fermat prime Fj. The case j = 1 gives the term a(n) = 10 because (4^5 + 1)/5^2 = 41 is a prime, while for j = 2, (16^17 + 1)/17^2 = 354689 * 2879347902817 is composite. Similarly (256^257 + 1)/257^2 is neither a prime nor the power of a prime, so there is no contribution from the cases j = 2, 3 (see also comments in A127317).
For j = 4 and for any possible other Fermat prime which could be found later, the question is still open, in the sense that it is not actually known if n = 16 * F4 = 1048592 is a term or not. That seems very unlikely, but in order to decide that question for j = 4, one would have to check if (2^1048592 + 1)/65537^2 is a prime or the power of a prime. As this number has 315649 digits, I wonder if it is possible to handle it with the existing primality tests.
(End)

			3 and 4 are not terms because 2^3 + 1 and 2^4 + 1 have only a single prime factor (counted without multiplicity).
6 and 10 are terms because 2^6 + 1 = 5 * 13 and 2^10 + 1 = 5^2 * 41 have two distinct prime factors.

Giuseppe Coppoletta, Table of n, a(n) for n = 1..63
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.
Eric Weisstein's World of Mathematics, Catalan's Conjecture.
Eric Weisstein's World of Mathematics, Zsigmondy Theorem.

Cf. A073936, A107036, A000978, A057182, A127317, A283657, A283364, A092559, A046799.

f[n_] := First[ Transpose[ FactorInteger[2^n + 1]]]; Select[ Range[100], Length[f[ # ]] == 2 & ]
Select[Range[1300],PrimeNu[2^#+1]==2&] (* Harvey P. Dale, Nov 28 2014 *)

isok(k) = #factor(2^k+1)~ == 2; \\ Michel Marcus, Nov 14 2017

A001221(2^a(n) + 1) = 2.

Edited by Robert G. Wilson v, Jan 03 2002

a(40)-a(52) by Giuseppe Coppoletta, May 02 2017

A127317 Numbers n such that (256^n + 1)/257 is prime.

Original entry on oeis.org

5, 13, 23029

Offset: 1

Alexander Adamchuk, Mar 29 2007

All terms are primes. Largest currently known prime of the form (2^n + 1)/257 is (256^23029 + 1)/257 found by Donovan Johnson 03/2005. The only currently known prime of the form (2^n + 1)/65537 is (65536^239 + 1)/65537.
From Giuseppe Coppoletta, May 18 2017: (Start)
In general, for any j > 1, if (2^(n*2^j) + 1)/Fj is a prime (where Fj = 2^2^j + 1 is the corresponding Fermat number), then n needs to be prime, as for any odd proper factor q of n, 2^(q*2^j) + 1 is another factor of the numerator. The same for j = 0, apart for the particular value n = 3^2.
For the case j = 4, I checked it again, and (65536^p + 1)/65537 indeed is not a prime at least for 239 < p < 12500, i.e. (2^n + 1)/65537 is not a prime at least up to n = 200000. Any higher upper bound available?
One can also remark that 65536 = 2^16 and 239 = 2^8 - 2^4 - 1. Is there any special reason (see Brennen's link) for that?
I checked also that (2^(p*2^j) + 1)/Fj is never a proper power (in particular it is not a prime power) for j = 0..4 and for any prime p, at least for any exponent p*2^j < 200000.
We can even conjecture that ((Fj-1)^p + 1)/Fj is always squarefree for any odd prime p and for any Fermat number Fj with j >= 0. Note that this is not true if p is not restricted to be a prime, even if p and Fj are coprime, as shown by the following counterexample relative to the case j = 1, f1 = 5: 4^91 + 1 == 0 mod 1093^2. Remark that any such counterexample has to be a Wieferich prime (A001220), but not every Wieferich prime gives a counterexample, as shown by the second known Wieferich prime (3511), which cannot match here because it belongs to A072936.
(End)

Jack Brennen, Primes of the form (4^p+1)/5^t, Seqfan (Mar 15 2017).
H. Dubner and T. Granlund, Primes of the Form (b^n+1)/(b+1), J. Integer Sequences, 3 (2000), #P00.2.7.
H. Lifchitz, Mersenne and Fermat primes field.

Cf. A000978 = numbers n such that (2^n + 1)/3 is prime. Cf. A057182 = numbers n such that (16^n + 1)/17 is a prime.

Cf. A092559, A073936.

Do[n=8*Prime[k];f=2^n+1;If[PrimeQ[f/257],Print[{n,n/8}]],{k,1,2570}]

A278242 Least number with the prime signature of 2^n + 1.

Original entry on oeis.org

2, 2, 2, 4, 2, 6, 6, 6, 2, 24, 12, 6, 6, 6, 30, 60, 2, 6, 210, 6, 6, 60, 30, 6, 30, 210, 210, 240, 6, 30, 4620, 6, 6, 420, 210, 2310, 210, 30, 210, 60, 6, 30, 30030, 6, 30, 9240, 2310, 30, 30, 30, 9240, 4620, 30, 30, 30030, 4620, 30, 420, 30, 210, 210, 6, 2310, 9240, 6, 30030, 30030, 30, 60, 420, 60060, 30, 2310, 30, 2310, 60060, 210, 30030, 446185740, 6, 30

Offset: 0

Antti Karttunen, Nov 19 2016

nonn

Antti Karttunen, Table of n, a(n) for n = 0..257

Cf. A000051, A046523.
Cf. A073936 (positions of 6's), A092559 (positions of 4's and 6's).
Cf. also A278240.

Table[Times @@ MapIndexed[(Prime@ First@ #2)^#1 &, #] &@ If[Length@ # == 1 && #[[1, 1]] == 1, {0}, Reverse@ Sort@ #[[All, -1]]] &@ FactorInteger[ 2^n + 1], {n, 0, 80}] (* Michael De Vlieger, Nov 21 2016 *)

A046523(n) = my(f=vecsort(factor(n)[, 2], , 4), p); prod(i=1, #f, (p=nextprime(p+1))^f[i]) \\ from Charles R Greathouse IV, Aug 17 2011
A278242(n) = A046523((2^n)+1);
for(n=0, 257, write("b278242.txt", n, " ", A278242(n)));

(define (A278242 n) (A046523 (A000051 n)))

a(n) = A046523(A000051(n)).

A283657 Numbers m such that 2^m + 1 has at most 2 distinct prime factors.

Original entry on oeis.org

0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 16, 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

Offset: 1

Vladimir Shevelev, Mar 13 2017

nonn

Using comment in A283364, note that if a(n) is odd > 9, then it is prime.
503 <= a(41) <= 596. - Robert Israel, Mar 13 2017
Could (4^p + 1)/5^t be prime, where p is prime, 5^t is the highest power of 5 dividing 4^p + 1, other than for p=2, 3 and 5? - Vladimir Shevelev, Mar 14 2017
In his message to seqfans from Mar 15 2017, Jack Brennen beautifully proved that there are no more primes of such form. From his proof one can see also that there are no terms of the form 2*p > 10 in the sequence. - Vladimir Shevelev, Mar 15 2017
Where A046799(n)=2. - Robert G. Wilson v, Mar 15 2017
From Giuseppe Coppoletta, May 16 2017: (Start)
The only terms that are not in A066263 are those m giving 2^m + 1 = prime (i.e. m = 0 and any number m such that 2^m + 1 is a Fermat prime) and the values of m giving 2^m + 1 = power of a prime, giving m = 3 as the only possible case (by Mihăilescu-Catalan's result, see links).
For the relation with Fermat numbers and for other possible terms to check, see comments in A073936 and A066263.
All terms after a(59) 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(65), the values 267017, 269987, 374321, 986191, 4031399 and 4101572 are also terms, but there still remains the remote possibility of some gaps in between. In addition, 13347311 and 13372531 are also terms, but possibly much further along in the numbering (see comments in A000978).
(End).

			0 is a term as 2^0 + 1 = 2 is a prime.
10 is a term as 2^10 + 1 = 5^2 * 41.
14 is not a term as 2^14 + 1 = 5 * 29 * 113.

Giuseppe Coppoletta, Table of n, a(n) for n = 1..65
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.
Eric Weisstein's World of Mathematics, Catalan's Conjecture.
Eric Weisstein's World of Mathematics, Zsigmondy Theorem.

Cf. A002587, A046799, A283364, A073936, A000978, A127317, A092559, A019434, A066263.

Contains 4*A057182.

# this uses A002587[i] for i<=500, e.g., from the b-file for that sequence
count:= 0:
for i from 0 to 500 do
  m:= 0;
  r:= (2^i+1);
  if i::odd then
    m:= 1;
    r:= r/3^padic:-ordp(r,3);
  elif i > 2 then
    q:= max(numtheory:-factorset(i));
    if q > 2 then
      m:= 1;
      r:= r/B[i/q]^padic:-ordp(r,A002587[i/q]);
    fi
  fi;
  if r mod B[i] = 0 then m:= m+1;
      j:= padic:-ordp(r, A002587[i]);
      r:= r/B[i]^j;
  fi;
  mmax:= m;
  if isprime(r) then m:= m+1; mmax:= m
  elif r > 1 then mmax:= m+2
  fi;
  if mmax <= 2 or (m <= 1 and m + nops(numtheory:-factorset(r)) <= 2) then
       count:= count+1;
     A[count]:= i;
  fi
od:
seq(A[i],i=1..count); # Robert Israel, Mar 13 2017

Select[Range[0, 313], PrimeNu[2^# + 1]<3 &] (* Indranil Ghosh, Mar 13 2017 *)

for(n=0, 313, if(omega(2^n + 1)<3, print1(n,", "))) \\ Indranil Ghosh, Mar 13 2017

a(16)-a(38) from Peter J. C. Moses, Mar 13 2017
a(39)-a(40) from Robert Israel, Mar 13 2017
a(41)-a(65) from Giuseppe Coppoletta, May 08 2017

cp's OEIS Frontend

A092559 Numbers k such that 2^k + 1 is a semiprime.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A066263 Numbers k such that 2^k + 1 has just two distinct prime factors.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A127317 Numbers n such that (256^n + 1)/257 is prime.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

A278242 Least number with the prime signature of 2^n + 1.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Scheme

Formula

A283657 Numbers m such that 2^m + 1 has at most 2 distinct prime factors.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Extensions