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.

Improve this question
$\endgroup$
5
  • 2
    $\begingroup$ See OEIS sequence A000341. However, asymptotics are not given there. $\endgroup$
    – Robert Israel
    Commented Jul 19, 2016 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
    Commented Jul 19, 2016 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
    Commented Jul 20, 2016 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
    Commented Jul 20, 2016 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
    Commented Jul 25, 2016 at 14:57

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
1
  • 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
    Commented Jul 20, 2016 at 18:00

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .