# Asymptotics on the number of ways to pair off $\{1, 2, \dots, 2n\}$ into primes

Given $S = \{1, 2, \dots, 2n\}$, we can always pair off elements into $n$ pairs such that each sum to a prime. The proof of this fact is easy and follows from Bertrand's postulate.

Now, let $\gamma(n)$ be the number of different ways to pair off the set $S$ into $n$ pairs that sum to primes. What is known of the asymptotics of this function?

From computer simulations, the first couple values are $1, 2, 3, 6, 26, 96, 210, 1106, 3759, 12577, 74072, 423884$ so it seems to grow fairly quickly.

• See OEIS sequence A000341. However, asymptotics are not given there. – Robert Israel Jul 19 '16 at 18:30
• This observation is nice enough that I will partly spoil it: Use Bertrand to show that there is a prime p between 2n and 4n, and use that for one of the sums. The rest of the proof suggests a partial enumeration: say such a pairing is intervallic if the pairs that form the same sum q are an interval for any q. You might get a good asymptotic on the number of intervallic pairings. Gerhard "If Goldbach Were Easy" Paseman, 2016.07.19. – Gerhard Paseman Jul 19 '16 at 18:59
• Perhaps an useful upper bound could be obtained by using the formulation as permanent together with the Bregman–Minc inequality. (Together with a useful estimate of the row sums from the prime number theorem). At least this should give something better than the trivial upper bound of $n!$. – Moritz Firsching Jul 20 '16 at 10:40
• One can note that for each odd number, there are something like $C\pi(2n)$ possible choices of even number to pair with it, where $C$ is some constant not much bigger than 1 (and probably less). Even for $C=2$ this gives an improvement ($(C\pi(n))^n$) on $n!$ for $n$ not too big. Gerhard "Can't Prove C Is Small" Paseman, 2016.07.20. – Gerhard Paseman Jul 20 '16 at 15:03
• If n = 12, then {(1,4), (2,5), (3,8), (6,7), (9,10), (11,12)} is the last time that such a pairing can be achieved in which pairs sum to distinct primes. – Bernardo Recamán Santos Jul 25 '16 at 14:57

Following up on my comment above, here is a recursion for counting the intervallic pairings. These are maps from the set of $2n$ integers to primes such that if $a$ and $b$ map to prime $q$, then not only does $q=a+b$ (and we assume $a \lt b$), then any number $c \in [a,b]$ also maps to $q$. Counting these maps with $I(2n)$ and declaring $I(0)=1$, we get the handy recursion (using prime values only for $q$)
$$I(2n) = \sum_{2n \lt q \lt 4n} I(q-(2n+1))$$
This should be good enough to give an exponential in $n$ lower bound, and might be tweaked to include some more pairings for a better lower bound.