A393671 a(n) = number of partitions of n into distinct prime parts, no two of which are adjacent primes.

1, 0, 1, 1, 0, 1, 0, 2, 0, 1, 1, 1, 0, 2, 1, 1, 2, 1, 2, 2, 3, 1, 3, 2, 3, 1, 4, 1, 3, 2, 4, 3, 4, 4, 4, 3, 5, 4, 4, 6, 4, 5, 6, 6, 6, 6, 6, 8, 7, 7, 10, 9, 6, 11, 9, 10, 10, 13, 8, 13, 11, 17, 10, 18, 14, 13, 17, 18, 14, 19, 17, 19, 18, 24, 21, 20, 23, 24, 22

Offset

0,8

Links

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

Example

a(24) counts these 3 partitions of 24: 19+5 = 17+7 = 17+5+2.

Maple

b:= proc(n, i) option remember; `if`(n=0, 1, `if`(i<1, 0,
      b(n, i-1)+`if`(ithprime(i)>n, 0, b(n-ithprime(i), i-2))))
    end:
a:= n-> b(n, numtheory[pi](n)):
seq(a(n), n=0..100);  # Alois P. Heinz, Mar 03 2026

Mathematica

prt[n_, sL_] := Module[{m = Length[sL], f}, If[n > Last[sL], Return["Extend sL"]];
f[i_, r_, b_] := f[i, r, b] = Which[r == 0, {{}}, r < 0 || i == 0, {}, True,
Join[f[i - 1, r, False], If[! b && s[[i]] <= r, Map[Prepend[#, sL[[i]]] &,
f[i - 1, r - sL[[i]], True]], {}]]]; Reverse[f[m, n, False]]]
z = 100;
s = Array[Prime, z];
m = Map[{#, prt[#, s]} &, Range[z]]
u = Map[Last, m];
Map[Length, u]
(* Peter J. C. Moses, Jan 26 2026 *)

Crossrefs

Cf. A000040, A000586, A393672, A393673, A393674, A393675, A393676.

Sequence in context: A205745 A333781 A243223 * A034178 A317531 A074169

Adjacent sequences: A393668 A393669 A393670 * A393672 A393673 A393674

Keyword

nonn

Author

Clark Kimberling, Mar 01 2026

Status

approved