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
--