Partition-related sequence

[franktaw at netscape.net]

 From David Wilson <davidwwilson at comcast.net>:
>What I am looking for is a multiset of integers that can be
>partitioned into k equal-sum multisets for k = 1, 2, 3, ..., n.

OK, I see now what you are trying to do.  Actually, I think my
question is at least equally interesting, but yours is interesting.

For your problem, I get a(6) <= 12, using any of
[2,2,2,3,3,3,4,5,6,10,10,10], [2,2,2,3,3,4,4,5,5,10,10,10],
[1,1,2,2,2,2,5,5,10,10,10,10], or [2,2,3,3,3,3,5,5,7,7,10,10].

Even assuming these values are correct for n = 1..6 is not
enough to determine the sequence, but A002088 is an
intriguing possibility.

There is a systematic way to get a solution for a(n+1) from
a solution for a(n), adding n new values.  Multiply each term
by the appropriate factor to get a sum divisible by the lcm
of the sum used for a(n) (is A003418 always achievable?)
and n+1, look at the groups summing to the total divided
by n.  Split one of the values in each group so that the total
divided by n+1 is achievable.  This is then a solution.

For example, n = 4, the partition is [1,1,2,2,3,3].  Multiplying
by 5 to get a sum of 60, we have parts summing to 15 of
[5,10] [5,10] [15] [15].  Splitting these, we get two parts
of [12,3], and two that are either [10,3,2] or [7,5,3].

This shows that a(n+1) <= a(n) + n.

Actually, when n+1 is composite, we can do better than this.
Let k be any factor of n+1.  Divide the solution for n into k
parts, and subdivide number each part so that it be divided
into (n+1)/k parts; this requires splitting at most (n+1)/k - 1
parts.  This gives us a solution using a(n) + k*((n+1)/k - 1)
= a(n) + n + 1 - k parts.  This is minimized when
k = (n + 1) / lpf(n + 1), where lpf is the least prime factor
function.  So we get, substituting n -> n-1,

a(n) <= a(n-1) + n - n/lpf(n).

Note that this is not always optimal; it gives a(6) <= 13, but
we can achieve a(6) <= 12.  (Or if a(5) < 10, then a(5) is
an exception instead.)  This difference can be explained by
noting that when we split (at least one of the) solutions for
a(5) into 2 parts, one of the parts is [10,10], which needs
no subdivision to split into halves.

I will conjecture that A002088 is in fact the solution to this
problem.

A final note: this problem is equivalent to asking how many
positive fractions are required so that they can divided into
k groups, each summing to 1/k, for every k from 1 to n.

Franklin T. Adams-Watters


________________________________________________________________________
More new features than ever.  Check out the new AIM(R) Mail ! - 
http://webmail.aim.com