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