How many natural number between $100$ and $1000$ exist which can be expressed as sum of 10 different primes.

How many natural number between $100$ and $1000$ exist which can be expressed as sum of 10 different primes.

For example , we can write $129$ as :

$$129 = 2+3+5+7+11+13+17+19+23+29$$

What would be the best way to solve this ? We could use modular arithmetic to reduce the number of test expression , but is there a more efficient way ?

Solution 1:

The smallest number we can obtain is the sum of first ten primes: $\sum\limits_{k=1}^{10} p_k=129$, so lets observe $(129,1000)$ instead of $(100,1000)$, and subtract the $28$ eliminated numbers at the end.

First we show numbers $179,\dots,1000$ can be expressed as the sum of exactly $10$ distinct primes.

The largest prime gap below $1129$ is $20$.

Taking $9$-length combinations of first $12$ primes gives us $42$ consecutive values: $137+1,\dots,137+42$ among their sums. This is more than enough to cover those gaps, as $42\gt 20$. Also, the $13$th prime is $p_{13}=41$.

This means we can obtain every number $179,\dots,1000$ as a sum of $10$ distinct primes, using some prime $(p_{n\ge 13})\ge 41$ and some $9$-length combination of first $12$ primes, since we have:

$$ (p_{n\ge 13})+(137+\{1,\dots,42\})$$

Where the largest gap between consecutive $p_{n}$ is $20\lt 42$, among numbers $\lt 1000 \lt 1129$.

Secondly and lastly, we check the remaining $50$ numbers with a simple program.

This leaves us to check only $50$ numbers in the interval $(129,179)$, to find those that can't be represented as a sum of exactly $10$ distinct primes.

It is sufficient to observe all primes up to $179-\left(\sum\limits_{k=1}^9 p_k=100\right)=79$, otherwise our sum is $\gt 179$.

I find it easier to write a simple brute-force python program, rather than checking this by hand:

(This sums all possible $10$-length combinations of primes $2,\dots,79$ and returns sums it didn't find.)

p = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79]

from itertools import combinations

sums = set([]);
for combo in combinations(p, 10):
    s = sum(combo)
    if s <= 179:
        sums.add(s)
not_possible = (set([i for i in range(129,179)])).difference(sums)
print(len(not_possible))
print(sorted(not_possible))

Which finds the only $19$ numbers that can't be represented as such sums:

19
[130, 132, 133, 134, 135, 136, 138, 139, 140, 142, 144, 146, 148, 150, 152, 154, 156, 160, 162]

Finally, we have: there are $|(100,1000)|-28-19=899-28-19=852$ such numbers.