Science & Mathematics » Mathematics » Prime pairs?

# Prime pairs?

Prove that the set { 1, 2, ..., 2k} can be partitioned into k distinct pairs {a_i, b_i} such that for each i, ( a_i + b_i) is prime

• It cant be proven, since it is false. [Oups, see below, the op statement may be true].

Hint: prime counting function π(n)

Eg: Let k = 100. Your set is thus 1,2,..., 200.
You want to partition this into 100 pairs {a_i, b_i}, such as their sum is prime.

The sum of a pair has a minimum of 3 and a max that can be 101 to 399.
But π(399) = 78. IOW, there are only 78 primes from 1 to 399. (There are less than that from 1 to 101).
But you need 100 of them, thus impossible. QED.

BUT.... I see now...Above I assumed that the a_i + b_i gives distinct (prime) values. You did not require that.
Again, for k=100, we can chose many pairs such that their sum is 199 say: {1,198}, {2,197}...{99,100}.
This has a max of 99 pairs. In fact, you always have less than k pairs; you have at maximum k-1 pairs. Hence impossible. BUT if you consider the possibilities of pairs such as {2,197} and {2, 3} in the same set, then you can trivially generate more pairs, hence possible. And if the a+b is allowed be be greater than 2k (that is not excluded in the op, hence is permitted), then by the theorem m<p<2m, just chose that p as to generate your pairs, as other replies have pointed out.
1
2
• There's a proof here that uses a high-powered theorem, so it's not particularly satisfying. http://mathhelpforum.com/number-theory/1...

Can anyone give a simpler proof?
2
0
• I agree with rotchm.
Take k = 60.
There are 60/2 = 30 pairs, so we need 30 primes less than 2x60 = 120. And we cannot use 2 because no pair of numbers 1 to 60 add to 2.
The 30th prime number, excluding 2, is 127.
Not possible when k = 60, so not true.
0
3
• This is a famous problem, risen to the status of conjecture. All attempts to mathematically prove it have come up empty.
0
5
• i think try to diagram the math problem it might help.Partitions are the number of ways a number can be added up
0
2
• The proof is by induction on n.

For n = 1 the result is trivial.
{1+2} = 3

For n > 1, let p be a prime satisfying 2n < p < 4n. Since 4n is not prime we have p = 2n + m for 1 ≤ m < 2k. Pair 2n with m, 2n−1 with m+1, and continue up to n+⌈k⌉ with n+⌊k⌋ (this last is a valid pair since m is odd).

This deals with all of the numbers in {m, m+1, …, 2n}; the inductive hypothesis deals with {1, 2, …, m−1} (again since m is odd).
4
0