A342136 Number of partitions of [2n] into pairs whose sums and differences are primes.

1, 0, 0, 0, 1, 2, 6, 10, 22, 101, 66, 504, 2088, 3572, 14398, 49984, 108030, 191228, 1087758, 5005440, 14081453, 97492234, 160186634, 939652634, 3926077642, 4273706733, 41832174879, 214185383046, 494248121522, 6153003414039, 38125026176659, 13635112709648, 39350572537836, 511502485322923, 1069875349612147, 5075263842958032

Offset

0,6

Links

Table of n, a(n) for n=0..35.

Wikipedia, Partition of a set

Formula

The graph on vertices [2n] and edges connecting pairs with prime sum and difference is bipartite (with odd numbers in one part and even numbers in the other). Hence, a(n) as the number of perfect matchings in this graph is given by the permanent of its reduced adjacency matrix (see PARI code). - Max Alekseyev, Sep 30 2025

Example

a(4) = 1: {{1,6}, {2,5}, {3,8}, {4,7}}.
a(5) = 2: {{1,6}, {2,9}, {3,10}, {4,7}, {5,8}}, {{1,6}, {2,5}, {3,8}, {4,9}, {7,10}}.

Maple

b:= proc(s) option remember; `if`(s={}, 1, (j-> add(`if`(i<j and
      andmap(isprime, [j+i, j-i]), b(s minus {i, j}), 0), i=s))(max(s)))
    end:
a:= n-> b({$1..2*n}):
seq(a(n), n=0..15);

Mathematica

b[s_] := b[s] = If[s == {}, 1, With[{j = Max[s]}, Sum[If[i < j && AllTrue[{j+i, j-i}, PrimeQ], b[s ~Complement~ {i, j}], 0], {i, s}]]];
a[n_] := b[Range[2n]];
a /@ Range[0, 15] (* Jean-François Alcover, Aug 25 2021, after Alois P. Heinz *)

Prog

(PARI) a342136(n) = matpermanent( matrix(n, n, i, j, isprime(2*i-1+2*j) && isprime(abs(2*i-1-2*j))) ); \\ Max Alekseyev, Sep 30 2025

Crossrefs

Cf. A000341, A009692, A342139, A342155.

Sequence in context: A125527 A376287 A200572 * A049750 A295139 A134016

Adjacent sequences: A342133 A342134 A342135 * A342137 A342138 A342139

Keyword

nonn

Author

Alois P. Heinz, Mar 01 2021

Extensions

a(25)-a(35) from Bert Dobbelaere, Mar 06 2021

Status

approved