A237125 Number of partitions of n such that no part is a prime divisor of n.

1, 1, 1, 2, 3, 6, 4, 14, 11, 19, 16, 55, 20, 100, 50, 72, 96, 296, 79, 489, 167, 328, 349, 1254, 271, 1331, 816, 1435, 980, 4564, 506, 6841, 2745, 4027, 3840, 6816, 2366, 21636, 7845, 12027, 6583, 44582, 4293, 63260, 18700, 20259, 29920, 124753, 15842, 120351

Offset

0,4

Comments

If n is prime, a(n) = A000041(n) - 1.

Links

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

Example

With n = 6, the prime divisors of 6 are 2 and 3, and the partitions of 6 that do not contain either 2 or 3 are: [6], [5,1], [4,1,1] and [1,1,1,1,1,1], so a(6) = 4.

Maple

with(numtheory): with(combinat):
a:= proc(n) local b, s; s:= factorset(n);
      b:= proc(n, i) option remember;
            `if`(n=0, 1, `if`(i<1, 0, b(n, i-1)+
            `if`(i>n or i in s, 0, b(n-i, i))))
          end;
      `if`(isprime(n), numbpart(n)-1, b(n$2))
    end:
seq(a(n), n=0..50);  # Alois P. Heinz, Feb 04 2014

Mathematica

a[1]=1; a[n_] := If[PrimeQ[n], PartitionsP[n] - 1, Block[{p = First /@ FactorInteger@n}, Length@ Select[ IntegerPartitions[n], Intersection[#, p] == {} &]]]; Array[a, 50] (* Giovanni Resta, Feb 04 2014 *)
a[0] = a[1] = 1; a[n_] := Module[{b, s}, s = FactorInteger[n][[All, 1]]; b[m_, i_] := b[m, i] = If[m == 0, 1, If[i<1, 0, b[m, i-1]+ If[i>m || MemberQ[s, i], 0, b[m-i, i]]]]; If[PrimeQ[n], PartitionsP[n]-1, b[n, n] ]]; Table[a[n], {n, 0, 50}] (* Jean-François Alcover, Nov 11 2015, after Alois P. Heinz *)

Crossrefs

Cf. A236937, A236938.

Sequence in context: A346928 A245712 A285331 * A227296 A318846 A231263

Adjacent sequences: A237122 A237123 A237124 * A237126 A237127 A237128

Keyword

nonn,look

Author

J. Stauduhar, Feb 03 2014

Extensions

a(8)-a(49) from Giovanni Resta, Feb 04 2014

Status

approved