4
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ See OEIS sequence A000341. However, asymptotics are not given there. $\endgroup$ – Robert Israel Jul 19 '16 at 18:30
  • $\begingroup$ 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. $\endgroup$ – Gerhard Paseman Jul 19 '16 at 18:59
  • $\begingroup$ 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!$. $\endgroup$ – Moritz Firsching Jul 20 '16 at 10:40
  • 1
    $\begingroup$ 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. $\endgroup$ – Gerhard Paseman Jul 20 '16 at 15:03
  • $\begingroup$ 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. $\endgroup$ – Bernardo Recamán Santos Jul 25 '16 at 14:57
1
$\begingroup$

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.

Gerhard "Takes The Easy Way Out" Paseman, 2016.07.19.

$\endgroup$
  • 1
    $\begingroup$ Interestingly, I(2n) is not monotonic increasing. For the first few n I get for I(2n) the values 1 1 2 3 8 14 6 25 25 37 75 144 79 194 320 329 598 1176 1245 2054 3949 2226 5738. Although I still think exponential growth can be proven, it seems much less clear now. Gerhard "The Road Seems More Bumpy" Paseman, 2016.07.20. $\endgroup$ – Gerhard Paseman Jul 20 '16 at 18:00

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.