Is it true that the first n prime numbers can be divided into two sets with sums differing at most by 1 for all n>1?

Question

Example ($n=6$):

$$2+5+13=20$$

$$3+7+11=21$$

Answer 1

To get this question off the "Unanswered" list, here's a write-up of the proof sketched in comments. Oleg567 should get the credit for the key idea of the specific statement to prove; I've given him two weeks to write up an answer, but maybe he thought the link to MathOverflow was sufficient.

---

Notation:

• $p_n$ denotes the $n$th prime number
• $P_n = \{p_1, \ldots, p_n\}$ denotes the set of the first $n$ prime numbers
• $S_n = \sum_{i=1}^n p_i$ denotes the sum of the first $n$ prime numbers
• $\sigma_n = \{ \sum_{p \in s} p \mid s \subseteq P \}$ denotes the set of sums which are possible with a subset of the first $n$ prime numbers

The property we prove is that $\sigma_n = \{0, 1, 2, \ldots, S_n\} \setminus \{1, 4, 6, S_n - 6, S_n - 4, S_n - 1\}$.

The proof is by induction. I'm going to tackle the inductive step first because then we'll see how many base cases we need. In other words, this is not a polished proof such as one might publish but a stream-of-consciousness to show the thought process.

Inductive step

Suppose that $n$ is sufficiently large (to be clarified) and that the property holds for all smaller values of $n$.

$\sigma_n = \sigma_{n-1} \cup \{ x + p_n \mid x \in \sigma_{n-1} \}$. The first part of that union gives us $\{0, 1, 2, \ldots, S_{n-1}\} \setminus \{1, 4, 6, S_{n-1} - 6, S_{n-1} - 4, S_{n-1} - 1\}$, so we need to show that the second part of the union gives us $\{S_{n-1} - 6, S_{n-1} - 4, S_{n-1} - 1\}$ and $\{S_{n-1} + 1, S_{n-1} + 2, \ldots, S_n\} \setminus \{S_n - 6, S_n - 4, S_n - 1\}$; i.e. that $$\begin{eqnarray} \{S_{n-1} - 6 - p_n, S_{n-1} - 4 - p_n, S_{n-1} - 1 - p_n\} \subseteq \sigma_{n-1} & \hspace{2em}\textrm{(1)} \\ \{S_{n-1} + 1, S_{n-1} + 2, \ldots, S_n\} \setminus \{S_n - 6, S_n - 4, S_n - 1\} \subseteq \{ x + p_n \mid x \in \sigma_{n-1} \} & \hspace{2em}\textrm{(2)} \end{eqnarray}$$

If $S_{n-1} - 6 - p_n > 6$ and $S_{n-1} - 6 - p_n \not\in \{S_{n-1} - 6, S_{n-1} - 4, S_{n-1} - 1\}$ then the first number in $(1)$ is covered. Rephrased, we want $$ p_n < S_{n-1} - 12 \\ p_n \not \in \{ 0, -2, -5 \}$$

Similarly for the other two special cases we want

$$ p_n < S_{n-1} - 10 \\ p_n \not\in \{ 2, 0, -3 \} \\ p_n < S_{n-1} - 7 \\ p_n \not\in \{ 5, 3, 0 \} $$

$(2)$ can be rewritten as $$\forall {0 \le x < p_n, x \not\in \{1,4,6\}}: S_{n-1} + p_n - x \in \{ x + p_n \mid x \in \sigma_{n-1} \}$$ or $$\forall {0 \le x < p_n, x \not\in \{1,4,6\}}: S_{n-1} - x \in \sigma_{n-1}$$ which again boils down to $S_{n-1} - p_n - 1 > 6$ or $p_n < S_{n-1} - 7$.

So the inductive step is good as long as $$5 < p_n < S_{n-1} - 12$$

