# 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 ?

• It looks like the best solution is to write a short computer program. Oct 7, 2019 at 10:35
• @ Rory Daulton can't we solve it using a pen and a paper?
– user712153
Oct 7, 2019 at 10:35
• Could you solve it with pen and paper? Of course, but it looks tedious. That is why I believe that the best way is with a computer program. The program would be short and easy to write. I have not spent much time on your problem, so I could have overlooked a quick pen-and-paper method. Oct 7, 2019 at 10:38
• @Alone_Knight What you could do : Start with $9$ primes and permute the tenth prime and delete all numbers you can get this way. Not sure whether this efficient however. Oct 7, 2019 at 12:36
• It seems only $19$ numbers $\in(129,1000]$ can't be represented as a sum of $10$ distinct primes: $\{130, 132, 133, 134, 135, 136, 138, 139, 140, 142, 144, 146, 148, 150, 152, 154, 156, 160, 162\}$. The rest each have a representation consisting of: some prime, and nine primes $\le p_{12}$, where $p_{12}$ is the $12$th prime. *It seems that $9$-length combinations of first $12$ primes are sufficient to fill in every gap between some prime $\lt 1000$ and every number $\in(162,1000]$.* - If we prove something like this result, then only handful numbers remain to be checked: $(129,162)$. Oct 7, 2019 at 12:37

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:
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.

• Nice answer :) Small correction - since your count starts at $129$, shouldn't the total be $999-128-19=852$ ? Oct 7, 2019 at 15:01
• @gandalf61 Oh I see, I forgot to exclude the $100,...,128$ numbers. Thank you for pointing this out. Oct 7, 2019 at 15:27
• Looks fine now - good work :) Oct 7, 2019 at 15:56