# Partitioning integers into pairs so that the sum of each pair is prime.

• Dec 7th 2009, 02:56 PM
comssa
Partitioning integers into pairs so that the sum of each pair is prime.
Show that, for every positive integer n, the numbers between 1 and 2n can be partitioned into pairs so that the sum of each pair is a prime number.

I tried a few examples, and I figured that an odd number must be paired up with an even number, which isn't much. You can split the numbers 1 to 2n into {1,3,...2n-1} and {2,4,...,2n}, and then somehow pick one number from each set such that all have prime sums, but I am kind of stuck.
• Dec 7th 2009, 05:54 PM
Black
Prove by induction.

The case \$\displaystyle n=1\$ is trivial.

Suppose that for \$\displaystyle n = 1,2,\dots,m-1\$, the integers \$\displaystyle 1,2,\dots,2n-1,2n \$ can be partitioned in pairs \$\displaystyle (x_1,y_1),(x_2,y_2),\dots,(x_n,y_n)\$ s.t. \$\displaystyle \forall j, x_j+y_j = prime. \$

For \$\displaystyle n=m\$, we have the integers \$\displaystyle 1,2,\dots,2m-1,2m\$. By the Bertrand-Chebyshev theorem \$\displaystyle \exists p=prime \$ s.t. \$\displaystyle 2m<p<4m \Longrightarrow p-2m<2m\$. Therefore we have the following pairs:

\$\displaystyle (p-2m,2m), (p-2m+1,2m-1),\dots, ((p-1)/2,(p+1)/2)\$.

This takes care of the integers \$\displaystyle p-2m\$ to \$\displaystyle 2m\$. For the rest, note that \$\displaystyle p-2m-1\$ is an even number (odd-odd=even) and \$\displaystyle p-2m-1<2m-1 \Longrightarrow p-2m-1 \le 2m-2 = 2(m-1)\$. By the induction hypothesis, we can partition the remaining integers into pairs s.t. the sum of each pair is prime. Q.E.D.