A306443 Number of ways of partitioning the set of the first n primes into two subsets whose sums differ at most by 1.

1, 0, 1, 1, 1, 1, 3, 2, 6, 5, 16, 13, 45, 39, 138, 122, 439, 392, 1417, 1286, 4698, 4341, 16021, 14860, 55146, 51085, 190274, 178402, 671224, 634511, 2404289, 2260918, 8535117, 8067237, 30635869, 29031202, 110496946, 105250449, 401422210, 383579285, 1467402238

Offset

0,7

Links

Alois P. Heinz, Table of n, a(n) for n = 0..2000

Wikipedia, Partition problem

Example

a(8) = 6: 2,17,19/3,5,7,11,13; 3,5,11,19/2,7,13,17; 3,5,13,17/2,7,11,19; 3,7,11,17/2,5,13,19; 2,3,5,11,17/7,13,19; 2,5,7,11,13/3,17,19.
a(9) = 5: 2,3,5,17,23/7,11,13,19; 2,5,7,13,23/3,11,17,19; 2,5,7,17,19/3,11,13,23; 2,5,11,13,19/3,7,17,23; 2,7,11,13,17/3,5,19,23.

Maple

s:= proc(n) s(n):= `if`(n=0, 1, ithprime(n)+s(n-1)) end:
b:= proc(n, i) option remember; `if`(i=0, `if`(n<=1, 1, 0),
     `if`(n>s(i), 0, (p->b(n+p, i-1)+b(abs(n-p), i-1))(ithprime(i))))
    end:
a:= n-> ceil(b(0, n)/2):
seq(a(n), n=0..45);

Mathematica

s[n_] := s[n] = If[n == 0, 1, Prime[n] + s[n - 1]];
b[n_, i_] := b[n, i] = If[i==0, If[n <= 1, 1, 0], If[n > s[i], 0, Function[ p, b[n + p, i - 1] + b[Abs[n - p], i - 1]][Prime[i]]]];
a[n_] := Ceiling[b[0, n]/2];
a /@ Range[0, 45] (* Jean-François Alcover, Apr 30 2020, after Alois P. Heinz *)

Crossrefs

Bisections give: A022894 (odd part), A113040 (even part).

Cf. A000040, A069918, A307877.

Sequence in context: A371906 A293549 A370377 * A336518 A189073 A107271

Adjacent sequences: A306440 A306441 A306442 * A306444 A306445 A306446

Keyword

nonn

Author

Alois P. Heinz, May 31 2019

Status

approved