A209402 Number of partitions of n into distinct primes except the prime factors of n.

1, 0, 0, 0, 0, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 2, 1, 2, 2, 2, 1, 2, 4, 3, 2, 3, 1, 2, 6, 3, 8, 4, 2, 5, 3, 5, 10, 4, 3, 5, 13, 4, 14, 7, 4, 7, 18, 9, 12, 9, 6, 9, 25, 11, 10, 10, 9, 14, 34, 10, 38, 16, 11, 24, 14, 13, 49, 20, 18, 12, 60, 25, 66, 31, 17, 28

Offset: 0

Author

Alois P. Heinz, Mar 22 2012

Keywords

• nonn
• look

Comments

a(n) = 0 for n in {1, 2, 3, 4, 6, 11}, a(n) = 1 for n in {0, 5, 7, 8, 9, 10, 12, 13, 14, 15, 17, 21, 27}, a(n) = 2 for n in {16, 18, 19, 20, 22, 25, 28, 33}, a(n) = 3 for n in {24, 26, 30, 35, 39}, a(n) = 4 for n in {23, 32, 38, 42, 45}. The smallest n such that a(n) = 0, 1, 2, ... is 1, 0, 16, 24, 23, 34, 29, 44, 31, 48, 37, 54, 49, 41, 43, ... . Missing values are in {15, 19, 21, 22, 26, 33, 35, 36, 37, 39, 42, ... }.

Examples

			a(5) = 1: [2,3].
a(7) = 1: [2,5].
a(16) = 2: [3,13], [5,11].
a(23) = 4: [3,7,13], [2,3,5,13], [5,7,11], [2,3,7,11].
a(24) = 3: [5,19], [7,17], [11,13].
a(29) = 6: [3,7,19], [2,3,5,19], [5,7,17], [2,3,7,17], [5,11,13], [2,3,11,13].
a(34) = 5: [3,31], [5,29], [11,23], [3,5,7,19], [3,7,11,13].
		

Links

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

Crossrefs

Cf. A000586, A208614.

Programs

Maple

with(numtheory):
a:= proc(n) option remember; local b, l, f;
      b:= proc(h, j) option remember;
            `if`(h=0, 1, `if`(j<1, 0,
            `if`(l[j]>h, 0, b(h-l[j], j-1)) +b(h, j-1)))
          end; forget(b);
      f:= factorset(n);
      l:= sort([({ithprime(i)$i=1..pi(n)} minus f)[]]);
      b(n, nops(l))
    end:
seq(a(n), n=0..300);

Mathematica

a[n_] := a[n] = Module[{b, l, f}, b[h_, j_] := b[h, j] = If[h == 0, 1, If[j < 1, 0, If[l[[j]] > h, 0, b[h - l[[j]], j-1]] + b[h, j-1]]]; f = FactorInteger[n][[All, 1]]; l = Sort[Union[Array[Prime, PrimePi[n]] ~Complement~ f]]; b[n, Length[l]]]; Table[a[n], {n, 0, 100}] (* Jean-François Alcover, Mar 27 2017, translated from Maple *)

Formula

a(p) = A000586(p)-1 for any prime p.