A071810

[franktaw at netscape.net]

Right.  In a sense, we're inverting the question: instead of asking for 
each subset, is its sum prime, we're asking for each prime, how many 
subsets sum to it.  To look at it a bit differently, how many ways are 
there to partition each prime into a sum of distinct primes, each less 
than or equal to Prime(n)?

It's been a while since I took statistics, but I think you can use a 
variant of the Central Limit Theorem to show that the coefficients of 
f_n(x) are sufficiently close to a normal distribution that a(n) ~ 2^n 
/ (2 log n).  The 2 in the denominator comes from the fact that the 
mean value of a subset sum is 1/2 sum_{k=1}^n Prime(k), which is 
approximately 1/2 n^2 log(n).  The probability that a number in that 
range is prime is about log (1/2 n^2 log n) = 2 log n + O(log log n).  
You also need to show that the standard deviation is large enough to 
average out the unevenness of the prime distribution, which gets into 
issues in number theory that are beyond what I can deal with.

Franklin T. Adams-Watters


-----Original Message-----
From: maxale at gmail.com

On 9/7/06, franktaw at netscape.net <franktaw at netscape.net> wrote: 
> I don't know for sure how he computed them, but the following works: 
> 
> Compute f_n(x) = product_{k=1}^n 1+x^Prime(k) = f_{n-1}(x) * 
> (1+x^Prime(n)). Then sum the coefficients of x^p in f_n(x) for p 
> prime. You only need to look at primes <= the sum of the first n 
> primes. 
 
The reason why this does not eat a lot of memory is the fact that the 
set of all numbers representable as the sum of some of the first n 
primes is rather small. The trivial bound on its size is n*pn ~= 
n^2*ln(n). That allows to compute many terms either implicitly as 
shown above or explicitly using a sort of dynamic programming. 
 
Max 


________________________________________________________________________
Check Out the new free AIM(R) Mail -- 2 GB of storage and 
industry-leading spam and email virus protection.