cp's OEIS Frontend

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.

%I A073918 #29 Mar 16 2023 18:35:33
%S A073918 2,3,7,31,211,2311,43891,870871,13123111,300690391,6915878971,
%T A073918 200560490131,11406069164491,386480064480511,18826412648012971,
%U A073918 693386350578511591,37508276737897976011,3087649419126112110271,183452981525059000664911,11465419967969569966774411
%N 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.
%C A073918 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 A073918 Max Alekseyev, <a href="/A073918/b073918.txt">Table of n, a(n) for n = 0..100</a> (terms for n = 0..24 from M. F. Hasler)
%F A073918 From _M. F. Hasler_, Jun 16 2007 (Start):
%F A073918 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 A073918 Corollary: For any m > 1 there is K > 0 such that for all k > K, a(k) = 1 (mod m).
%F A073918 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 A073918 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 A073918 a(0) = 1 + 1 = 2 (empty product of zero primes).
%e A073918 a(1) = 1 + 2 = 3.
%e A073918 a(2) = 1 + 2*3 = 7.
%e A073918 a(3) = 1 + 2*3*5 = 31.
%e A073918 a(4) = 1 + 2*3*5*7 = 211.
%e A073918 a(5) = 1 + 2*3*5*7*11 = 1 + 11# = 2311.
%e A073918 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 A073918 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 A073918 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 A073918 (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 A073918 Cf. A055734 (number of distinct prime factors of phi(n)).
%Y A073918 Cf. A073917, A098026.
%Y A073918 Cf. A000040 (primes), A002110 (primorial), A081545 (same with composite instead of primes).
%K A073918 nonn
%O A073918 0,1
%A A073918 _Amarnath Murthy_, Aug 18 2002
%E A073918 More terms from _Vladeta Jovovic_, Aug 20 2002
%E A073918 Edited by _M. F. Hasler_, May 31 2018