2
$\begingroup$

For any even number N, partition the integers from 1 to N into pairs such that the sum of the two numbers in each pair is a prime number.

$\endgroup$
4
$\begingroup$

Starting from the top, find the first pair $(N,N-k)$ with $k$ the least odd number for which the sum $2N-k$ is a prime. That takes care of pairs $(N,N-k),(N-1,N-k+1),\cdots$ and you are left with the numbers from $1$ to the even number $N-k-1$ which you can assume are doable by induction.

--> Actually any odd $k$ for which the sum of the pair $(N,N-k)$, i.e. $2N-k$, is prime will do for a starting block $(N,N-k),(N-1,N-k+1)$ for the partition, and choosing the largest such $k$ makes for the fewest "iterations" needed to make the partition.

$\endgroup$

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.