|
%I #23 Dec 05 2020 04:53:26
%S 2,5,37,193,2161,23041,241921,2903041,55987201,958003201,17915904001,
%T 250822656001,5518098432001,142216445952001,2897001676800001,
%U 90386452316160001,1807729046323200001,52563198423859200001
%N Smallest prime which is 1 more than the product of n distinct composite numbers.
%C Let K(m) be the smallest possible K satisfying the Theorem. Conjecture: K(m) ~ m, i.e., a(k) ~ A002808(1)*...*A002808(k), only very few of the last factors will be insignificantly larger.
%C Let K(b,r) be the smallest possible K satisfying the Corollary, i.e., the index from which on all a(k)-1 are multiples of b^r. With the preceding conjecture, there are asymptotically at least (k+PrimePi(A002808(k)))/b multiples of b among the factors of a(k)-1, so this is an (asymptotic) lower bound on r.
%C Experimentally, a(k) = 1 + Product_{i>=1} prime(i)^e(i), with e(1)~k*3/2, e(2)~k*2/3, e(3)~k/4, e(4)~k/5, ... (Here ~ is not asymptotic equivalence.) Is there a simple formula? - _M. F. Hasler_, Jun 16 2007
%H Jinyuan Wang, <a href="/A081545/b081545.txt">Table of n, a(n) for n = 0..300</a> (terms 0..99 from M. F. Hasler)
%F Theorem: For any m > 0 there is a K > 0 such that for all k > K, a(k)-1 is divisible by the first m composite numbers.
%F Corollary: For any b > 1, r > 0 there is a K > 0 such that for all k > K, a(k) == 1 (mod b^r). Taking b=10 shows that all a(k) > a(8) end in 0..01 with an increasing number of zeros. - _M. F. Hasler_, Jun 16 2007
%e Writing c(n) for the n-th composite number A002808(n):
%e a(0) = (Product_{i=1..0} c(i))+1 = 1+1 = 2 (empty product).
%e a(1) = c(1)+1 = 4+1 = 5.
%e a(2) = c(1)*c(4)+1 = 4*9+1 = 37, since c(1)*c(k)+1 is not prime for k < 4.
%e a(3) = c(1)*c(2)*c(3)+1 = 4*6*8 + 1 = 193.
%e a(4) = c(1)*c(2)*c(4)*c(5)+1 = 2161, nothing better since c(6)*c(3) > c(5)*c(4).
%e a(5) = c(1)*c(2)*c(3)*c(5)*c(6)+1 = 23041, none better since c(7)*c(4) > c(5)*c(6).
%e a(6) = c(1)*c(2)*c(3)*c(4)*c(5)*c(7)+1 = 241921, best since c(1)*...*c(6)+1 is not prime.
%e a(7) = p(7)+1 = 2903041 with p(n) = Product_{i=1..n} c(i). - _M. F. Hasler_, Jun 16 2007
%o (PARI) A081545(n, b=0 /*best*/, p=1 /*product*/, f=[]/*factors*/)={ if( #f<n, /* initialize f[1..n] to first n composites */ b=3; f=vector( n, i, while( isprime( b++ ),); b ); p=prod( i=1,n-1, f[i] ); /* get upper limit by incrementing last factor until prime is found */ while( !isprime( 1+p*b ), while( isprime( b++ ),)); b=1+p*b; p*=f[n] ); if( isprime( 1+p ), /*print("best: " f);*/ 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 = A081545( n-1, b, p*f[n], f), while( isprime( f[n]++ ),) /* next composite */ ); b } /* then vector(30,n,A081545(n-1)) gives the first 30 terms */ \\ _M. F. Hasler_, Jun 16 2007
%Y Cf. A002808 (composite numbers), A073918, A081546, A131100.
%K nonn,nice
%O 0,1
%A _Amarnath Murthy_, Apr 01 2003
%E More terms from _Michel ten Voorde_ Jun 13 2003
%E Terms beyond a(8) by _M. F. Hasler_ Jun 16 2007
| 