|
| |
|
|
A005109
|
|
Class 1- (or Pierpont) primes: primes of the form 2^t*3^u + 1.
(Formerly M0673)
|
|
56
|
|
|
|
2, 3, 5, 7, 13, 17, 19, 37, 73, 97, 109, 163, 193, 257, 433, 487, 577, 769, 1153, 1297, 1459, 2593, 2917, 3457, 3889, 10369, 12289, 17497, 18433, 39367, 52489, 65537, 139969, 147457, 209953, 331777, 472393, 629857, 746497, 786433, 839809, 995329, 1179649, 1492993, 1769473, 1990657
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,1
|
|
|
COMMENTS
|
The definition is given by Guy: a prime p is in class 1- if the only prime divisors of p - 1 are 2 or 3; and p is in class r- if every prime factor of p - 1 is in some class <= r- - 1, with equality for at least one prime factor. - N. J. A. Sloane, Sep 22 2012
See A005105 for the definition of class r+ primes.
Gleason, p. 191: a regular polygon of n sides can be constructed by ruler, compass and angle-trisector iff n = 2^r * 3^s * p_1 * p_2 * ... * p_k, where p_1, p_2, ..., p_k are distinct elements of this sequence and > 3.
Sequence gives primes solutions to p == +1 (mod phi(p-1)). - Benoit Cloitre, Feb 22 2002
These are the primes p for which p-1 is 3-smooth. Primes for which either p+1 or p-1 have many small factors are more easily proved prime, so most of the largest primes found have this property. - Michael B. Porter, Feb 19 2013
For terms p > 3, omega(p-1) = 3 - p mod 3. Consider terms > 3. Clearly, t > 0. If p == 1 mod 3, u > 0: hence omega(p-1) = 2 because p-1 has two prime factors. If p == 2 mod 3, u = 0: hence omega(p-1) = 1 because p-1 is a power of 2. The latter case corresponds to terms that are Fermat primes > 3. Similar arguments demonstrate the converse, that for p > 3, if omega(p-1) = 3 - p mod 3, p is a term. - Chris Boyd, Mar 22 2014
Named after the American mathematician James Pierpont (1866-1938). - Amiram Eldar, Jun 09 2021
|
|
|
REFERENCES
|
Richard K. Guy, Unsolved Problems in Number Theory, 3rd Edition, Springer, 2004, section A18, p. 66.
George E. Martin, Geometric Constructions, Springer, 1998. ISBN 0-387-98276-0.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
|
|
|
LINKS
|
Claudi Alsina and Roger B. Nelson, A Panoply of Polygons, Dolciani Math. Expeditions Vol. 58, AMS/MAA (2023), see page 112.
|
|
|
FORMULA
|
|
|
|
EXAMPLE
|
97 = 2^5*3 + 1 is a term.
|
|
|
MATHEMATICA
|
PrimeFactors[n_Integer] := Flatten[ Table[ #[[1]], {1}] & /@ FactorInteger[n]]; f[n_Integer] := Block[{m = n}, If[m == 0, m = 1, While[ IntegerQ[m/2], m /= 2]; While[ IntegerQ[m/3], m /= 3]]; Apply[Times, PrimeFactors[m] - 1]]; ClassMinusNbr[n_] := Length[NestWhileList[f, n, UnsameQ, All]] - 3; Prime[ Select[ Range[3, 6300], ClassMinusNbr[ Prime[ # ]] == 1 &]]
Select[Prime /@ Range[10^5], Max @@ First /@ FactorInteger[ # - 1] < 5 &] (* Ray Chandler, Nov 01 2005 *)
mx = 2*10^6; Select[Sort@ Flatten@ Table[2^i*3^j + 1, {i, 0, Log[2, mx]}, {j, 0, Log[3, mx/2^i]}], PrimeQ] (* Robert G. Wilson v, Jul 16 2014, edited by Michael De Vlieger, Aug 23 2017 *)
|
|
|
PROG
|
(PARI)
N=10^8; default(primelimit, N);
pq(p)={p-=1; (p/(2^valuation(p, 2)*3^valuation(p, 3)))==1; }
forprime(p=2, N, if(pq(p), print1(p, ", ")));
(PARI) /* much more efficient: */
A005109_upto(lim=1e10)={my(L=List(), k2=1);
until ( lim <= k2 *= 2, my(k23 = k2);
until ( lim <= k23 *= 3, isprime(k23+1) && listput(L, k23+1));
(Magma) [p: p in PrimesUpTo(10^8) | forall{d: d in PrimeDivisors(p-1) | d le 3}]; // Bruno Berselli, Sep 24 2012
(PARI)
N=10^8; default(primelimit, N);
print1("2, 3, "); forprime(p=5, N, if(omega(p-1)==3-p%3, print1(p", "))) \\ Chris Boyd, Mar 22 2014
(GAP)
K:=10^7;; # to get all terms <= K.
A:=Filtered([1..K], IsPrime);;
B:=List(A, i->Factors(i-1));;
C:=[];; for i in B do if Elements(i)=[2] or Elements(i)=[2, 3] then Add(C, Position(B, i)); fi; od;
(Python)
from itertools import islice
from sympy import nextprime
def A005109_gen(): # generator of terms
p = 2
while True:
q = p-1
q >>= (~q&q-1).bit_length()
a, b = divmod(q, 3)
while not b:
a, b = divmod(q:=a, 3)
if q==1:
yield p
p = nextprime(p)
|
|
|
CROSSREFS
|
Cf. A048135, A048136, A056637, A077497, A077498, A077500, A081426, A122259, A019434, A000668, A000040, A003586.
|
|
|
KEYWORD
|
nonn,nice,easy
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
Comments and additional references from Antreas P. Hatzipolakis (xpolakis(AT)otenet.gr)
|
|
|
STATUS
|
approved
|
| |
|
|
