[math-fun] rationals hard to approximate by rationals
Consider a rational number (in reduced form) X=A/B. Suppose I tell you B, and I ask you to "find A such that X has only 1s and 2s in its partial fraction expansion." (Even better, "...and with the fewest 2s.") For example if B=2^32. You could by brute force just try all 2^32 possible A (actually only 2^31 if we insist A=odd) computing the continued fraction of each A/B, Is there a faster method? How fast can you get? For which (if any) B's is the problem unsolvable? -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)
Is not B=6 unsolvable? The only reduced rationals with denominator 6 are 1/6 and 5/6. 1/6 has continued fraction 0;6. 5/6 has 0;1,5. Both have terms that exceed 2. Have I misunderstood the question? If I have understood correctly, then 9 and 14 are also unachievable. I have an algorithm for listing these, but I haven't implemented it. I'll go into it in more detail if Warren confirms that I have understood the problem correctly. On Wed, Sep 11, 2013 at 9:14 PM, Warren D Smith <warren.wds@gmail.com>wrote:
Consider a rational number (in reduced form) X=A/B.
Suppose I tell you B, and I ask you to "find A such that X has only 1s and 2s in its partial fraction expansion." (Even better, "...and with the fewest 2s.")
For example if B=2^32. You could by brute force just try all 2^32 possible A (actually only 2^31 if we insist A=odd) computing the continued fraction of each A/B,
Is there a faster method? How fast can you get? For which (if any) B's is the problem unsolvable?
-- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
If I understand the problem correctly there are many unsolvable B: 4, 6, 9, 10, 14, 15, 16, 20, 22, 23, 24, 25, 28, 32, 33, 35, 36, 37, 38, .... Up to 10,000 it looks like less than half are solvable. Charles Greathouse Analyst/Programmer Case Western Reserve University On Thu, Sep 12, 2013 at 10:38 AM, Allan Wechsler <acwacw@gmail.com> wrote:
Is not B=6 unsolvable? The only reduced rationals with denominator 6 are 1/6 and 5/6. 1/6 has continued fraction 0;6. 5/6 has 0;1,5. Both have terms that exceed 2. Have I misunderstood the question?
If I have understood correctly, then 9 and 14 are also unachievable. I have an algorithm for listing these, but I haven't implemented it. I'll go into it in more detail if Warren confirms that I have understood the problem correctly.
On Wed, Sep 11, 2013 at 9:14 PM, Warren D Smith <warren.wds@gmail.com
wrote:
Consider a rational number (in reduced form) X=A/B.
Suppose I tell you B, and I ask you to "find A such that X has only 1s and 2s in its partial fraction expansion." (Even better, "...and with the fewest 2s.")
For example if B=2^32. You could by brute force just try all 2^32 possible A (actually only 2^31 if we insist A=odd) computing the continued fraction of each A/B,
Is there a faster method? How fast can you get? For which (if any) B's is the problem unsolvable?
-- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
My analysis was faulty. Charles is way ahead of me, I think. On Thu, Sep 12, 2013 at 11:00 AM, Charles Greathouse < charles.greathouse@case.edu> wrote:
If I understand the problem correctly there are many unsolvable B: 4, 6, 9, 10, 14, 15, 16, 20, 22, 23, 24, 25, 28, 32, 33, 35, 36, 37, 38, .... Up to 10,000 it looks like less than half are solvable.
Charles Greathouse Analyst/Programmer Case Western Reserve University
On Thu, Sep 12, 2013 at 10:38 AM, Allan Wechsler <acwacw@gmail.com> wrote:
Is not B=6 unsolvable? The only reduced rationals with denominator 6 are 1/6 and 5/6. 1/6 has continued fraction 0;6. 5/6 has 0;1,5. Both have terms that exceed 2. Have I misunderstood the question?
If I have understood correctly, then 9 and 14 are also unachievable. I have an algorithm for listing these, but I haven't implemented it. I'll go into it in more detail if Warren confirms that I have understood the problem correctly.
On Wed, Sep 11, 2013 at 9:14 PM, Warren D Smith <warren.wds@gmail.com
wrote:
Consider a rational number (in reduced form) X=A/B.
Suppose I tell you B, and I ask you to "find A such that X has only 1s and 2s in its partial fraction expansion." (Even better, "...and with the fewest 2s.")
For example if B=2^32. You could by brute force just try all 2^32 possible A (actually only 2^31 if we insist A=odd) computing the continued fraction of each A/B,
Is there a faster method? How fast can you get? For which (if any) B's is the problem unsolvable?
-- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
This is related to the so-called "Zaremba conjecture"; you can find articles about it with that keyword. It is known you can do it when B is a (sufficiently large) power of 2, 3, 5, and 6. The results are due to Niederreiter and others. Jeffrey Shallit On 9/11/13 9:14 PM, Warren D Smith wrote:
Consider a rational number (in reduced form) X=A/B.
Suppose I tell you B, and I ask you to "find A such that X has only 1s and 2s in its partial fraction expansion." (Even better, "...and with the fewest 2s.")
For example if B=2^32. You could by brute force just try all 2^32 possible A (actually only 2^31 if we insist A=odd) computing the continued fraction of each A/B,
Is there a faster method? How fast can you get? For which (if any) B's is the problem unsolvable?
On 9/12/13, Jeffrey Shallit <shallit@uwaterloo.ca> wrote:
This is related to the so-called "Zaremba conjecture"; you can find articles about it with that keyword.
It is known you can do it when B is a (sufficiently large) power of 2, 3, 5, and 6. The results are due to Niederreiter and others.
Jeffrey Shallit
--Oho, there is a largish literature on this. Shallit's tip led to http://arxiv.org/abs/1103.0422 http://arxiv.org/abs/1107.3776 where they claim that asymptotically 100% of integers B>0 have a matching A with 0<A<B, gcd(A,B)=1, such that the continued fraction of A/B has all partial quotients <=2189. It is suspected 2189 could be lowered to 5. Hensley conjectured if B is prime then it could be lowered to 2. Niederreiter 1986 showed for B any power of 2 or power of 3 there exists A such that continued fraction of A/B has all partial quotients <=3 or 4 (I do not have N's paper, this is from other people's conflicting descriptions of it). Harald Niederreiter: Dyadic fractions with small partial quotients, Monatsh. Math.,101,4(1986) 309-315. None of the papers I saw gave any substantial amount of computational evidence for anything. -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)
It appears empirically, that if B is any power of 2 exceeding 2^24, then there exist A such that the continued fraction for A/B has only 1s and 2s as partial quotients. The unconvincing speculation that this keeps on working would be based on the empirical fact that the number of A's seems to be noisily increasing as a function of n for B=2^n from n=24 (no solutions) up to n=31 (21 solutions). However, this is rudely interrupted at n=32 (only 5 solutions) and n=33 (zero solutions!!) ----------- Now to explain my "faster than brute force" method for trying to find solutions A (given B) such that A/B has only 1s and 2s in its continued fraction: You initially make a table of all continued fractions [1,2,2,1,1...] of some maximum length L containing only 1s and 2s, and view them as 2x2 matrices. (and we could employ other measures than "maximum length"...) Now we do a "meet in the middle attack." That is, we are going to consider length-2L continued fractions made by gluing two halves from our table together. This multiplies their 2x2 matrices. One of the matrix entries has to equal B to yield a solution. The crude way would simply consider all possible matrix-pairs in time quadratic in the size of our table. The better idea is to consider all matrix-pairs from our table, only considering the ones which can yield our desired B (and saving immense time by not considering other matrix-pairs which have no chance to work). This can be done using "computational geometry." Namely, given matrix1, the suitable matrix2 such that matrix1*matrix2 has an entry B, are those such that a certain 2-vector dot product equals B. This corresponds to those such that the two entries X,Y in that dot product, lie on a certain line. So if we preprocess our table -- each table element viewed as an X,Y two-tuple -- to support "fast line queries" using known data structures for computational geometry ("simplex range queries" will do) we can accomplish this a lot faster than brute force, effectively reducing "quadratic" to a smaller power than 2. An interesting meld of computational geometry and number theory, but I have not implemented & tested this.
participants (4)
-
Allan Wechsler -
Charles Greathouse -
Jeffrey Shallit -
Warren D Smith