Denote $P[n]$ as the prime sequence $\{p_1,p_2,\cdots,p_n\}$.


  • 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.

  • 1
    $\begingroup$ 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. $\endgroup$ – S. Carnahan Aug 5 '10 at 5:11
  • $\begingroup$ 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. $\endgroup$ – Mariano Suárez-Álvarez Aug 5 '10 at 5:11
  • $\begingroup$ @Scott, I think that when you start with the first 11 primes that greedy algorithm does not work. $\endgroup$ – Mariano Suárez-Álvarez Aug 5 '10 at 5:48
  • $\begingroup$ 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 $\endgroup$ – user8140 Aug 5 '10 at 6:57
  • $\begingroup$ 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. $\endgroup$ – 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.

  • $\begingroup$ 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 $\endgroup$ – user8140 Aug 15 '10 at 11:47
  • $\begingroup$ 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.$' $\endgroup$ – 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.

(Link: http://en.wikipedia.org/wiki/Subset_sum_problem#Pseudo-polynomial_time_dynamic_programming_solution)

  • $\begingroup$ 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. $\endgroup$ – user8140 Aug 5 '10 at 7:10
  • $\begingroup$ @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). $\endgroup$ – 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.

  • $\begingroup$ One wonders how thin a subset of Pn can be to produce a thick subset of SSn. $\endgroup$ – The Masked Avenger Jan 6 '15 at 19:54

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.