Partition-related sequence

[franktaw at netscape.net]

I have a beautiful proof that A002088 is an upper bound for this
sequence.

The key is in my final note.

To get a solution for a given n, start with the Farey sequence for n.
(That is, all fractions between 0 and 1 inclusive with denominator
<= n.)  Now look at the differences between adjacent values.
These obviously sum to 1, and equally obviously, can be partitioned
into groups each summing to 1/k for each k from 1 to n: just break
at the fractions j/k for 0 < j < k.  (j/k may not be in lowest terms,
but if not it can be reduced.)

And, quite trivially, the number of fractions added to the Farey
sequence for each n is phi(n).

For example, for n = 7, the Farey sequence is:
0/1 1/7 1/6 1/5 1/4 2/7 1/3 2/5 3/7 1/2 4/7 3/5 2/3 5/7 3/4 4/5
   5/6 6/7 1/1

The differences are:
1/7 1/42 1/30 1/20 1/28 1/21 1/15 1/35 1/14 1/14 1/35 1/15
   1/21 1/28 1/20 1/30 1/42 1/7.

To get back to David's problem, multiply by the lcm of the
denominators, which in this case is 420.  We get
60 10 14 21 15 20 28 12 30 30 12 28 20 15 21 14 10 60
or rearranging:
[10,10,12,12,14,14,15,15,20,20,21,21,28,28,30,30,60,60]

Franklin T. Adams-Watters

 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.

Me:
...

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