A077564 Number of partitions of n into parts with distinct prime signatures.

1, 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

Offset: 0

Author

Amarnath Murthy, Nov 11 2002

Keywords

• nonn

Comments

The 'prime signature' of n is the sorted list of exponents in the prime factorization of n.

Examples

			a(7) = 4. The partitions are 7, 6+1, 4+3, 4+2+1. (5+2, 3+2+2, ... are not counted.)
		

Links

• Sean A. Irvine, Table of n, a(n) for n = 0..200

Crossrefs

Cf. A077563.

Programs

Mathematica

sig[n_] := Sort[Last/@FactorInteger[n]]; f[n_, m_] := Module[{sm}, If[n>m(m+1)/2||n<0, Return[{}]]; If[n==0, Return[{{}}]]; sm=sig[m]; f[n, m]=Union[f[n, m-1], Prepend[ #, m]&/@Select[f[n-m, m-1], !MemberQ[sig/@#, sm]&]]]; a[n_] := Length[f[n, n]] (* f[n, m] is list of partitions of n into parts <= m with distinct prime signatures *)

Extensions

Edited by Dean Hickerson, Nov 11 2002