[seqfan] Re: Pieces of cake sequence A265286 and a question

[Max Alekseyev]

Allan, thank you for sharing this clever trick!
I'm not sure though if it can practically help here as finding even a
single solution takes much time already for n=6,7. And I don't remember if
I ever got solution for n=8 with the MILP approach.
Going for all solutions one-by-one will multiply the running time
significantly (also there will be many solutions differing just in the
order of pieces, which we don't really want to distinguish).
Anyway, I can probably run this approach for n=5 and see what all the
solutions look like.
Regards,
Max


On Fri, Jan 22, 2016 at 7:33 PM, Allan Wechsler <acwacw at gmail.com> wrote:

> Max, you can trick a MILP solver into giving all solutions by using as your
> objective function a weighted sum of all the integer variables, with
> irrational numbers as the weights. (Of course this can only be approximated
> in floating point.) One solution optimizes this objective. Set that
> solution aside and add a constraint that requires the objective to be less
> than this optimum, and re-solve. This will give a second-best solution. By
> continually adjusting the new constraint downward, you will list all the
> solutions.
>
> On Fri, Jan 22, 2016 at 7:21 PM, Max Alekseyev <maxale at gmail.com> wrote:
>
> > Neil,
> >
> > Frankly speaking, I do not know how to get all the solutions for a MILP
> > problem. I'm using Sage (powered with Gurobi solver) here and it reports
> > only one solution.
> >
> > Instead, I've tried to minimize the smallest piece in a solution and
> found
> > that 1/120 is the smallest possible piece (in a 9-piece solution) for
> n=5.
> > This does not guarantee though that the denominator cannot go above 120
> > (e.g., this does not eliminate a possibility of a part being, say,
> 7/240).
> > Now it's running for n=6.
> >
> > Regards,
> > Max
> >
> >
> > On Fri, Jan 22, 2016 at 4:38 PM, Neil Sloane <njasloane at gmail.com>
> wrote:
> >
> > > OK, then I will add the question to A265286.
> > >
> > > But your integer programming approach make it possible to find ALL the
> > > solutions for small n,
> > > right, so in principal the question could be answered?
> > >
> > >
> > >
> > > Best regards
> > > Neil
> > >
> > > Neil J. A. Sloane, President, OEIS Foundation.
> > > 11 South Adelaide Avenue, Highland Park, NJ 08904, USA.
> > > Also Visiting Scientist, Math. Dept., Rutgers University, Piscataway,
> NJ.
> > > Phone: 732 828 6098; home page: http://NeilSloane.com
> > > Email: njasloane at gmail.com
> > >
> > >
> > > On Fri, Jan 22, 2016 at 4:34 PM, Max Alekseyev <maxale at gmail.com>
> wrote:
> > >
> > > > Neil,
> > > > I'm sorry I misread your question. I do not know the answer and
> believe
> > > > your question is a hard one, provided that we don't even know how to
> > > > compute A265286 efficiently.
> > > > Regards,
> > > > Max
> > > >
> > > > On Fri, Jan 22, 2016 at 4:31 PM, Max Alekseyev <maxale at gmail.com>
> > wrote:
> > > >
> > > > > Hi Neil,
> > > > > The second example in A265286 negatively answers your question.
> > > > > Regards,
> > > > > Max
> > > > >
> > > > > On Fri, Jan 22, 2016 at 3:45 PM, Neil Sloane <njasloane at gmail.com>
> > > > wrote:
> > > > >
> > > > >> Rainer R. mentioned Max Alekseyev's lovely sequence A265286.
> > > > >>
> > > > >> Given n, look for the smallest set of fractions {f_1, f_2, ...,
> f_M}
> > > in
> > > > >> the
> > > > >> range 0 to 1 such that for each k with 1 <= k <= n, we can
> partition
> > > the
> > > > >> f_i into k groups whose sums are equal. For n=5 the minimal M is
> 9,
> > > and
> > > > a
> > > > >> solution is
> > > > >> {1/60, 1/30, 1/20, 1/12, 7/60, 2/15, 1/6, 1/5, 1/5}
> > > > >>
> > > > >> OK, now look at all the solutions for a given value of n,
> > > > >> with M (the minimal value) parts. Now ask, what is the minimal
> > > > >> denominator?
> > > > >>
> > > > >> Is it always A003418(n) = LCM{1,2,...,n}?
> > > > >>
> > > > >> If not, we get a new sequence: given n, first minimize the number
> of
> > > > >> parts,
> > > > >> then minimize the biggest denominator
> > > > >>
> > > > >> Max, do you know the answer?
> > > > >>
> > > > >> _______________________________________________
> > > > >>
> > > > >> Seqfan Mailing list - http://list.seqfan.eu/
> > > > >>
> > > > >
> > > > >
> > > >
> > > > _______________________________________________
> > > >
> > > > Seqfan Mailing list - http://list.seqfan.eu/
> > > >
> > >
> > > _______________________________________________
> > >
> > > Seqfan Mailing list - http://list.seqfan.eu/
> > >
> >
> > _______________________________________________
> >
> > Seqfan Mailing list - http://list.seqfan.eu/
> >
>
> _______________________________________________
>
> Seqfan Mailing list - http://list.seqfan.eu/
>