Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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 to two non-overlapping sublists , each sublist has equal sum Total[P[n]]/2;When n=2k is even, prime list P[n] can be partitioned to 2 non-overlapping sublists , one sublist's sum is (Total[P[n]]-1)/2, the other's is (Total[P[n]]+1)/2.

For example:

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

......

How to write an efficient program to check it? any clue to prove or disprove this conjecture? BTW:I asked this question at mathgroup before, but I didn't describe it clearly.

share|improve this question
1  
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
add comment

2 Answers

up vote 2 down vote accepted

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.

share|improve this answer
    
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
add comment

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)

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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