A088044 Number of partitions of n with distinct prime signatures.

1, 1, 2, 2, 2, 3, 4, 4, 5, 6, 8, 10, 10, 11, 14, 14, 19, 22, 22, 25, 30, 34, 38, 40, 46, 54, 60, 63, 74, 81, 85, 91, 108, 118, 126, 134, 153, 173, 180, 186, 214, 236, 245, 262, 301, 326, 338, 355, 395, 437, 461, 476, 540, 592, 610, 649, 717, 768, 811, 853, 943, 1039, 1078

Offset

1,3

Comments

Essentially the same as A077564. [From R. J. Mathar, Sep 11 2008]

Links

Table of n, a(n) for n=1..63.

Example

a(9) = 6 and the partitions are (9), (1,8), (3,6),(4,5), (1,2,6),(2,3,4).
The partitions (2,7), (1,3,5),(1,4,4), etc. are not considered for the count as 2 and 7 both are prime and so on.

Prog

(PARI) ps(n) = local(f); f = factor(n); vecsort(f[, 2]);
b(n, lim, used, cUsed) = local(s, v, found, j, used2); if (n == 0, return(1)); if (n > lim*(lim + 1)/2, return(0)); s = 0; for (i = 1, lim, v = ps(i); found = 0; j = 1; while (!found && j <= cUsed, if (v == used[j], found = 1, j++)); if (!found, used2 = used; used2[1 + cUsed] = v; s += b(n - i, min (n - i, i - 1), used2, cUsed + 1))); s;
a(n) = b(n, n, vector(12), 0); \\ David Wasserman, Jun 21 2005

Crossrefs

Cf. A088045.

Sequence in context: A104410 A018048 A077564 * A351908 A029051 A338826

Adjacent sequences: A088041 A088042 A088043 * A088045 A088046 A088047

Keyword

nonn

Author

Amarnath Murthy, Sep 20 2003

Extensions

More terms from David Wasserman, Jun 21 2005

Status

approved