login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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

%I

%S 2,3,7,31,211,2311,43891,870871,13123111,300690391,6915878971,

%T 200560490131,11406069164491,386480064480511,18826412648012971,

%U 693386350578511591,37508276737897976011,3087649419126112110271,183452981525059000664911,11465419967969569966774411

%N 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.

%C 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

%H M. F. Hasler Jun 16 2007, <a href="/A073918/b073918.txt">Table of n, a(n) for n = 0..24</a>

%F From _M. F. Hasler_, Jun 16 2007 (Start):

%F 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.

%F Corollary: For any m > 1 there is K > 0 such that for all k > K, a(k) = 1 (mod m).

%F 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)

%F 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

%e a(0) = 1 + 1 = 2 (empty product of zero primes).

%e a(1) = 1 + 2 = 3.

%e a(2) = 1 + 2*3 = 7.

%e a(3) = 1 + 2*3*5 = 31.

%e a(4) = 1 + 2*3*5*7 = 211.

%e a(5) = 1 + 2*3*5*7*11 = 1 + 11# = 2311.

%e 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}.

%e 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

%t Generate[pIndex_, i_] := Module[{p2, t}, p2=pIndex; While[p2[[i]]++; Do[p2[[j]]=p2[[i]]+j-i, {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

%o (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 n-th 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( n-1, 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

%Y Cf. A055734 (number of distinct prime factors of phi(n)).

%Y Cf. A073917, A098026.

%Y Cf. A000040 (primes), A002110 (primorial), A081545 (same with composite instead of primes).

%K nonn

%O 0,1

%A _Amarnath Murthy_, Aug 18 2002

%E More terms from _Vladeta Jovovic_, Aug 20 2002

%E Edited by _M. F. Hasler_, May 31 2018

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified June 12 10:58 EDT 2021. Contains 344947 sequences. (Running on oeis4.)