|
| |
|
|
A005113
|
|
a(n) is the least prime of class n (sometimes written n+) according to the Erdos-Selfridge classification of primes.
(Formerly M2057)
|
|
41
| |
|
|
2, 13, 37, 73, 1021, 2917, 15013, 49681, 532801, 1065601, 8524807, 68198461, 545587687, 1704961513, 23869461181, 288310406533
(list; graph; refs; listen; history; internal format)
|
|
|
|
OFFSET
| 1,1
|
|
|
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.
John W. Layman (layman(AT)math.vt.edu) 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.
2*a(15)-1 = 47738922361 < a(16) <= 429650301257 = 9*2*a(15)-1 - M. F. Hasler (Maximilian.Hasler(AT)gmail.com), Apr 02 2007
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 (Maximilian.Hasler(AT)gmail.com), Apr 09 2007
a(16) <= 288310406533, with equality if 144155203267 is the 12th 15+ prime; 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 (Maximilian.Hasler(AT)gmail.com), Apr 09 2007
a(16) calculated using A129475(n) up to n=19. - M. F. Hasler (Maximilian.Hasler(AT)gmail.com), Apr 16 2007
|
|
|
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).
|
|
|
FORMULA
| 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 (Maximilian.Hasler(AT)gmail.com), Apr 02 2007
|
|
|
EXAMPLE
| 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.
|
|
|
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
|
|
|
PROG
| (PARI) checkclass(n, p)={ n=factor(n+1)[, 1]; if( n[ #n] <= 3, return(1)); if( #p <= 1 | n[ #n] < p[ #p], return(2)); n[1]=p[ #p]; p=vecextract(p, "^-1"); forstep( i=#n, 2, -1, if( n[i] < n[1], break); if( checkclass(n[i], p) > #p, return(2+#p))); 0 }; A005113(n, p, a=[])={ while( #a<n, until( checkclass(p, a) > #a, p=nextprime(p+1)); a=concat(a, p); p=a[ #a]*2-2); a }; A005113(11) /* < 10 sec @ 2 GHz */ - M. F. Hasler (Maximilian.Hasler(AT)gmail.com), Apr 02 2007
(PARI) class( n, s=+1 /* +1 for n+ class, -1 for n- class */ ) = { if( isprime(n), if(( n=factor(n+s)[, 1] ) & n[ #n]>3, vecsort(vector(#n, i, class(n[i], s)))[ #n]+1, 1), 0) }; 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 (Maximilian.Hasler(AT)gmail.com), Apr 09 2007
|
|
|
CROSSREFS
| Cf. A056637, A005105, A005106, A005107, A005108, A019268.
Cf. A081633 - A081639, A084071, A090468, A129474 - A129476, A129469.
Sequence in context: A063092 A034011 A085497 * A072857 A119535 A011919
Adjacent sequences: A005110 A005111 A005112 * A005114 A005115 A005116
|
|
|
KEYWORD
| more,nonn
|
|
|
AUTHOR
| N. J. A. Sloane (njas(AT)research.att.com).
|
|
|
EXTENSIONS
| Extended through a(12) by Robert G. Wilson v (rgwv(AT)rgwv.com).
a(13) from John W. Layman (layman(AT)math.vt.edu).
a(14) from Don Reble, Apr 11, 2003. 4294967296 < a(15) <= 23869461181.
a(15) from Sam Handler (sam_5_5_5_0(AT)yahoo.com), Aug 17 2006
a(7) corrected by Tomas Oliveira e Silva, Oct 27 2006
a(16) from M. F. Hasler (Maximilian.Hasler(AT)gmail.com), Apr 16 2007
|
| |
|
|
