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

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

Offset: 1

Author

N. J. A. Sloane

Keywords

• more
• nonn

Comments

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

Examples

			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.
		

References

• 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).

Crossrefs

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

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

Programs

Mathematica

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

PARI

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

PARI

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

Extensions

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