

A073918


Smallest prime which is 1 more than a product of n distinct primes: a(n) is a prime and a(n)  1 is a squarefree number with n prime factors.


14



2, 3, 7, 31, 211, 2311, 43891, 870871, 13123111, 300690391, 6915878971, 200560490131, 11406069164491, 386480064480511, 18826412648012971, 693386350578511591, 37508276737897976011, 3087649419126112110271, 183452981525059000664911, 11465419967969569966774411
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,1


COMMENTS

Apparently the same as record values of A055734: least k such that phi(k) has n distinct prime factors, where phi is Euler's totient function. If the Mathematica program is used for large n, then "fact" should be reduced to, say, 1.1 in order to increase the search speed.  T. D. Noe, Dec 17 2003


LINKS

M. F. Hasler Jun 16 2007, Table of n, a(n) for n = 0..24


FORMULA

From M. F. Hasler, Jun 16 2007 (Start):
Conjecture: For any m > 0 there is K > 0 such that for all k > K, a(k)1 is divisible by the first m primes.
Corollary: For any m > 1 there is K > 0 such that for all k > K, a(k) = 1 (mod m).
Conjecture 2: Let K(m) be the smallest possible K satisfying the above Conjecture. Then K(m) ~ m, i.e., a(k) ~ A002110(k), only very few of the last factors will be a bit larger. (End)
Remark: the last "~" above was not intended to mean asymptotic equivalence. It appears that lim inf a(n)/A002110(n) = 1, but the lim sup might well be larger. It would be interesting to know whether it has a finite value.  M. F. Hasler, May 31 2018


EXAMPLE

a(0) = 1 + 1 = 2 (empty product of zero primes).
a(1) = 1 + 2 = 3.
a(2) = 1 + 2*3 = 7.
a(3) = 1 + 2*3*5 = 31.
a(4) = 1 + 2*3*5*7 = 211.
a(5) = 1 + 2*3*5*7*11 = 1 + 11# = 2311.
a(6) = 1 + 2*3*5*7*11*19 = 43891, since 13# + 1 and 11#*17 + 1 = 17#/13 + 1 is not prime, and 17#/p + 1 is larger than a(6) for all p in {2, ..., 11}.
The index of the smallest prime which is not a factor of a(n)+1 is (1, 2, 3, 4, 5, 6, 6, 7, 7, 9, 10, 12, 11, 12, 13, 15, 16, 15, 16, 18, 19, 20, 21, 22, 22, 23, 25, 27, 26, 29, 29, ...) for n = 0, 1, 2, ...  M. F. Hasler, May 31 2018


MATHEMATICA

Generate[pIndex_, i_] := Module[{p2, t}, p2=pIndex; While[p2[[i]]++; Do[p2[[j]]=p2[[i]]+ji, {j, i+1, Length[p2]}]; t=Times@@Prime[p2]; t<fact*base, AppendTo[s, t]; If[i<Length[p2], Generate[p2, i+1]]]]; fact=2; Table[pin=Range[n]; base=Times@@Prime[pin]; s={base}; Do[Generate[pin, j], {j, n}]; s=Sort[s]; noPrime=True; i=0; While[noPrime&&i<Length[s], i++; noPrime=!PrimeQ[1+s[[i]]]]; If[noPrime, 1, 1+s[[i]]], {n, 20}]  from T. D. Noe


PROG

(PARI) A073918(n, b=0 /*best*/, p=1 /*product*/, f=[]/*factors*/)={ if( #f<n, f=primes(n); p=factorback(f[^1]); b=f[n]; /* get upper limit by incrementing last factor until prime is found */ while( !isprime( 1+p*b), b=nextprime(b+1)); b=1+p*b; p*=f[n] ); if( isprime( 1+p ), return( 1+p )); /* always p < b */ /* increase the nth factor to recursively explore all solutions < b */ p /= f[n]; until( b <= 1+p*f[n]  ( n < #f && f[n] >= f[n+1] )  !b = A073918( n1, b, p*f[n], f), f[n]= nextprime( f[n]+1 ) ); b } \\ then, e.g.: apply(A073918, [0..30]).  M. F. Hasler Jun 16 2007


CROSSREFS

Cf. A055734 (number of distinct prime factors of phi(n)).
Cf. A073917, A098026.
Cf. A000040 (primes), A002110 (primorial), A081545 (same with composite instead of primes).
Sequence in context: A006862 A038710 A241196 * A096350 A018239 A066279
Adjacent sequences: A073915 A073916 A073917 * A073919 A073920 A073921


KEYWORD

nonn


AUTHOR

Amarnath Murthy, Aug 18 2002


EXTENSIONS

More terms from Vladeta Jovovic, Aug 20 2002
Edited by M. F. Hasler, May 31 2018


STATUS

approved



