A160763 - OEIS

%I #17 Sep 24 2015 12:20:35

%S 1,3,49,87,130321,4753,7212549413161,285541,7890946561,834472284661,

%T 174913992535407978606601,19699251391,

%U 23205949656945057666311162427422570380321

%N Least number having n divisors such that every sum of two or more divisors is composite.

%C First term of A093893 to have n divisors.

%C a(2)=3, a(3)=7^2, a(4)=3*29, a(5)=19^4, a(6)=7^2*97, a(7)=139^6, a(8)=31*61*151, a(9)=211^2*421^2, a(10)=211^4*421, a(11)=211^10, a(12)=211^2*421*1051, a(13)=2311^12, 5.92*10^20<a(14)<=2311^6*50821, a(15)<=120121^4*150151^2, a(16)<=120121*150151*180181*270271, a(17)=120121^16, a(18)<=4084081^2*5105101^2*8168161, a(19)=2312311^18, (10^7)^22<a(23)<=892371481^22, ...

%C Proof that a(n) exists for all n: We will show that there is a prime p such that the sums of two or more divisors of p^(n-1) are all composite. Let Q be the product of the primes less than or equal to n. Let p be a prime of the form Qk+1. Observe that the divisors of p^(n-1), which are just powers of p, have the same form Qk+1 (but with different k, of course). Hence a sum of r of these powers will have the form Qk+r (for some k). Due to the way Q is constructed and r <= n, r and Q have a common factor, making Qk+r composite. Furthermore, by Dirichlet's theorem, we know there are an infinite number of primes p that will work for each n. [_T. D. Noe_, Jun 01 2009]

%C If a(14) < 2311^6*50821, then a(14) = p^6*q with primes p,q such that 139<=p<1000 and p^6 in A093893. - _Hagen von Eitzen_, Jun 03 2009

%C If a(14) < 2311^6*50821, then a(14) = p^6*q with p in {139,151,181,211,241} and q being prime. - _Max Alekseyev_, Sep 24 2015

%t (* first do *) Needs["Combinatorica`"] (* then *) f[n_] := Block[{d = Divisors@n, k, mx = 1 + 2^DivisorSigma[0, n]}, k = 2 + Length@d; While[k < mx, If[ PrimeQ[Plus @@ NthSubset[k, d]], Break[]]; k++ ]; If[k == mx, Length@d, 0]]; t = Table[0, {20}]; k = 1; While[k < 2*10^7, a = f@k; If[a > 0 && t[[a]] == 0, t[[a]] = k; Print[{a, k}]]; k += 2]; t

%Y Cf. A093893, A000005.

%K nonn

%O 1,2

%A _Robert G. Wilson v_, May 25 2009, May 29 2009

%E Definition revised by _N. J. A. Sloane_, May 30 2009

%E Term a(9) corrected, a(10)-a(13) and more upper bounds added by _Max Alekseyev_ and _Hagen von Eitzen_, May 30 2009

%E a(19) from _M. F. Hasler_, May 31 2009

%E Edited by _Max Alekseyev_, Sep 25 2009

%E a(1)=1 prepended by _Max Alekseyev_, Mar 31 2015