Irreducible partitions

[David Wasserman]

You might add that there can't be any zeros in the sequence, because you can always get an irreducible partition of n as follows:
take c_1 to be the largest square <= n, then c_2 is the largest square <= n - c_1, etc.  More generally, this greedy algorithm works for any A that contains 1.
For A = the primes, the only zero is at n = 1.  The greedy algorithm doesn't work, but if p is a prime factor of n, then you can repeat p n/p times.  The first irreducible partitions not of this form are
8 = 5+3
9 = 7+2
10 = 7+3
12 = 7+5
14 = 11+3
15 = 13+2
15 = 7+5+3
16 = 13+3
16 = 11+5
There is a slight modification of the greedy algorithm that works in this case: if n is not prime, take c_1 to be the largest prime < n - 1; repeat until you are left with a prime.

It's a very interesting concept; too bad I don't have any more time to play with it.

 - David