# A prime sequence can be partitioned into two sets of equal or consecutive sum

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.

-
There is no need to write a program, because the statement is true. Fix n, and starting from the largest prime in P[n] and following decreasing order, put each prime into the pile with the smaller sum. Standard estimates like Bertrand's postulate (and improvements - see Wikipedia) imply the difference between the two piles will be less than, say, 3/2 the next prime on the list. This reduces to a small case analysis at the end. –  S. Carnahan Aug 5 '10 at 5:11
Google should find various algorithms to solve the so-called partition problem en.wikipedia.org/wiki/Partition_problem, which can be solved efficiently in lots of cases, it seems. –  Mariano Suárez-Alvarez Aug 5 '10 at 5:11
@Scott, I think that when you start with the first 11 primes that greedy algorithm does not work. –  Mariano Suárez-Alvarez Aug 5 '10 at 5:48
Thank you, Scoot,Mariano. @Mariano,Yes! According to the greedy algorithm: (31+19+17+7+5) -(29+23+13+11+3)=79-79=0, then how to put 2? While (31+29+17+3)=80, 23+13+19+11+7+5+2=80, to be more beautiful, 31+29-23-19+17-13-11-7-5+3-2=0 –  user8140 Aug 5 '10 at 6:57
Sorry, by "small case analysis at the end" I meant that the smallest primes needed to be arranged by hand, not that the greedy algorithm could be proved to work by case analysis. –  S. Carnahan Aug 10 '10 at 17:18

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.

-
please read Mariano Suárez-Alvarez's comment! when M(n−1)=0, then it must be M(n)=2 – a-boy 0 secs ago –  user8140 Aug 15 '10 at 11:47
I think that we could just do the greedy algorithm on choosing `$e_n, then e_n−1, and so on, until to e_6, then choose e_6,...,e_1 by hand.$' –  user8140 Aug 15 '10 at 12:00

This is a special case of the subset-sum problem, which is NP-complete in general but probably tractable in your case. Wikipedia describes a pseudo-polynomial-time algorithm that may work for you.

-
when n is big(for example n=100), I think the "pseudo-polynomial-time algorithm" doesn't work efficiently for this problem. I wish to get a simple strategy to decide to the two parts of the prime sequence, however the greedy algorithm fails to achieve. –  user8140 Aug 5 '10 at 7:10
@a-boy: Nope: the performance is O(n^(3+epsilon)) (if I computed correctly), so n=100 is very manageable (takes about 0.05 seconds on my laptop, not highly optimized). –  Darsh Ranjan Aug 6 '10 at 5:03

Expanding on the comment above, consider Pn, the set of the first n primes, and SSn, the set of subset sums of Pn. For n greater than 3, we see that SSn is 6 numbers shy of being the interval [0, Sn], where Sn is the largest subset sum, and these numbers are 1,4,6 and their negatives subtracted from Sn. Letting m=n+1, one sees this by noting SSm= SSn union the shifted set p_m + SSn. (One also needs p_m less than S_n - 6, but that is easily established.)

Now the question can be answered by noting there is a subset sum equaling floor of (Sn)/2, and setting the sign of those numbers in that sum to minus.

Added: If a sum is realizable, one can use a tempered greedy algorithm which subtracts the largest available prime from a running total as long as the result is not 1, 4, or 6.

-
One wonders how thin a subset of Pn can be to produce a thick subset of SSn. –  The Masked Avenger Jan 6 at 19:54