OEIS has 18 matches for (1,2,4,6,9,11); at the moment I am betting that none of them are "the answer"; if any one of them is in fact the f(n) we have been discussing, it will take nontrivial mathematics to prove it. On Mon, Dec 18, 2017 at 4:29 PM, <rcs@xmission.com> wrote:
We can extend Victor's 11 piece solution for n=6 to a 17-piece solution for n=7.
There's an inequality: F(n) <= F(n-1)+n-1 Arrange all the pieces along the line [0,1] in any order. Make n-1 cuts at k/n for 0<k<n.
I'd like to say F(n) <= F(n-1) + phi(n), but I can only get
F(n) <= F(n-1) + (n - maximum-proper-divisor(n))
I'm allowing 1 as a proper divisor, but not n. To get the inequality: let m = max-prop-div(n). Arrange the pieces in the n-1 solution into size 1/m groups. Place these along the [0,1] line. Then some of the cuts for k/n will overlap all the cuts for the 1/m grouping.
We can say F(n) <= sum(phi(n)). In this case, just make all the cuts for k/j with (k,j)=1 and 0<=k<j<=n. (This is just the Farey series for n, excluding 1/1.) With no rearrangement of the pieces, when we get around to making the cuts for k/n, cuts will already exist for all proper divisors d|n. The sum should be roughly n(n+1)/2 * 6/pi^2. In this solution, the smallest piece is 1/n(n-1). The common denominator for all the pieces is indeed LCM(1...n), very roughly e^n.
Rich
-----------
Quoting Tom Karzes <karzes@sonic.net>:
For what it's worth, here's a naive, almost-certainly-suboptimal 18-part solution for n=7 corresponding to the bound of 18 given by https://oeis.org/A092249
1/42, 1/42, 1/35, 1/35, 1/30, 1/30, 1/28, 1/28, 1/21, 1/21, 1/20, 1/20, 1/15, 1/15, 1/14, 1/14, 1/7, 1/7
Tom
Victor Miller writes:
Tom, Thanks. I'm trying f(7) now, but it looks really hard. I give a tentative upper bound for the number of parts, and let it optimize it. I suspect that the previously conjectured upper bound from A092249 isn't right. Just to see if I could give it a much larger space to explore, I gave it a tentative upper bound of 112 and after a few minutes it hasn't even found any feasible solution! The only thing that it's proved so far is that f(7) >= 12.
Victor
On Mon, Dec 18, 2017 at 2:57 PM, Tom Karzes <karzes@sonic.net> wrote:
Wow, nice job! I was expecting f(5) to be 10. Your 9-part solution beats a simple union of divisions into equal parts!
And your 11-part solution for f(6) also beats a simple union of divisions into equal parts!
Have you tried f(7), or is that past what it can handle?
Tom
Victor Miller writes:
Whoops, in f(6) threre should have been 2 parts of size 7/60: 1/30, 1/30, 1/20, 1/20, 1/12, 1/12, 1/10, 7/60, 7/60, 1/6, 1/6
On Mon, Dec 18, 2017 at 2:22 PM, Victor Miller < victorsmiller@gmail.com
wrote:
I coded the model in cplex (I'll give the slightly corrected version subsequently). It calculated f(5) = 9, parts= 1/60, 1/30, 1/20, 1/12, 1/10, 3/20, 1/6, 1/5, 1/5 and f(6) = 11, parts 1/30, 1/30, 1/20, 1/20, 1/12, 1/12, 1/10, 7/60, 1/6, 1/6
On Sun, Dec 17, 2017 at 5:52 PM, Victor Miller < victorsmiller@gmail.com> wrote:
> Slight correction in my last post. Here is the correct version. > Tomorrow, when I get into work, I'll give the f(5) problem to cplex and > report back. > > Victor > > Solve the following problem -- given a positive integer n > 1, and a > positive integer k decide if there are k reals x[1], ..., x[k] >= 0 > such that, for every integer i > 1, there are y[i,r,j], j=1, ..., k, > r=1,...,i in {0,1} > > 1) sum_{j,r} y[i,r,j] = 1 # exactly one of the y[i,r,j] = 1 for each i > 2) 1/i = sum_j y[i,r,j] * x[j] for r=1, ..., i > 3) x[j] in [0, 1/n] for j=1,..., k > > We can linearize (2) by using big-M: > > z[i,r,j] = y[i,r,j] * x[j]. Then z[i,r,j] in [0, 1/n] > > (1/n) * (1-y[i,r,j]) >= x[j] - z[i,r,j] >= -(1/n) * (1-y[i,r,j]) > > There's lots of symmetries. We can (partially) break them by insisting > that for each i the k vectors (y[i,1,j], ... , y[i,i,j]), j=1,...,k are > lexicographically increasing. > > Also, as remarked before, we don't need to put any conditions for i, for > which a non-trivial multiple is <=n. > > > On Sun, Dec 17, 2017 at 2:40 PM, Victor Miller < victorsmiller@gmail.com> > wrote: > >> More specifically let x[1], ..., x[k] be non-negative variables <= 1, >> and for each i=2, ..., n, let y[i,j] be a 0/1 variable whose value of 1 >> means that x[i] contributes to the j-th 1/i. We then have >> 1/i = sum(j) y[i,j] * x[j]. We also have sum(i) y[i,j] = 1 (or maybe <= >> 1 if you want to omit that piece). You might object that sum(j) y[i,j] * >> x[j] isn't linear. You can fix this by introducting new variables >> z[i,j] = x[j] if y[i,j] = 1 and 0 otherwise. You can enforce this by >> z[i,j] <= (1-y[i,j]) + x[j] and z[i,j] >= x[j] - (1-y[i,j]). So giving >> this to a MIP solver is a finite algorithm for the problem. >> >> On Sun, Dec 17, 2017 at 2:24 PM, Victor Miller < victorsmiller@gmail.com> >> wrote: >> >>> Here's a proof that there are optimal rational solutions: For a >>> putatitve solution to f(n) = k, you can write a mixed integer program which >>> will say whether or not there is such a solution. The only integer >>> variables are 0/1 variables which indicate whether "piece" i contributes to >>> a particular sum producing 1/n. There are only a finite number of settings >>> for these. Once you have done this the remainder is a polytope bounded by >>> half spaces with integer coefficients. So the vertices of the polytope >>> have rational coefficients. An optimal solution must be among these. >>> >>> On Sun, Dec 17, 2017 at 2:01 PM, Tom Karzes < karzes@sonic.net> wrote: >>> >>>> Can you prove that it's safe to ignore irrational solutions? Here's a >>>> (non-optimal) irrational solution for f(3), using 5 component values: >>>> >>>> 1/3 = sqrt(2)/8 + (8 - 3*sqrt(2))/24 >>>> 1/3 = (4 - sqrt(2))/8 + (3*sqrt(2) - 4)/24 >>>> 1/3 = 1/3 >>>> >>>> 1/2 = sqrt(2)/8 + (4 - sqrt(2))/8 >>>> 1/2 = 1/3 + (8 - 3*sqrt(2))/24 + (3*sqrt(2) - 4)/24 >>>> >>>> Can we always do as well (or better) using only rational component >>>> values? >>>> I suspect the answer is yes. >>>> >>>> Note that the example above has the general form: >>>> >>>> 1/3 = a + (1/3 - a) >>>> 1/3 = (1/2 - a) + (a - 1/6) >>>> 1/3 = 1/3 >>>> >>>> 1/2 = a + (1/2 - a) >>>> 1/2 = 1/3 + (1/3 - a) + (a - 1/6) >>>> >>>> This works for any value of "a" that doesn't produce zero or negative >>>> values. In particular, "a" can be given a rational value. Is it the >>>> case that any solution involving irrational values can be decomposed >>>> into something like this, which in turn can be converted into a >>>> rational solution? >>>> >>>> Tom >>>> >>>> >>>> Allan Wechsler writes: >>>> > I was challenging myself to try to think of any finite algorithm, >>>> be it >>>> > ever so expensive and cumbersome, that would settle the question of >>>> whether >>>> > p pieces suffices for a given n. A useful lemma would be that if it >>>> can be >>>> > done in p pieces, then it can be done with pieces whose >>>> denominaters divide >>>> > n!. (LCM(1,...,n) would be even stronger, but for my purposes it >>>> doesn't >>>> > matter how weak this lemma is.) >>>> > >>>> > Then, we could say, "Iterate over all partitions of n! into p >>>> parts, and >>>> > for each such partition, check to see if it works, using the >>>> partition as >>>> > the numerators of fractions whose denominators are all n!." This >>>> would be >>>> > heinously expensive but it would at least provide an upper bound on >>>> how >>>> > much computational work we have to do. >>>> > >>>> > But I can't even prove the lemma. >>>> > >>>>
_______________________________________________ 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
--
_______________________________________________ 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