6
$\begingroup$

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 ?

$\endgroup$
6
  • 3
    $\begingroup$ It looks like the best solution is to write a short computer program. $\endgroup$ Oct 7, 2019 at 10:35
  • $\begingroup$ @ Rory Daulton can't we solve it using a pen and a paper? $\endgroup$
    – user712153
    Oct 7, 2019 at 10:35
  • 2
    $\begingroup$ 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. $\endgroup$ Oct 7, 2019 at 10:38
  • $\begingroup$ @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. $\endgroup$
    – Peter
    Oct 7, 2019 at 12:36
  • 2
    $\begingroup$ 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)$. $\endgroup$
    – Vepir
    Oct 7, 2019 at 12:37

1 Answer 1

8
$\begingroup$

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.

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

You must log in to answer this question.