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