Suppose we want to show that all natural numbers may be generated by summing prime numbers, then the proof may be as follows:

  1. In case the natural number in question is even, it must be a sum of twos.
  2. In case it is odd, we can replace one of the twos of the even number smaller than this number by one with a three.

This means that one isn't generated in this way, but the rest of the natural numbers will be.

Suppose we take the two out of the set of all prime numbers. With a little bit more complicated proof we can show that all numbers greater than four can be generated by summing the remaining primes.

Suppose we take the two and the three out, then, again, we can show that all number greater than fifteen can be generated using the remaining primes.

The Question

Using the example above, let $+^*$ be the operation of "as many sums as needed", let $P$ be the set of all primes. Define $N_p$ be the number such that $\{q \;|\; s, r \in P \land s, r \geq p \land q = s +^* r\} \cap \{ n \;|\; n \in \mathbb{N} \land n < N_p\} = \emptyset$. Is the set $\{N_q \;|\; q \in \mathbb{N}\}$ finite?

In other words: suppose we keep removing the smallest prime from the set of all primes, will we ever encounter a situation s.t. there will be repeating intervals of natural numbers which we cannot generate summing the remaining primes?

PS. This is not a homework. The original problem I was facing was related to automata theory and free monoid of a language defined as $L'=L^*, L=\{a^p \;|\; Prime(p)\}$, but it wasn't asking to solve the above question.


In fact, much more than this is true. You don't need infinitely many primes; any two primes will suffice to generate all sufficiently large numbers (in particular, every number greater than or equal to $(p-1)(q-1)$). For more information, look up the phrases Frobenius Coin Problem or 'McNugget problem'.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.