A005108 -id:A005108 - cp's OEIS frontend

A005105 Class 1+ primes: primes of the form 2^i*3^j - 1 with i, j >= 0.

2, 3, 5, 7, 11, 17, 23, 31, 47, 53, 71, 107, 127, 191, 383, 431, 647, 863, 971, 1151, 2591, 4373, 6143, 6911, 8191, 8747, 13121, 15551, 23327, 27647, 62207, 73727, 131071, 139967, 165887, 294911, 314927, 442367, 472391, 497663, 524287, 786431, 995327

Offset: 1

N. J. A. Sloane, Simon Plouffe

nonn

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 A005109 for the definition of class r- primes.
Odd terms are primes satisfying 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 n>1, x=2*a(n) is a solution to the equation phi(sigma(x)) = x-phi(x). Also all Mersenne primes are in the sequence. - Jahangeer Kholdi, Sep 28 2014

			23 is in the sequence since 23 is prime and 23 + 1 = 24 = 2^3 * 3 has all prime factors less than or equal to 3.

R. K. Guy, Unsolved Problems in Number Theory, A18.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Ray Chandler, Table of n, a(n) for n = 1..7170 (terms < 10^1000; terms 1..691 from T. D. Noe, terms 692..5000 from Charles R Greathouse IV)
C. K. Caldwell, The Prime Pages.
G. Everest, P. Rogers and T. Ward, A higher-rank Mersenne problem, pp. 95-107 of ANTS 2002, Lect. Notes Computer Sci. 2369 (2002).
R. J. Mathar, Maple programs to generate b-files for b005105 to b005108, b081633 etc.
Index entries for sequences related to the Erdos-Selfridge classification

Cf. A069353, A069356, A005109, A005108, A019434, A000668, A000040, A003586, A129469.

A:=Filtered([1..10^7],IsPrime);;     I:=[3];;
B:=List(A,i->Elements(Factors(i+1)));;
C:=List([0..Length(I)],j->List(Combinations(I,j),i->Concatenation([2],i)));;
A005105:=Concatenation([2],List(Set(Flat(List([1..Length(C)],i->List([1..Length(C[i])],j->Positions(B,C[i][j]))))),i->A[i])); # Muniru A Asiru, Sep 28 2017

[p: p in PrimesUpTo(6*10^6) | forall{d: d in PrimeDivisors(p+1) | d le 3}]; // Bruno Berselli, Sep 24 2012

For Maple program see Mathar link.
# Alternative:
N:= 10^6: # to get all terms <= N
select(isprime,{seq(seq(2^i*3^j-1, i=0..ilog2(N/3^j)), j=0..floor(log[3](N)))});
# if using Maple 11 or earlier, uncomment the following line
# sort(convert(%,list));  # Robert Israel, Sep 28 2014

