Prime pairs?

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

i think try to diagram the math problem it might help.Partitions are the number of ways a number can be added up

This is a famous problem, risen to the status of conjecture. All attempts to mathematically prove it have come up empty.

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.

There's a proof here that uses a high-powered theorem, so it's not particularly satisfying. http://mathhelpforum.com/number-theory/119181-part...

Can anyone give a simpler proof?

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

---my original reply

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.

--end of my original reply.

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.