Irreducible partitions

[Franklin T. Adams-Watters]

I have been looking recently at what I call irreducible partitions.  A partition c_1 + ... + c_k = n, where the c_i are taken from a set/sequence A, is irreducible (with respect to A) if no subset with more than one term of the c_i's sums to a member of A.

For example, taking A to be the squares, 1 + 4 + 9 = 14 is an irruducible partition of 14, but 1 + 1 + 4 + 4 + 4 is not, because 1 + 4 + 4 = 9 is a square.

Obviously, there are a number of sequences here.  In particular, one can ask how many irreducible partitions of n over A there are.  Focussing on the squares (as I have so far) I get the sequence (for n from 0 to 60):

1,1,1,1,1,1,1,1,1,1,1,1,2,1,1,1,1,2,2,2,2,3,2,2,2,1,2,2,3,2,3,
2,3,3,2,3,1,2,2,2,1,2,3,3,3,2,3,3,5,1,2,3,4,4,4,4,5,6,4,4,5

This is hand calculated; I would appreciate it if someone would check and extend it.  Assuming I haven't made any mistakes, this sequence is not yet in the OEIS.

The thing that intrigues me is the location of the 1's in this sequence.  Obviously, any square (more generally, any member of A) will have a unique irreducible representation.  Otherwise, the values 1 through 15, excluding 12, are the only ones to this point with this property - except for 40.  Can anyone find any more 1's?  Or prove that there aren't any.

The asymptotic behavior of the sequence is also far from clear - except that are infinitely 1's.  Do other values occur infinitely often?  I don't even see any way to prove that the sequence is unbounded, although it certainly seems to be.

By way of contrast, consider the case where A is the powers of some integer m > 1.  In this case, every integer will have a unique irreducible representation, reflecting its representation in base m. (More generally, this applies when each term of A is divisible by the previous one - such as the factorials).

-- 
Franklin T. Adams-Watters
16 W. Michigan Ave.
Palatine, IL 60067
847-776-7645


__________________________________________________________________
Switch to Netscape Internet Service.
As low as $9.95 a month -- Sign up today at http://isp.netscape.com/register

Netscape. Just the Net You Need.

New! Netscape Toolbar for Internet Explorer
Search from anywhere on the Web and block those annoying pop-ups.
Download now at http://channels.netscape.com/ns/search/install.jsp