mx = 10^6; Select[ Sort@ Flatten@ Table[2^i*3^j - 1, {i, 0, Log[2, mx]}, {j, 0, Log[3, mx/2^i]}], PrimeQ] (* or *)
Prime[ Select[ Range[78200], Mod[ Prime[ # ] + 1, EulerPhi[ Prime[ # ] + 1]] == 0 &]] (* or *)
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]]; ClassPlusNbr[n_] := Length[ NestWhileList[f, n, UnsameQ, All]] - 3; Prime[ Select[ Range[3, 78200], ClassPlusNbr[ Prime[ # ]] == 1 &]]

list(lim)=my(v=List(), N); lim=1+lim\1; for(n=0, logint(lim,3), N=3^n; while(N<=lim, if(ispseudoprime(N-1),listput(v, N-1)); N<<=1)); Set(v) \\ Charles R Greathouse IV, Jul 15 2011; corrected Sep 22 2015

from itertools import count, islice
from sympy import integer_log, isprime
def A069353(n):
    def bisection(f,kmin=0,kmax=1):
        while f(kmax) > kmax: kmax <<= 1
        kmin = kmax >> 1
        while kmax-kmin > 1:
            kmid = kmax+kmin>>1
            if f(kmid) <= kmid:
                kmax = kmid
            else:
                kmin = kmid
        return kmax
    def f(x): return n+x-sum(((x+1)//3**i).bit_length() for i in range(integer_log(x+1,3)[0]+1))
    return bisection(f,n-1,n-1)
def A005105_gen(): # generator of terms
    return filter(lambda n:isprime(n), map(A069353,count(1)))
A005105_list = list(islice(A005105_gen(),30)) # Chai Wah Wu, Mar 31 2025

{primes p : A126433(PrimePi(p)) = 1 }. - R. J. Mathar, Sep 24 2012

More terms from Benoit Cloitre, Feb 22 2002

Edited and extended by Robert G. Wilson v, Mar 20 2003

A005113 Smallest prime in class n (sometimes written n+) according to the Erdős-Selfridge classification of primes.

Original entry on oeis.org

2, 13, 37, 73, 1021, 2917, 15013, 49681, 532801, 1065601, 8524807, 68198461, 545587687, 1704961513, 23869461181, 288310406533

Offset: 1

N. J. A. Sloane

A prime p is in class 1 if (p+1)'s largest prime factor is 2 or 3. If (p+1) has other prime factors, p's class is one more than the largest class of its prime factors. See also A005105.
John W. Layman observes that for n=10..13, the ratios r(n)= a(n)/a(n-1) are increasingly close to an integer, being 1.9999981, 7.99999906, 8.00000059 and 7.999999985.
Layman's observation is a consequence of a(n+1) = m*a(n)-1 for (n,m)=(1,7),(3,2),(4,14),(9,2),(10,8),(12,8),(14,14), while a(12) = 8 a(11)+5 is a coincidence which does not fit into that scheme. This relationship is not unusual since any N+ prime p is by definition such that p+1 = m*q where q is a (N-1)+ prime and m = (p+1)/q must be even since p,q are odd (except for q=2, allowing the odd m=7 for n=1 above) and the least N+ prime has good chances of having q equal to the least (N-1)+ prime. - M. F. Hasler, Apr 09 2007
a(n+1) >= 2*a(n)-1 since a(n+1)+1 = p*q with p of class n+ (thus >= a(n) and odd) and thus q >= 2 (even and positive). a(n+1) <= min { p = 2*k*a(n)-1 | k=1,2,3,... such that p is prime }. - M. F. Hasler, Apr 02 2007
a(17) <= 1833174628057, with equality if 916587314029 is the 10th 16+ prime; a(18) <= 3666349256113, with equality if a(17) = 1833174628057; a(19) <= 65994286610033, with equality if 41431295033731 is the third 18+ prime; a(20) <= 764276710625653, with equality if 382138355312827 is the third 19+ prime. - M. F. Hasler, Apr 09 2007

			1553 is in class 4 because 1553+1 = 2*3*7*37; 7 is in class 1 and 37 is in class 3. 37 is in class 3 because 37+1 = 2*19 and 19 is in class 2. 19 is in class 2 because 19+1 = 2*2*5 and 5 is in class 1. 5 is in class 1 because 5+1=2*3.

R. K. Guy, Unsolved Problems in Number Theory, A18.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Cf. A056637, A005105, A005106, A005107, A005108, A019268.

Cf. A081633 - A081639, A084071, A090468, A129474, A129475, A129469.

PrimeFactors[n_Integer] := Flatten[ Table[ #[[1]], {1}] & /@ FactorInteger[n]]; NextPrime[n_] := Block[{k = n + 1}, While[ !PrimeQ[k], k++ ]; k]; 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]]; ClassPlusNbr[n_] := Length[ NestWhileList[f, n, UnsameQ, All]] - 3; a = Table[0, {15}]; a[[1]] = 2; k = 5; Do[c = ClassPlusNbr[ k]; If[ a[[c]] == 0, a[[c]] = k]; k = NextPrime[k], {n, 1, 28700000}]; a

checkclass(n,p)={ n=factor(n+1)[,1]; n[#n] <= 3 && return(1); (#p <= 1 || n[#n] < p[#p]) && return(2); n[1]=p[#p]; p=vecextract(p,"^-1"); forstep( i=#n,2,-1, n[i] < n[1] && break; checkclass(n[i],p) > #p && return(2+#p)) }
A005113(n,p,a=[])={ while( #a #a, p=nextprime(p+1)); a=concat(a,p); p=a[#a]*2-2); a } \\ A005113(11) takes < 10 sec @ 2 GHz in 2007; less than 2.5 sec @ 2 GHz in 2013. \\ M. F. Hasler, Apr 02 2007

class(n, s=+1 /* for n+ class; -1 for n- class */)={ isprime(n) || return; (( n=factor(n+s)[,1] ) && n[ #n]>3 ) || return(1); vecsort( vector( #n,i,class( n[i],s )))[#n]+1 }
someofnextclass( a, limit=0, s=0, b=[], p)={ if(!s,/* guess + or - */ s=( class(a[1]) && class(a[1])==class(a[2]) )*2-1 ); print("looking for primes of class ", 1+class( a[1], s), ["+","-"][1+(s<0)] ); for( i=1,#a, p=-s; until( p>=limit, until( isprime(p), p+=a[i]<<1 ); b=concat(b,p); if( !limit, limit=p)) ); vecsort(b) };
c=A090468; for(i=15,20,c=someofnextclass(c,9e12);print("least prime of class ",i,"+ is <= ",c[1])) \\  M. F. Hasler, Apr 09 2007

Extended through a(12) by Robert G. Wilson v
a(13) from John W. Layman
a(14) from Don Reble, Apr 11 2003
a(15) from Sam Handler (sam_5_5_5_0(AT)yahoo.com), Aug 17 2006
a(7) corrected by Tomás Oliveira e Silva, Oct 27 2006
a(16) calculated using A129475(n) up to n=19 by M. F. Hasler, Apr 16 2007
Edited by Max Alekseyev, Aug 17 2013

A005107 Class 3+ primes (for definition see A005105).

Original entry on oeis.org

37, 103, 113, 151, 157, 163, 173, 181, 193, 227, 233, 257, 277, 311, 331, 337, 347, 353, 379, 389, 397, 401, 409, 421, 457, 463, 467, 487, 491, 521, 523, 541, 547, 569, 571, 601, 607, 613, 631, 653, 683, 701, 727, 733, 773, 787, 797, 811, 821, 829, 853, 857

Offset: 1

N. J. A. Sloane, Simon Plouffe

nonn

R. K. Guy, Unsolved Problems in Number Theory, A18.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

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

Cf. A005113, A005105, A005106, A005108.

For Maple program see Mathar link in A005105.

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]]; ClassPlusNbr[n_] := Length[ NestWhileList[f, n, UnsameQ, All]] - 3; Prime[ Select[ Range[150], ClassPlusNbr[ Prime[ # ]] == 3 &]]

Edited and extended by Robert G. Wilson v, Mar 20 2003

A081633 Class 5+ primes (for definition see A005105).

Original entry on oeis.org

1021, 1321, 1381, 1459, 1877, 2467, 2503, 2657, 2707, 3253, 3313, 3547, 3701, 3733, 3907, 4561, 4817, 4937, 5441, 5443, 5527, 5693, 5839, 5861, 6037, 6131, 6211, 6217, 6277, 6361, 6373, 6569, 6653, 7057, 7243, 7591, 7753, 7817, 7883, 8101, 8123, 8221

Offset: 1

Robert G. Wilson v, Mar 20 2003

nonn

R. K. Guy, Unsolved Problems in Number Theory, A18.

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

Cf. A005113, A005105, A005106, A005107, A005108, A081634, A081635, A081636, A081637, A081638, A081639.

For Maple program see Mathar link in A005105.

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]]; ClassPlusNbr[n_] := Length[ NestWhileList[f, n, UnsameQ, All]] - 3; Prime[ Select[ Range[1040], ClassPlusNbr[ Prime[ # ]] == 5 &]]

A005106 Class 2+ primes (for definition see A005105).

Original entry on oeis.org

13, 19, 29, 41, 43, 59, 61, 67, 79, 83, 89, 97, 101, 109, 131, 137, 139, 149, 167, 179, 197, 199, 211, 223, 229, 239, 241, 251, 263, 269, 271, 281, 283, 293, 307, 317, 349, 359, 367, 373, 419, 433, 439, 449, 461, 479, 499, 503, 509, 557, 563, 577, 587, 593

Offset: 1

N. J. A. Sloane, Simon Plouffe

nonn

R. K. Guy, Unsolved Problems in Number Theory, A18.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

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

Cf. A005113, A005105, A005107, A005108.

For Maple program see Mathar link in A005105.

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]]; ClassPlusNbr[n_] := Length[ NestWhileList[f, n, UnsameQ, All]] - 3; Prime[ Select[ Range[120], ClassPlusNbr[ Prime[ # ]] == 2 &]]

{prime(n): A126433(n) = 2}. - R. J. Mathar, Mar 26 2024

Edited and extended by Robert G. Wilson v, Mar 20 2003

A081639 Class 11+ primes.

Original entry on oeis.org

8524807, 18381361, 18575041, 19180817, 21312019, 31984321, 34099231, 40357021, 44206633, 44839273, 48499459, 51148847, 51444961, 51884467, 54144121, 57129613, 57780487, 58293601, 61378571, 65578901, 66786721, 66787873

Offset: 1

Robert G. Wilson v, Mar 20 2003

nonn

R. K. Guy, Unsolved Problems in Number Theory, A18.

R. J. Mathar, Table of n, a(n) for n = 1..108

Cf. A005113, A005105 - A005108, A081633 - A081638, A084071, A090468.

For Maple program see Mathar link in A005105.

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]]; ClassPlusNbr[n_] := Length[ NestWhileList[f, n, UnsameQ, All]] - 3; Prime[ Select[ Range[150000], ClassPlusNbr[ Prime[ # ]] == 11 &]]

A081635 Class 7+ primes.

Original entry on oeis.org

15013, 16333, 22093, 24841, 43321, 49003, 52517, 54721, 62533, 63761, 69061, 69073, 70061, 74597, 75781, 75793, 75913, 82561, 83233, 84673, 87433, 87509, 88793, 91081, 92761, 94321, 98737, 99367, 101641, 105097, 110881, 111973, 114343

Offset: 1

Robert G. Wilson v, Mar 20 2003

nonn

R. K. Guy, Unsolved Problems in Number Theory, A18.

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

Cf. A005113, A005105, A005106, A005107, A005108, A081633, A081634, A081636, A081637, A081638, A081639.

For Maple program see Mathar link in A005105.

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]]; ClassPlusNbr[n_] := Length[ NestWhileList[f, n, UnsameQ, All]] - 3; Prime[ Select[ Range[10820], ClassPlusNbr[ Prime[ # ]] == 7 &]]

A081638 Class 10+ primes.

Original entry on oeis.org

1065601, 2424973, 5114881, 7222561, 8124481, 8524091, 8647411, 8650321, 9190681, 9287521, 9590417, 10617601, 10929817, 11996161, 12349093, 12508081, 12786181, 12971117, 13570681, 14113027, 14308123, 14312743, 14476807

Offset: 1

Robert G. Wilson v, Mar 20 2003

nonn

R. K. Guy, Unsolved Problems in Number Theory, A18.

R. J. Mathar, Table of n, a(n) for n = 1..360

Cf. A005113, A005105, A005106, A005107, A005108, A081633, A081634, A081635, A081636, A081637, A081639.

For Maple program see Mathar link in A005105.

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]]; ClassPlusNbr[n_] := Length[ NestWhileList[f, n, UnsameQ, All]] - 3; Prime[ Select[ Range[150000], ClassPlusNbr[ Prime[ # ]] == 10 &]]

A081634 Class 6+ primes.

Original entry on oeis.org

2917, 4933, 5413, 7507, 8167, 8753, 10567, 10627, 11047, 11261, 11677, 12073, 12251, 12421, 12433, 12553, 12721, 14293, 15017, 17041, 18181, 18493, 19267, 19333, 20023, 21193, 21313, 21661, 22397, 24481, 25933, 26261, 26437, 27361

Offset: 1

Robert G. Wilson v, Mar 20 2003

nonn

R. K. Guy, Unsolved Problems in Number Theory, A18.

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

Cf. A005113, A005105, A005106, A005107, A005108, A081633, A081635, A081636, A081637, A081638, A081639.

For Maple program see Mathar link in A005105.

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]]; ClassPlusNbr[n_] := Length[ NestWhileList[f, n, UnsameQ, All]] - 3; Prime[ Select[ Range[3000], ClassPlusNbr[ Prime[ # ]] == 6 &]]

A081636 Class 8+ primes.

Original entry on oeis.org

49681, 109441, 120103, 151561, 198733, 210193, 246241, 255043, 266401, 280243, 295873, 326659, 326701, 347773, 355171, 360421, 368881, 397633, 397673, 423001, 441877, 447137, 471241, 480541, 489989, 499397, 508037, 511507, 532757, 539401

Offset: 1

Robert G. Wilson v, Mar 20 2003

nonn

R. K. Guy, Unsolved Problems in Number Theory, A18.

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

Cf. A005113, A005105, A005106, A005107, A005108, A081633, A081634, A081635, A081637, A081638, A081639.

For Maple program see Mathar link in A005105.

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]]; ClassPlusNbr[n_] := Length[ NestWhileList[f, n, UnsameQ, All]] - 3; Prime[ Select[ Range[44535], ClassPlusNbr[ Prime[ # ]] == 8 &]]

cp's OEIS Frontend

A005105 Class 1+ primes: primes of the form 2^i*3^j - 1 with i, j >= 0.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

GAP

Magma

Maple

Mathematica

PARI

Python

Formula

Extensions

A005113 Smallest prime in class n (sometimes written n+) according to the Erdős-Selfridge classification of primes.

Views

Author

Keywords

Comments

Examples

References

Crossrefs

Programs

Mathematica

PARI

PARI

Extensions

A005107 Class 3+ primes (for definition see A005105).

Views

Author

Keywords

References

Links

Crossrefs

Programs

Maple

Mathematica

Extensions

A081633 Class 5+ primes (for definition see A005105).

Views

Author

Keywords

References

Links

Crossrefs

Programs

Maple

Mathematica

A005106 Class 2+ primes (for definition see A005105).

Views

Author

Keywords

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A081639 Class 11+ primes.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Maple

Mathematica

A081635 Class 7+ primes.

Views

Author

Keywords

References