Here we apply Bertrand's postulate. The stronger the version taken, the simpler the proof will be, so we take Hanson's tight version that $\forall 2 \le x \in \mathbb{N}: \exists 3x < p < 4x: p \textrm{ is prime}$. If $p_k \equiv 1 \pmod 3$ then take $x = \frac{p_k + 2}{3}$ and $p_{k+1} < \frac{4p_k + 8}{3}$ or $p_k > \frac{3}{4}p_{k+1} - 2$; if $p_k \equiv 2 \pmod 3$ then take $x = \frac{p_k + 1}{3}$ and $p_{k+1} < \frac{4p_k + 4}{3}$ or $p_k > \frac34 p_{k+1} - 1$.

In either case $p_k \ge \frac{3}{4}p_{k+1} - 1$, so by induction $$p_{n-i} \ge \left(x \to \tfrac34 x - 1 \right)^i(p_n) = \left(\tfrac34\right)^i p_n - \frac{\left(\tfrac 34\right)^i - 1}{\tfrac 34 - 1} = \left(\tfrac34\right)^i (p_n + 4) - 4$$

Then $$S_{n-1} = \sum_{i=1}^{n-1} p_i \ge \sum_{i=1}^{n-1} \left(\tfrac34\right)^i (p_n + 4) - 4 = 3 (p_n + 4) \left(1 - \left(\tfrac34\right)^{n-1}\right) - 4(n-1) $$ Thus certainly $S_{n-1} > p_n + 12$ if $$3 (p_n + 4) \left(1 - \left(\tfrac34\right)^{n-1}\right) - 4(n-1) > p_n + 12$$ i.e. if $$p_n > \frac{4^n (n-1) + 4 \times 3^n}{2 \times 4^{n-1} - 3^n}$$

This is getting a bit long, so I'll abbreviate the next step. We show¹ that the right hand side grows by less than $2$ for $n > 5$, and since primes are at least $2$ apart and $$19 = p_8 > \frac{4^8 (8-1) + 4 \times 3^8}{2 \times 4^{8-1} - 3^8} = \frac{484996}{26207} \approx 18.51$$ we're good for $n \ge 8$.

Base cases

• $n = 1$: the subset sums of $\{2\}$ are $\{0, 2\}$, which is correct.
• $n = 2$: the subset sums of $\{2, 3\}$ are $\{0, 2, 3, 5\}$, which is correct.
• $n = 3$: the subset sums of $\{2, 3, 5\}$ are $\{0, 2, 3, 5, 7, 8, 10\}$, which is correct.
• $n = 4$: the subset sums of $\{2, 3, 5, 7\}$ are $\{0, 2, 3, 5, 7, 8, 9, 10, 12, 14, 15, 17\}$, which is correct.
• $n = 5$: the subset sums of $\{2, 3, 5, 7, 11\}$ are $\{0, 2, 3, 5, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 23, 25, 26, 28\}$, which is correct.
• $n = 6$: the subset sums of $\{2, 3, 5, 7, 11, 13\}$ are $\{0, 2, 3, 5, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 36, 38, 39, 41\}$, which is correct.
• $n = 7$: the subset sums of $\{2, 3, 5, 7, 11, 13, 17\}$ are $\{0, 2, 3, 5, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 53, 55, 56, 58\}$, which is correct.

Postscript

You said in the comments that

Moreover, if the statement can be proven and if it is true for multiple other sequences as well then, in my eyes, the primes seem to progress in a highly structured way - no?

Not really. I think that the weakest form of Bertrand's postulate would be enough, and even the form we use just says that if the primes grow exponentially then the exponent is less than $\tfrac43$. Much stronger bounds on their growth are known (it's not exponential: the $n$th prime is about $n \ln n$), but despite this for many purposes they can be treated as distributed randomly with a known distribution.

---

¹ $$\frac{4^{n+1} ({n+1}-1) + 4 \times 3^{n+1}} {2 \times 4^{{n+1}-1} - 3^{n+1}} - \frac{4^n (n-1) + 4 \times 3^n} {2 \times 4^{n-1} - 3^n} = 2 - \frac{(n - 2) 12^n + 6 \times 9^n}{16^n - 3.5\times 12^n + 3\times 9^n} \\ $$