A071810

[Max A.]

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