I am finding this discussion confusing. Aren't we agreed that the sequence I called f(n) is the one called A265286 (as Don Reble pointed out)? Jim On Monday, December 18, 2017, Allan Wechsler <acwacw@gmail.com> wrote:
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
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun