Date: Sat, 12 Oct 1996 17:05:31 -0700 (PDT) From: WAGON@thuban.ac.hmc.edu Subject: Odd Greediness To: eppstein@ics.uci.edu
I am busily updating my Egyptian fraction algorithms for a revision of Mma in Action. I was testing your heuristic for the Odd Greedy, when I discovered 3/179 Odd Greedy doesnot do well on this at all. In fact, I have not completed the representation. So far I am at a term with 55,000 digits. The number of digits is doubleing at each stage. I hesitate to suggest that this might be a counterexample...... stan wagon macalester college (visiting Harvey Mudd for a couple of weeks).
Date: Sun, 13 Oct 1996 12:11:32 -0700 (PDT) From: WAGON@thuban.ac.hmc.edu Subject: an amazing Egyptian fraction To: Klee, Campbell, Guy, Eppstein, Wellin
The number 3/179 has a rather amazing output when the greedy odd Egyptian fraction algorithm is tried out on it. Recall that it is a famous open question whether ODD GREEDY always halts. On 3/179 the algorithm produces 19 terms, the last of which has 439492 digits!!! Takes a little under an hour for my computer to get this. ANd the sequence of numerators of the remainders is somewhat amazing: 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 2, 3, 4, 1 Of course, when I saw the 3,4,5,6...I thought I was on to something....could this continue forever? Well, I don't think so. But I have to say that this puts Eppstein's heuristic, based on the fact that the remainder/numerators might behave like a random walk, in some doubt. Perhaps this is the largest Egyptian fraction ever computed? stan wagon (at Harvey Mudd College for a couple of weeks).
Date: Sat, 19 Oct 1996 18:13:40 -0700 (PDT) To: Milo Gardner <gardnerm@gaia.ecs.csus.edu> From: Kevin Brown <ksbrown@ksbrown.seanet.com> Subject: Re: Is this view interesting?
Hi, Here's something about the 3/179 phenomenon that was probably obvious to you, but that just occured to me. In general if you have a fraction N/D you can generate an expansion N 1 1 1 1 --- = ---- + ---- + ---- + ---- + ... D d[0] d[1] d[2] d[3] that is quadratically convergent (i.e., the number of correct digits roughly doubles with each term) using the recurrence (N+k) d[k+1] = (N+k-1) d[k]^2 - (N+k) d[k] + (N+k+1) with the initial value d[0] = 1 + (D+1)/N. We can re-write this recurrence in the form d[k]^2 - 1 d[k+1] = d[k]^2 - d[k] + 1 - ---------- (1) N+k Of course this doesn't guarantee that the values of d[j] are necessarily integers. To make d[0] an integer we must have D=-1 (mod N). Thereafter on the kth step we must have d[k]^2 - 1 divisible by (N+k), which implies that d[k] = +1 or -1 (mod N+k). Taking the fraction 5/179 as an example, we have N=5 and D=179, which gives d[0] = 37 d[1] = 1105 d[2] = 1045489 d[3] = 956415297493 d[4] = 813093530024486866555885 d[5] = 2975044898554565064901765456700565614513893820093/5 This gives a unit fraction expansion up until the denominator d[5], which is not an integer because d[4] = 4 (mod 9), so it's not congruent to +1 or -1 (mod N+k). As a result, the sequence of remainders is 6, 7, 8, 9, 2,... The numerator of N/D - 1/d[0] - 1/d[1] - 1/d[2] - 1/d[3] - 1/d[4] should be 10, but d[4] happens to be divisible by 5, so the reduced numerator is 2. As a result the recurrence stops giving integers, because it's based on the assumption that the remainders increase by 1 at each step. Of course, we can start the recurrence over again with this new value of N/D. For another example, consider the fraction found by Stan Wagon, 3/179. In this case the recurrence formula (1) gives d[0] = 61 d[1] = 2731 d[2] = 5963959 d[3] = 29640666497443 d[4] = 753059237496518829212535343 d[5] = 496210938281483556785833636950652507016084391058576351 and so on As Stan discovered, recurrence (1) with the initial value d[0]=61 gives integer values for a long time, up to 19 terms. The factorizations of d[k]-1 are somewhat cumulative, as shown below d[0]-1 = (2)(2)(3) (5) d[1]-1 = (2) (3) (5)(7) (13) d[2]-1 = (2) (3)(3) (7)(11)(13)(331) d[3]-1 = (2) (3) (7) (13)(331) (14909897) d[4]-1 = (2) (3) (11)(13)(331)(7505)(77839)(323759)(14909897) d[5]-1 = (d[4]-1)(3)(3)(5)(5)(big composite) If we let f_N(n) denote one less than the index of the first non-integer value given by the recurrence formula (1) with the initial value d[0]=n, then we saw previously that f_5(37) = 4. I've also found that f_3(51)=2. Judging from the remainders quoted by Stan in his email I'd guess that f_3(61)=13. It would be interesting to tabulate f(n) for each value of n up to, say 1000. Of course, this doesn't completly describe an expansion, because once the integers break down you can start over again with the new N/D, as illustrated by the remainders in Stan's example 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 2, 3, 4, 1 |---------------------------------------------------| |--------| |-| Nevertheless, it would be interesting to know the lengths of just the first unbroken sequence for each initial value, to see if 61 is the optimum. I wouldn't be surprised if there are arbitrarily large values of f_3(n). To put it another way, it would be surprising if there was some finite upper limit to f_3(n). A similar survey could be done for f_N(n) for other values of N. This all must be closely related to Sylvester's sequence, defined in Sloane's Handbook of Integer Sequences (M0865) as a(n+1) = a(n)^2 - a(n) + 1 This is the same as formula (1) except it doesn't have the last term involving N. Anyway, I suppose you could estimate the expected value of f_N(n) for any given N and n, because it seems to just be a matter of whether each d[k] is or is not congruent to +-1 (mod N+k). Assuming d[k] is equally likely to be in any of the N+k equivalence classes mod N+k, this gives a probability of 2/(N+k) that the kth step will give an integer. This certainly suggests that small numerators N will give the best chance for long strings. I suppose the probability of j consecutive integers is something like N! ------ 2^j (N+j)! Hmmm...this suggests that Stan's example has a probability of about 1 in 425,675,250. Maybe the assumption of equi-probable equivalence classes is wrong? Regards, Kevin Brown
Date: Sun, 20 Oct 1996 12:35:54 -0700 (PDT) From: Milo Gardner <gardnerm@gaia.ecs.csus.edu> To: David Eppstein <eppstein@ICS.UCI.EDU> Subject: Re: Is this view interesting?
Hi David ad Stan: It appears that Kevin's approach would benefit by appying Mathematica to Stan's 3/179 discussion. Kevin notes several well known areas in a manner that is beyond by readings. Could either of you comment on Kevin's latest suggestions? At the same time I would like to receive a few clues on understanding Sylvester's references. Thanks again for this interesting discussion. Milo attachment: It's interesting to ponder these things. I've found more examples of fractions like Stan's 3/179 that persist for a long time under the odd-greedy algorithm. Here's a short of list of fractions that act somewhat like 3/179 under iterations of x[k] -> x[k-1]^2 - x[k-1] + 1 - (x^2-1)/(N+k) (1) Table of "Persistently Odd & Greedy" Denominators: numerators 3 5 7 11 13 17 19 ----- ----- ------ ------ ------ ------ -------- 179 139 12473 1627 50387\ 218483\ 168149 197 1399 18143 14299 84239/ 223651/ 223211 377 2209 20663 17071 129947 366283\ 334931 629 2699 22049 41381 260597 371449/ 827 3649 24023 46331 594047\ 398071 1079 4909 32129 58057 627899/ 589933 1367 5039 40193 77417 674309 1619 5809 43679 99439 1817 5849 45863 1997 7289 46073 2069 8549 2249 For example, the first "persistent" fraction with numerator 5 is 5/139. The next is 5/1399, and so on. Stan's example is the first with numerator 3, followed by 3/197, 3/377, and so on. Each of these gives integer values for AT LEAST the initial 9 steps of the recurrence. That's as far as UBASIC will go before overflowing. I may try to get access to a program like Maple or Mathematica that (I think) can handle larger numbers. Failing that, I may try to write a program that evaluates the recurrence (mod p) for various primes p, which should enable me to determine how long the sequence goes on giving integers (although it won't tell me what those integers are). ksb wrote: >> This all must be closely related to Sylvester's sequence, defined in >> Sloane's Handbook of Integer Sequences (M0865) as >> >> a(n+1) = a(n)^2 - a(n) + 1 At 09:04 AM 10/20/96 -0700, Milo Gardner wrote: > That is to say, in what context did Sylvster define the above > relationship? I don't really know. I tried expanding the number 1 into unit fractions using the "prime-greedy" algorithm and got the sequence of denominators 2, 3, 7, 43, 1811,...etc. Then I looked up this sequence in Neil Sloane's Handbook of Integer Sequences and didn't find it...but I did notice the sequence 2,3,7,43,1807,...etc, which Sloane identifies as "Sylvester's sequence: a(n+1) = a(n)^2 - a(n) + 1". That didn't mean much to me, but then later when I derived the recurrence formula (1) from the requirement that the remainders increase by 1 at each step I noticed that it's very similar to Sylvester's recurrence. Sloane gives a couple of references, so I may try to check them out and see what Sylvester was doing. Regards, Kevin Brown P.S. Here are the first 10 denominators of the odd-greedy expansion for 5/139 = 1/29 + 1/673 + ...etc. The remainders are 5,6,7,8,9,10, 11,12,13,14,15,...? This is as far as UBASIC will go. d[0] = 29 d[1] = 673 d[2] = 387553 d[3] = 131422274281 d[4] = 15352723712926705785241 d[5] = 212135512864915777239968297129711897866300033 d[6] = 409104325622371338467604953357978082953878048586177214938\ 97280640199932919070783202610049 d[7] = 153419153472690634864150017185777107559299805417890183499\ 272997519053632772626491340819360118174137086820455429713\ 416964590925749755511324783696772099377098474672840615225\ 6857153 d[8] = 217268646021018488189693240228565514275160177407850629994\ 495520904153601210114475821596442873445136368464250383097\ 897470481550522003668308567157956616246526980656914868188\ 905828194669545264606583504719656586700910755790573361615\ 845263856445950094950269233409307815652091171689242021513\ 593190860971424799113988467435498218586244472773775258862\ 7179171387841 d[9] = 438338313621061591588732697821632657090815994417952651750\ 196843659141963784334595668404882949721754133099877843743\ 374090880740156878962453066485105197189108338604511165159\ 768822504094680333940958695870836714033324261355500454558\ 525274938130297837873483082255474634839353884981645950349\ 045757155675850817042667805401129890205592460676557856529\ 369921355099326487841647049276293102282576484783153789299\ 984977815226510311393133766384512554064764350054278720622\ 297467299808394262911741266558602742112068945931175493740\ 121781914338509607752570075598240917421138794963961060662\ 320227329206946215033007635394390156167460854714040381731\ 965702377595200628217672038155021026743769778253209871213\ 9173378898005200153921921 d[10]= 179331112042279073368723150909617862212578651817045112473\ 033793212576666742738879759694836161880734798621541980956\ 679622943552391824636146352741936377202926901576036490930\ 256443385820060816291558642490866183873861387186944020506\ 814251252783375196463130031627842572919866122071468966546\ 573738820818479096114782810135863865974403720621477539052\ 840476004951966657591621894615323232240542958762462166401\ 548942120482448740243703912882459890829581318610631061799\ 774440947096694300142945116991159305470971403961209302671\ 952021385098987681550798314457193958037317087362621280207\ 909446575877818231067825488998187769831187656371958407642\ 484015049725777147870394269432019929966228079927508733554\ 577859054727030112759510495607432338531897715400945878151\ 499019285887398030789861054109403198132708748563229334549\ 903997620682547365812663388912532598542080837704907809526\ 844778550961523820410590635784859939278772894258968557133\ 396901525617285485004221406978362535131539776991167438862\ 219286151610238945433593358912118104891770182053255809299\ 911747571517307395191688603507795725851523276015400616021\ 197318989653677873226258152326576201471874885514819400669\ 481006327197732192759053734209905723597692802968611079561\ 143702311576995799510059797294457983741322023047146079841\ 196474419128836722512690797867793784728592281545700924188\ 502267396800499731996854139165660769476566424052661655801\ 39668678886207435906351359208691567820467092786305 KSB
From: eppstein@ics.uci.edu To: WAGON@macalester.edu Subject: Re: Problem 848 (fwd) Date: Tue, 04 Nov 1997 11:41:37 -0800
Jeff Erickson forwarded me your above-titled message on odd Egyptian fraction representations of 3/179. You asked to be sent any solutions. As I believe you know, I have a large collection of algorithms for constructing Egyptian fractions, published in Mathematica in Educ. & Res., and online at http://www.ics.uci.edu/~eppstein/numth/egypt/ Most of these methods produce some even denominators, but a few do not. (Beware, I probably introduced some typos transferring these from my Mac to my Sun.) EgyptOddGreedy[3/179] didn't terminate in a reasonable amount of time. I assume this is why you chose this particular fraction to ask about... The proofs I know of that odd representations exist are I think pretty similar to the method I implemented as EgyptRemainder, which takes as a second argument a "powerful" number (with lots of divisors so that there are lots of ways to form sums of divisors). If the powerful number is odd, you get odd representations, modulo some recombination that happens because of possible repeated terms. EgyptRemainder[3/179,3*3*3*5*5*7] yielded the following: 1/105 + 1/189 + 1/525 + 1/33831 + 1/93795 1/105 + 1/189 + 1/525 + 1/31325 + 1/120825 1/105 + 1/175 + 1/675 + 1/33831 + 1/93795 1/105 + 1/175 + 1/675 + 1/31325 + 1/120825 1/75 + 1/525 + 1/675 + 1/33831 + 1/93795 1/75 + 1/525 + 1/675 + 1/31325 + 1/120825 1/75 + 1/315 + 1/4725 + 1/33831 + 1/93795 1/75 + 1/315 + 1/4725 + 1/31325 + 1/120825 1/63 + 1/1575 + 1/4725 + 1/33831 + 1/93795 1/63 + 1/1575 + 1/4725 + 1/31325 + 1/120825 EgyptShort[3/179,3], a close-to-brute-force search for representations with few terms (the second argument is the number of terms) produced a number of three-term representations, among them the odd 1/61 + 1/2745 + 1/491355 1/63 + 1/1253 + 1/11277 1/63 + 1/1611 + 1/3759 These are therefore the only odd three-term representations. The last of these is particularly succinct. There is only one two-term representation of 3/179, not odd. A small modification of EgyptSmallMult (another brute force method, which combines small multiples of the original fraction in order to get something that differs from the input by a fraction not divisible by the original denominator) shows that 3/179 = 1/895 + 1/1611 + 1/1969 + 1/2685 + 7/495, 3/179 = 1/179 + 1/537 + 1/895 + 1/1253 + 1/2327 + 1/2685 + 3/455, and that any other set of odd unit fractions having a difference from 3/179 that is not itself a multiple of 1/179 must include a higher denominator. Calling EgyptShort on 7/495 produces the representations 1/895 + 1/1611 + 1/1969 + 1/2685 + 1/77 + 1/1485 + 1/2079 1/895 + 1/1611 + 1/1969 + 1/2685 + 1/77 + 1/1575 + 1/1925 1/895 + 1/1611 + 1/1969 + 1/2685 + 1/77 + 1/1683 + 1/1785 1/895 + 1/1611 + 1/1969 + 1/2685 + 1/81 + 1/891 + 1/1485 1/895 + 1/1611 + 1/1969 + 1/2685 + 1/81 + 1/935 + 1/1377 1/895 + 1/1611 + 1/1969 + 1/2685 + 1/81 + 1/561 + 1/1683 1/895 + 1/1611 + 1/1969 + 1/2685 + 1/81 + 1/693 + 1/1071 1/895 + 1/1611 + 1/1969 + 1/2685 + 1/81 + 1/765 + 1/935 1/895 + 1/1611 + 1/1969 + 1/2685 + 1/87 + 1/495 + 1/1595 1/895 + 1/1611 + 1/1969 + 1/2685 + 1/91 + 1/585 + 1/693 1/895 + 1/1611 + 1/1969 + 1/2685 + 1/95 + 1/495 + 1/627 1/895 + 1/1611 + 1/1969 + 1/2685 + 1/99 + 1/275 + 1/2475 1/895 + 1/1611 + 1/1969 + 1/2685 + 1/99 + 1/285 + 1/1881 1/895 + 1/1611 + 1/1969 + 1/2685 + 1/99 + 1/297 + 1/1485 1/895 + 1/1611 + 1/1969 + 1/2685 + 1/99 + 1/315 + 1/1155 1/895 + 1/1611 + 1/1969 + 1/2685 + 1/99 + 1/385 + 1/693 1/895 + 1/1611 + 1/1969 + 1/2685 + 1/99 + 1/429 + 1/585 1/895 + 1/1611 + 1/1969 + 1/2685 + 1/105 + 1/315 + 1/693 1/895 + 1/1611 + 1/1969 + 1/2685 + 1/105 + 1/385 + 1/495 1/895 + 1/1611 + 1/1969 + 1/2685 + 1/117 + 1/195 + 1/2145 1/895 + 1/1611 + 1/1969 + 1/2685 + 1/117 + 1/209 + 1/1235 1/895 + 1/1611 + 1/1969 + 1/2685 + 1/117 + 1/221 + 1/935 1/895 + 1/1611 + 1/1969 + 1/2685 + 1/135 + 1/165 + 1/1485 1/895 + 1/1611 + 1/1969 + 1/2685 + 1/135 + 1/189 + 1/693 1/895 + 1/1611 + 1/1969 + 1/2685 + 1/135 + 1/209 + 1/513 1/895 + 1/1611 + 1/1969 + 1/2685 + 1/143 + 1/195 + 1/495 1/895 + 1/1611 + 1/1969 + 1/2685 + 1/165 + 1/225 + 1/275 1/895 + 1/1611 + 1/1969 + 1/2685 + 1/171 + 1/209 + 1/285 which have the minimum max denominator (2685) of any odd representation of 3/179. Unless I missed one in going through the results, all other representations with the same max denominator have more terms. -- David Eppstein UC Irvine Dept. of Information & Computer Science eppstein@ics.uci.edu http://www.ics.uci.edu/~eppstein/
Date: Tue, 04 Nov 1997 20:26:26 -0500 (CDT) From: Stan Wagon <WAGON@macalester.edu> Subject: Re: Problem 848 (fwd) To: eppstein@ics.uci.edu
thanks for news. David Bailey (NASA) has just finished with 3/2879. Last term has 3,000,000 digits.
From: eppstein@ics.uci.edu To: WAGON@macalester.edu Subject: Re: Problem 848 (fwd) Date: Tue, 04 Nov 1997 21:15:38 -0800
David Bailey (NASA) has just finished with 3/2879. Last term has 3,000,000 digits. 3/2879 has 11 three-term odd representations, the one with the smallest max denominator being 1/963 + 1/308053 + 1/2772477. The minimum possible max denominator in any odd representation is 60459; the unique shortest representation having that max denominator is 1/14395 + 1/20153 + 1/25911 + 1/43185 + 1/48943 + 1/54701 + 1/60459 + 1/1615 + 1/5355. Is there some systematic procedure of finding bad examples for the odd greedy method, or do you and Bailey just try all of them and see which ones run long?
Date: Wed, 05 Nov 1997 08:58:49 -0500 (CDT) From: Stan Wagon <WAGON@macalester.edu> Subject: Re: Problem 848 (fwd) To: eppstein@ics.uci.edu
nope, we do not know a systematic way to find bad examples. Would be nice to have some sort of heuristic, as I would like to find one that stumps Bailey's algorithm.... Stan Wagon, Professor of Mathematics Macalester College, St. Paul, Minnesota 55105 (612) 696-6057 fax = (612) 696-6518 primary e-mail: wagon@macalester.edu secondary e-mail: wagon@compuserve.com web page: http://www.math.macalester.edu/~wagon To subscribe to the Problem of the Week send a message to <<MAILSERV@MACALESTER.EDU>>. Body of message should read simply SUBSCRIBE POTW-L Macalester students should NOT subscribe to the e-list, but get printed postings instead.
Date: Sun, 9 Nov 1997 18:37:29 -0500 From: stan wagon <wagon@compuserve.com> Subject: Egyptian fraction Mma package To: "INTERNET:eppstein@ics.uci.edu" <eppstein@ics.uci.edu>
1. Best to use wagon@macalester.edu You sounded pretty confident that the smallest-denominator example you to= ld me for 3/179 was indeed the smallest. Is that a certainty? Brief Comments on Package (I have not really exercised it yet). I note that "Splitting" is not an option for Method. But it was surely in your MiER paper. What about ODD GREEDY? Is that what results when one using the OddQ restriction on Greedy? You should follow standard Mma style for usage messages: Smallest::usage =3D "Select is an option to EgyptianFraction that, when s= et to Smallest, causes only those decompositions minimizing the maximum denominator to be retuned."; Several of my correspondents -- Milo Gardner, Charles Rees -- seem interested in how exactly the Egyptians came up with their forms. M.G. ha= s some code that he belives captures their work, so presumably he does inde= ed have a rigorous algorithm.... I have found it VERY valuable to have a ShowNumerators option. Perhaps ShowRemainderNumerators is a better name. This causes the numerators of the remainders to be returned as part of th= e answer. I guess for some methods the concept of a "remainder" might not b= e meaningful. I have not wholly exercised your package. Not clear how to publicize it. I could mention it on my PoW-e-list if you don't min= d receiving requests for it. Bailey is now up to 50,000,000 digits with 5/3809 via odd greedy!
From: eppstein@ics.uci.edu To: wagon@compuserve.com Subject: Re: Egyptian fraction Mma package Date: Sun, 09 Nov 1997 18:49:25 -0800
You sounded pretty confident that the smallest-denominator example you to= ld me for 3/179 was indeed the smallest. Is that a certainty? Yes. 179 is prime, and the SmallMultiples method found that that denominator was necessary even to get 3/179-(unit fractions) to have a denominator coprime to 179. Bailey is now up to 50,000,000 digits with 5/3809 via odd greedy! It has many three-term representations, the best being 1/897 + 1/6739 + 1/20217. Unfortunately 3809 is not prime, making it harder to find representations minimizing the denominator. SmallMultiples ran out of memory and crashed my machine -- I have some ideas on reducing its memory a little but I don't think they'd help enough. However, I implemented a variant, FactorMultiples (try combinations of multiples of the largest prime factor of the denominator until the remaining fraction is coprime to that factor) which (together with reverse greedy) found 1/2051 + 1/2925 + 1/5567 + 1/5985 + 1/7325 The information printed by Debug->True (I renamed this to Trace->True since it's useful for tracing progress not just debugging, and added the partial numerators and denominators you requested) can be used to prove that this expansion minimizes the maximum denominator. -- David Eppstein UC Irvine Dept. of Information & Computer Science eppstein@ics.uci.edu http://www.ics.uci.edu/~eppstein/
Date: Wed, 12 Nov 1997 13:27:35 -0800 (PST) From: Milo Gardner <gardnerm@ecs.csus.edu> To: eppstein@ics.uci.edu Subject: 5/3809
Dear David, Stan Wagon suggested that it would be alright to mention points related to 'optiminally' converting 5/3809. ------------------------------------------------------------ Not much new to report on Egyptian fractions. I sent out a long report several days ago. Eppstein is working on a Mathematica package that incorporates a variety of methods. David Bailey (and I) continue to wonder about 5/3809's behavior under odd greedy. His program checks to 60,000,000 digits, but it did not halt. So, if this halts, it leads to numbers having more than 60,000,000 digits. Eppstein's package has no trouble finding reps. of 5/3809 such as: 1/897 + 1/6739 + 1/20217 and 1/2051 + 1/2925 + 1/5567 + 1/5985 + 1/7325. Eppstein adds that his small max-denominator result reported in previous mailing is provably optimal. Readers interested in his general-purpose Egyptian fractions package should contact him: eppstein@ics.uci.edu . ------------------------------------------------------------ I wonder if you have factor 3809 into: 5/13(1/293) such that 5/13 - 1/4 = (20 - 13)/(4*13) = (4 + 2 + 1)/(4*13) or 4/13 - 1/4 = (16 -13)/(4*13) = (2 + 1)/(4*13) as Greeks would have considered the solution: 5/3809 = 293'(4' 13' 26' 52')? pretty close to your 5-term 25 times last term denominator. I guess 13' 26' 52' can be reduced by adding a 4th term, by using several methods. Of course another historical factoring can be considered, to find a 3-term series. 5/3809 = 1/13(5/293) where, 5/293 = 60' + (4 + 3)/(60*293) = 60' + 293'(15' + 20') or, 5/3809 = 13'(60' + 293'(15' + 20') It appears that your optimal solution lists a 5-term series one with a last term of 25 times 293, rather than my first attempt of 260 times near your 3-term 69 times series. I did all of my calculations in my head, as noted above. Regards, Milo Gardner
From: eppstein@ics.uci.edu To: gardnerm@ecs.csus.edu Subject: Re: 5/3809 Date: Wed, 12 Nov 1997 14:00:37 -0800
It appears that your optimal solution lists a 5-term series one with a last term of 25 times 293, rather than my first attempt of 260 times near your 3-term 69 times series. You should note that I was looking for solutions in which all denominators are odd, since this was in the context of the odd greedy method performing badly. Most of the denominators in the solution you mention 293'(4' 13' 26' 52') are even. If you don't require denominators to be odd there are better solutions, e.g. 762' 2902458' (if you are trying to minimize the number of terms) or 2344' 3223' 3432' 3516' (if you are trying to minimize the max denominator). -d
From: eppstein@ics.uci.edu To: wagon@macalester.edu Subject: odd greedy Date: Tue, 25 Nov 1997 16:08:30 -0800
Your and D. Bailey's experiments with odd greedy have been casting a lot of doubt on my heuristic argument that the numerator declines on average (the argument based on assuming that the next numerator for a fraction x/y should behave like a random variable uniformly distributed over the integers in the interval (0,2x)). Here is some more doubt. I tried implementing a method for computing the numerators of the odd greedy method based only on the knowledge of the denominator mod some base (rather than the true denominator). At each step the divisions you do cause the base to (usually) decrease; so the method could terminate due to lack of information rather than terminating due to reaching zero. Anyway, I started from 3/x and worked through all possible sequences of numerators from there. There are many fewer than one might expect: - If x is 1 mod 5 the sequence is {3,1}. - If x is 5 or 11 mod 30 the sequence is {3,4,1}. - If x is 23 mod 30 the sequence is {3,4,5,4,1}. - If x is 29,47,59, or 77 mod 90 the sequence is {3,4,5,1}. - If x is 17,269,287 or 539 mod 630 the sequence is {3,4,5,6,1}. - If x is 89 or 467 mod 630 the sequence is {3,4,5,6,7,2,1}. The remaining cases, 107,179,197,359,377,449,557, and 629 mod 630 all begin with the same sequence {3,4,5,6,7,8,9,10,...}. Starting from here I got a little sloppy about exhaustively searching all values, so my results are a little suspect, but it seems that depending on the value of x mod 3050, the next numerator should be either 3 or 11. The values of x leading to a 3 seem to all have the sequence {3,4,5,6,7,8,9,10,3,4,1}. The values of x leading to 11 either have the sequence {3,4,5,6,7,8,9,10,1} (if x has the right value mod 11 to cause a cancellation) or {3,4,5,6,7,8,9,10,11,...}. As you computed over a year ago, the full sequence of numerators for 3/179 is {3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,2,3,4,1} so this pattern of increasing the numerator by one continues for many more steps. But why does this increase happen so often for such a small number as 179? Why are there so few other choices for possible numerator sequences? All numerator sequences I've seen so far either terminate quickly or eventually fall into the increase-by-one pattern e.g. 5/3809: {5,2,3,4,5,6,7,...}; why? -d
From: eppstein@ics.uci.edu To: wagon@macalester.edu Subject: odd greedy Date: Tue, 25 Nov 1997 16:19:12 -0800
All numerator sequences I've seen so far either terminate quickly or eventually fall into the increase-by-one pattern e.g. 5/3809: {5,2,3,4,5,6,7,...}; why? Oops, not 3809, I meant 3803 (or other numbers congruent to 83, 203, or 263 mod 300). In fact I wonder whether you meant 3809 when you sent the following paragraph to your potw mailing list: David Bailey (and I) continue to wonder about 5/3809's behavior under odd greedy. His program checks to 60,000,000 digits, but it did not halt. So, if this halts, it leads to numbers having more than 60,000,000 digits. My calculations indicate it has a three-term odd greedy expansion: 5/3809 = 1/763 + 1/484379 + 1/201104957599. What number is Bailey really working on? Not 3803 either, it has numerator sequence {5,2,3,4,5,6,7,8,9,10,1}. -d
Date: Tue, 25 Nov 1997 19:03:30 -0500 (CDT) From: Stan Wagon <WAGON@macalester.edu> Subject: Re: odd greedy To: eppstein@ics.uci.edu
5/5809 is the cute one. Sorry for the typo. I am glad to see you are relooking at your heuristic. It would be nice to have a heuristic for this question....but I am rather hoping some examples DO go to infinity! Looks like you are getting some insight into the "increase-by-one" sequence?....or are you just observing that they exist? stan (I have no info about the Japanese...will ask Bailey again if he has asked them.)
From: eppstein@ics.uci.edu To: wagon@macalester.edu Subject: Re: odd greedy Date: Tue, 25 Nov 1997 18:16:03 -0800
In a few seconds Mathematica was able to carry out the odd greedy method for 5/5809 modulo 37943838567204570000 and determine that its numerator sequence is {5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,1}. In fact this was much quicker than finding the expansion 1/2355 + 1/4239 + 1/4995 (this same expansion was returned both by searching for min number of terms with Method->MinimizeTerms and by searching for min max denomator with Method->SmallMultiples, both slower than doing the odd greedy modulo arithmetic). -- David Eppstein UC Irvine Dept. of Information & Computer Science eppstein@ics.uci.edu http://www.ics.uci.edu/~eppstein/
From: eppstein@ics.uci.edu To: WAGON@macalester.edu Subject: Re: odd greedy Date: Mon, 01 Dec 1997 10:45:03 -0800
Late news: David Eppstein, by working modulo 37943838567204570000, has shown that the odd greedy algorithm for a halts with 27 terms, and the numerator remainder sequence is: 5, 6, 7, . . . , 30, 1. Correct? Sounds good to me. I guess we could change the problem to: Given n, determine the total number of digits in the odd greedy expansion. One observation I made over the weekend is that with my new code, finding the sequence of odd greedy numerators (if finite) now takes time polynomial in the combined input and output sizes. Computing the exact denominators is exponential if all you want is the numerators since the integer precision needed roughly doubles at each step -- the modular code's required precision increases at each step too but linearly rather than exponentially. In other words, it's not a coincidence that my code worked for 5/5809 and Bailey's didn't. The new modular code is so fast that only an extremely long finite sequence, much longer than the sequence for 5/5809, would fail to be distinguished from an infinite sequence.
Date: Wed, 03 Dec 1997 12:52:02 -0500 (CDT) From: Stan Wagon <WAGON@macalester.edu> Subject: from helaman To: _eppstein: ;
some old comments from helaman ferguson..... --Boundary_(ID_XvH1SeoOMjDRjTmJrmDg2g) Content-type: TEXT/PLAIN; CHARSET=US-ASCII > [**** Insert text here ****] > > --Boundary_(ID_q0gHSkKJWP+ylWQg0CBy5Q) > Content-type: MESSAGE/RFC822 > > Return-path: <helamanf@super.org> > Received: from super.super.org by macalester.edu (PMDF V5.1-8 #15853) > with ESMTP id <01IPVM94RJJO001WO4@macalester.edu> for WAGON@macalester.edu; > Tue, 11 Nov 1997 09:02:42 CDT > Received: by super.super.org; id KAA18669; Tue, 11 Nov 1997 10:01:56 -0500 (EST) > Received: from gotham.super.org(192.239.79.2) by super.super.org via smap (3.2) > id xma018665; Tue, 11 Nov 1997 10:01:36 -0500 > Received: from opal.super.org (opal [192.239.79.68]) > by gotham.super.org (8.6.12/8.6.12.1) with ESMTP id KAA11021; Tue, > 11 Nov 1997 10:01:34 -0500 > Received: (helamanf@localhost) by opal.super.org (8.6.12/8.6.12.client) > id KAA20510; Tue, 11 Nov 1997 10:01:34 -0500 > Date: Tue, 11 Nov 1997 10:01:34 -0500 > From: helamanf@super.org (Helaman R.P. Ferguson) > Subject: Re: Egypt > To: WAGON@macalester.edu, dbailey@nas.nasa.gov, helamanf@super.org, > jborwein@cecm.sfu.ca, njas@research.att.com, pborwein@cecm.sfu.ca > Message-id: <199711111501.KAA20510@opal.super.org> > > It is not surprising that the reciprocal odd expansions for > rationals p/q, q odd should have arbitrarily long lengths. > When q is even the reciprocal odd expansions are infinite, > so whenever p/q, q odd is particularly close to another > rational a/b, b even or sum thereof we expect the > reciprocal odd expansion to be long. For example, > > 5/5809 = 1/1162 + 1/6750058 > > > --Boundary_(ID_q0gHSkKJWP+ylWQg0CBy5Q)-- Stan Wagon, Professor of Mathematics Macalester College, St. Paul, Minnesota 55105 (612) 696-6057 fax = (612) 696-6518 primary e-mail: wagon@macalester.edu secondary e-mail: wagon@compuserve.com web page: http://www.math.macalester.edu/~wagon To subscribe to the Problem of the Week send a message to <<MAILSERV@MACALESTER.EDU>>. Body of message should read simply SUBSCRIBE POTW-L Macalester students should NOT subscribe to the e-list, but get printed postings instead. --Boundary_(ID_XvH1SeoOMjDRjTmJrmDg2g)--
From: eppstein@ics.uci.edu To: WAGON@macalester.edu, helamanf@super.org Subject: Re: from helaman Date: Wed, 03 Dec 1997 11:13:45 -0800
> It is not surprising that the reciprocal odd expansions for > rationals p/q, q odd should have arbitrarily long lengths. > When q is even the reciprocal odd expansions are infinite, > so whenever p/q, q odd is particularly close to another > rational a/b, b even or sum thereof we expect the > reciprocal odd expansion to be long. For example, > > 5/5809 = 1/1162 + 1/6750058 Does this really make sense? I don't see how being within 1/6750058 is "particularly close" to the even rational 1/1162 when the odd greedy expansion gets within much closer distances after a very small number of terms. In general if p/q (q odd) is within distance d of an even fraction r/s (suppose as above that s<q) then d is bounded below by something like 1/q^2, but the odd greedy expansion for p/q will have denominators much bigger than q^2 in only three terms. So after those three terms the odd greedy expansions for p/q and r/s should diverge. In this particular example the expansions don't even stay similar for more than two terms: 5/5809 = 1/1163 + 1/1125979 + ... while 1/1162 = 1/1163 + 1/1351407 + ... By the way, I've been experimenting more with my modular code, looking for fractions having the same pattern as 5/5809 of the numerators increasing by one at each term. Starting with 7, I was able to find plenty of fractions 7/x for which the numerators increased all the way to 38 (for instance 7/1113923414579765333660423), but I am having trouble finding any for which they increase to 39. Other arithmetic sequences of numerators also seem easy enough to generate. -- David Eppstein UC Irvine Dept. of Information & Computer Science eppstein@ics.uci.edu http://www.ics.uci.edu/~eppstein/
From: eppstein@ics.uci.edu To: WAGON@macalester.edu Subject: Re: size Date: Thu, 04 Dec 1997 11:50:06 -0800
In the traditional greedy situation it is easy to prove a functional relationship between the number of digits in the denominators and the length of the representation. It is in the Egyptian chapter in Klee/Wagon. Quite possibly the same ideas would work in the odd case. It should be easy to compute the approximate denominators in floating point, to any reasonable number of significant digits, since each is a simple function of the previous denominator and numerator, and we can now find the numerators exactly. So the first digits of the denominators are easy, and the last digits are also easy (by the modular arithmetic I've been doing), it's the middle that's hard (because it's too big, not unlike certain peoples' middles in this holiday season). I could even modify my program to output a straight-line-program for evaluating all the denominators, e.g. d1=(an explicit integer), d2=(some explicit quadratic in d1), d3=(some explicit quadratic in d2), etc. But of course you wouldn't have the time and space to actually expand all these quadratics in exact integer arithmetic... So your latest example might involve a trillion digits! From 7 to 38 involves 32 doublings of the number of digits. So the total number of digits should be roughly 25*2^32 ~ 10^11, somewhat shy of the trillions. -d