Denote $P[n]$ as the prime sequence $\{p\_1,p\_2,\cdots,p\_n\}$.


**Conjecture:**


* When $n=2k+1$ is odd, prime list $P[n]$ can be partitioned into two non-overlapping sublists, in which each sublist has equal sum $\operatorname{Total}[P[n]]/2$.
* When $n=2k$ is even, prime list $P[n]$ can be partitioned into two non-overlapping sublists, one sublist's sum is $(\operatorname{Total}[P[n]]-1)/2$, the other's is $(\operatorname{Total}[P[n]]+1)/2$.


For example:
$$
\begin{align\*}
3-2 &= 1 \\
5-3-2 &= 0 \\
7 - 5 - 3 + 2 &= 1 \\
11 - 7 - 5 + 3 - 2 &= 0 \\
13 - 11 - 7 + 5 + 3 - 2 &= 1
\end{align\*}
$$
and so on.


How could I write an efficient program to check it? Any clues to prove or disprove this conjecture?


BTW: I asked this question at mathgroup before, but I didn't describe it clearly.



A prime sequence can be partitioned into two sets of equal or consecutive sum
Scott Carnahan had an interesting idea; let's formalize it into an actual solution. We will show that, given $n \ge 2$ a positive integer, $p\_1, \cdots, p\_n$ the first *n* primes, we have some $e\_1, \cdots, e\_n$ with $e\_i = \pm 1$ such that $|e\_1p\_1 + e\_2p\_2 + \cdots + e\_np\_n| \le 1$. (Note that we may further stipulate that $e\_n = 1$.) A simple parity argument from here suffices to prove the conjecture.


We will prove this by induction on $n$. The cases $2 \le n \le 6$ are trivial to verify, and were provided already by a-boy. We now fix $n \ge 7$.


We first need some asymptotics in the form of the Bertrand-Chebyshev theorem; we use the formulation that for $m > 1$ there is a prime between $m$ and $2m$.


Write $S\_k = e\_np\_n + e\_{n-1}p\_{n-1} + \cdots + e\_{n-k+1}p\_{n-k+1}$, and let $M(k)$ be the minimum of $|S\_k|$ over all tuples $(e\_n, e\_{n-1}, \cdots, e\_{n-k+1})$. We stipulated earlier that $e\_n = 1$, so we have $M(1) = p\_n$. Two facts that will be useful to us in the future are that (1) $M(k+1) \le |M(k)-p\_{n-k}|$ and (2) if $|a| \le |b|$, then $\min{\{|a+b|,|a-b|\}} \le |b|$.


We claim that $M(k) \le p\_{n-k+1}$ for $k = 1, 2, \cdots, n-2$. We prove this by induction on $k$. The claim for $k = 1$ is trivial. Now if $M(k) \le p\_{n-k}$, then we are done, as $M(k+1) \le \min{\{|M(k)+p\_{n-k}|,|M(k)-p\_{n-k}|\}} \le p\_{n-k}$ by fact (2).


Now suppose $p\_{n-k} < M(k) \le p\_{n-k+1}$. Write $2m+1 = p\_{n-k+1} \ge p\_3 = 5$, so that $m > 1$. In this case we know that $m < p\_{n-k} < M(k) \le 2m$. But then $M(k+1) \le M(k) - p\_{n-k} \le 2m-(m+1) = (m-1) < p\_{n-k}$ as desired.


The fact that $M(k) \le p\_{n-k+1}$ is eminently useful. 


Indeed, we may use it to dispatch of the even case immediately. Set $k = n-6$. Then we have $M(n-6) \le 17$. As all sums considered in $M(n-6)$ are sums of an even number of odd terms, we in fact have $M(n-6) \le 16$ and even. Now we simply note that all odd numbers between -15 and 15 are realizable as sums and differences of the first 6 primes, which is left as an easy computational exercise.


In the odd case, we consider $k = n-5$. Then $M(n-5) \le 13$. For the same parity reasons as above, we have in fact $M(n-5) \le 12$. And again, we note that all even numbers between -12 and 12 are realizable as sums and differences of the first 5 primes - another easy computational exercise.


The limits of $n-6$ and $n-5$ are the best possible for our small-case analysis.


If we were to establish an algorithm for this, we could just do the greedy algorithm on choosing $e\_n$, then $e\_{n-1}$, and so on, each time choosing $e\_k$ so as to minimize $S\_{k+1}$ (or randomly if $S\_k = 0$). Our claim that $M(k) \le p\_{n-k}$ will continue to be satisfied by the greedy algorithm, as the proof of the claim does not involve changing prior $e\_i$. Thus our greedy-algorithm mimium modulus must satisfy the same inequality, and we continue until we are at $n-6$ or $n-5$, then finish as in our nonconstructive proof.


