Partition-related sequence

[David Wilson]

Not to disparage your proof, but it seemed obvious to me that A002088(n) was 
an upper bound on my problem solution. If you take a rod and add cuts that 
break it into first 1, then 2, then 3, up to n equal pieces, you end up with 
A002088(n) pieces. We have now both arrived at the crucial question as to 
whether it is possible to do better.

----- Original Message ----- 
From: <franktaw at netscape.net>
To: <seqfan at ext.jussieu.fr>
Sent: Saturday, January 19, 2008 12:17 AM
Subject: Re: Partition-related sequence


>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
>
>
> -- 
> No virus found in this incoming message.
> Checked by AVG Free Edition. Version: 7.5.516 / Virus Database: 
> 269.19.6/1231 - Release Date: 1/18/2008 11:55 AM
>