Warren writes: It seems to me the top open problem here is to determine the asymptotic behavior of F(n). It clearly is somewhere between linear and quadratic growth. Theorem: F(n) < 0.2704 * n^2 for all large-enough n. This is due to the inequality F(n) <= F(n-1) + n - LargestDivisor(n). and the fact that the average value of LargestDivisor(n) is C*n where C=0.4593 roughly, and more precisely C = Sum[Product[1-1/Prime[m],{m,1,k}]/Prime[k],{k,1,infinity}]. Here 0.2704 = (1-C)/2 more precisely. I doubt that upper bound is tight. I have a nonrigorous but reasonably convincing "random covering" argument that there exists a constant K>0 such that F(n) < K * (n^2) / log(n) for all sufficiently large n. Subquadratic. It even is plausible that any K>1 works, using natural log; perhaps my argument can be rigorized but at present I have not done that. On Tue, Dec 19, 2017 at 1:01 PM, Allan Wechsler <acwacw@gmail.com> wrote:
Victor, I can't remember if you managed to put a lower bound on the LCM of the denominators. The Russian group discussed this as well, and found some optimal solutions for n=5 that required a common denominator of 120 rather than 60. But n=5 does have some solutions based on 60ths. My intuition is that there will always be optimal solutions based on a common denominator of LCM(1..n). But I can't come close to proving it.
Tom, the Russians give several complete lists of solutions for n=5 and (I think) n=6; it ought to be possible to use them to look for ones that are not refinements of smaller solutions. I am guessing that there are some such, which would answer your question in the negative.
On Tue, Dec 19, 2017 at 11:57 AM, Tom Karzes <karzes@sonic.net> wrote:
Is it necessarily the case that an optimal solution for n+1 can be derived from an optimal solution for n by making additional cuts (i.e., by splitting some of the fractions)?
Another way to ask this is whether an optimal solution for n+1 can be reduced to an optimal solution for n by combining pieces. I.e., can the groupings up to n always be formed with certain pieces from the n+1 solution always occurring in pairs?
Tom
Victor Miller writes:
Allan, Thanks. Why didn't I see that? In any case it's not completely clear to me what the algorithms were to find good solutions for f(n), but here's one:
Do this inductively -- collect a whole bunch of good solutions for f(n), and try to extend them to f(n+1), by a sort of bin packing procedure: have n+1 bin of capacity 1/(n+1) and for each solution for f(n) try to place the pieces in the bins so that you need to make the minimal number of cuts to make them fit exactly. It's not clear, a priori, which of the minimal solutions to f(n) will extend to f(n+1), you need to collect a bunch of them.
On Tue, Dec 19, 2017 at 10:47 AM, Allan Wechsler <acwacw@gmail.com> wrote:
Google translate seems to work fine for the Russian discussion at dxdy.ru. Every once in a while you trip over something (like LCM = NOK).
They seem like a rather jolly, collegial crew over there.
They also wrestled momentarily with the worry that the optimal solution might be irrational, but somebody quickly demonstrated that the problem was equivalent to very big systems of linear equations with rational coefficients, exactly as Victor pointed out here.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun