A009692 Number of partitions of {1, 2, ..., 2n} into pairs whose differences are primes.

1, 0, 1, 3, 10, 40, 153, 921, 5144, 30717, 230748, 1766056, 14052445, 116580521, 897876519, 7657321097, 75743979608, 788733735080, 7569825650083, 75242386295617, 831978453306391, 9444103049405370, 120064355466770831, 1579842230380587833

Offset

0,4

Links

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

Example

a(3) = 3: {{1,6}, {2,4}, {3,5}}, {{1,4}, {2,5}, {3,6}}, {{1,3}, {2,5}, {4,6}}. - Alois P. Heinz, Nov 15 2016

Maple

b:= proc(s) option remember; `if`(s={}, 1, (j-> add(`if`(i<j
      and isprime(j-i), b(s minus {i, j}), 0), i=s))(max(s)))
    end:
a:= n-> b({$1..2*n}):
seq(a(n), n=0..12);  # Alois P. Heinz, Nov 15 2016

Mathematica

b[s_] := b[s] = If[s == {}, 1, Function[j, Sum[If[i < j && PrimeQ[j - i], b[s ~Complement~ {i, j}], 0], {i, s}]][Max[s]]];
a[n_] := b[Range[2n]];
Table[Print[n, " ", a[n]]; a[n], {n, 0, 18}] (* Jean-François Alcover, Mar 01 2021, after Alois P. Heinz *)

Crossrefs

Cf. A000341.

Sequence in context: A099763 A318118 A149052 * A149053 A149054 A149055

Adjacent sequences: A009689 A009690 A009691 * A009693 A009694 A009695

Keyword

nonn,hard

Author

David W. Wilson

Extensions

a(0), a(14)-a(18) from Alois P. Heinz, Nov 15 2016

a(19)-a(23) from Bert Dobbelaere, Feb 20 2020

Status

approved