## Odd-Greedy Unit Fraction Expansions

Any ratio of integers m/n can be expressed as a finite sum of unit
fractions, i.e., fractions with unit numerators.  One method of
expanding a given fraction into a sum of unit fractions is via the
"greedy algorithm", according to which at each stage we select the
largest possible unit fraction (i.e., with the least denominator)
less than or equal to the current remainder.  It's easy to show
that this necessarily terminates in a finite number of steps with
a complete unit fraction expansion.

However, if we allow only odd denominators it's not known whether
the greedy algorithm applied to a rational number necessarily
terminates in a finite number of steps.  Of course, we can easily
define real numbers that have infinite odd-greedy expansions - just
take any infinite sequence of odd unit fractions such that the kth
denominator d[k] is greater than (1/2)d[k-1]^2 - d[k-1]  -  but we
don't know if any such number is rational.  (For a more detailed
discussion of the possible rationality of infinite odd greedy
expansions, see Irrationality of Quadratic Sums.)

Anyway, although most ratios of small numbers can be expressed as a
sum of just a few odd unit fractions, it turns out that some of these
fractions have surprisingly long odd-greedy expansions.  For example,
the odd-greedy expansion of 3/179 has 19 terms.  Moreover, the sequence
of numerators of the remainders is striking:

3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 2, 3, 4, 1

This was noted by Stan Wagon, who asked via email if there were fractions
with even longer odd-greedy expansions, and for an explanation of the sequence
of consecutive remainder numerators, which turns out not to be a unique
occurrence.  (See The Greedy Algorithm for Unit Fractions.) I suggested
to Stan that he look at the fraction 5/139, which also runs to 19 terms,
with the sequence of remainder numerators

5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 26, 51, 2, 3, 4, 1

I also directed his attention to a handful of other possibilities that were
likely to yield long sequences, with emphasis on 3/2879 and 5/5809 as being
strong candidates.  Subsequently David Bailey performed an exhaustive computer
search for lenghty sequences and re-discovered the fact that these two
fractions give unusually long odd-greedy expansions.  The fraction 5/5809
is a particularly nice example because the sequence of remainder numerators
increases by 1 at each step, all the way to the end: 5,6,7,...,29,30,1.

I also mentioned to Stan (and to David Eppstein) that although the
denominators in these sequences can run into the billions of digits,
they could be evaluated using modulo arithmetic with a suitable modulus,
since the denominators involve only small prime factors. David subsequently
applied this approach with the modulus 6(31!)(10!)(6!)(4!)^2 to compute the
remainders of the 5/5809 sequence.

I also told Stan and David that it wouldn't be too difficult to construct
fractions with arbitrarily long odd-greedy expansions, but this apparently
was overlooked (judging from Richard Guy's subsequent account of the history
of this problem in the Dec 98 issue of The American Mathematical Monthly). So
I'll show here how to construct a fraction with odd-greedy expansion of
length k for any positive integer k.

The key to understanding these expansions is to note that if we begin with
any fraction of the form n/(2m-1) where m is divisble by n, the Odd-Greedy
algorithm will give the first unit fraction term 1/(2[m/n]+1) with the
remainder

n+1
--------------------
2[(m/n)(2m+n-1)] - 1

so this becomes the new fraction to be expanded.  In effect the
values of n and m have been transformed according to

n  ->  n+1            m  ->  (m/n)(2m+n-1)

Now, if our new value of m is divisible by the new value of n, we
can repeat the process, and this continues to give the odd greedy
terms and remainders until we reach a stage where m is not divisible
by n. Notice that the sequence of numerators consists of consecutive
integers, and at each stage m is being divided by n and multiplied
by the factor (2m+n-1).  Therefore, if our initial value of m is
something like 100!, it's clear that we can continue this process
for numerators up to AT LEAST 100, at which point we will have
exhausted the divisibility that we built in to our initial value
of m.  However, during those 100 steps we have been multiplying m
by many large and generally composite numbers, so there's a fair
chance that m will have acquired more useful factors by that point.
In any case, we can answer one of our questions by noting that the
odd-greedy expansion of 3/(N!-1) must have at least N-2 terms, and
the remainders for those terms are 3,4,5,..,N.

Of course, our initial m need not be a factorial, but it must be
divisible by the first numerator, and it helps if it has some
common factors with some subsequent numerators.  To illustrate
how this works, consider the case of 3/179, where the initial value
of m is 90, which only covers the numerators 3 and 5, with a spare
power of 3 and 2.  On the very first step we divide m by 3 but
multiply by (2m+3-1)=182, which fortuitously gives us another power
of 2 to cover the numerator 4 (just in time!), and also gives us 7
and 13, which we will use shortly.  Then on the next step we divide
by 4 but multiply by 10923, which gives us 11 as well as another
factor of 3 (not to mention a factor of 331, which doesn't do us
much good directly).  As we continue we acquire the factors of 2
and 3 we need to cover the numerators 6, 8, and 9, as well as
another factor of 5 to cover 10.

This shows how the process tends to feed on itself once it gets
started, because the more steps we take, the more factors we apply
to m, often providing the factors needed to enable further steps
with consecutive remainder numerators.  This is the reason long
sequences of unit-increasing remainders are so common, even for
fairly small fractions.

It's interesting to consider the odd greedy expansion of a fraction
such as 3/(500! - 1).  We know this will contain at least 500 terms
(and since the number of digits in the denominators roughly doubles
on each term, the 500th term would have over 2^500 digits), and the
numerators of the remainders will be 4,5,6,...,500, but what will
happen then?  After cumulatively multiplying into m numbers of the
form (2m+n-1) nearly 500 times, we will likely have accumulated
a huge number of factors in m, so it wouldn't be too surprising if
the sequence continued past the point when the initial m had been
exhausted (especially since the terms (2m+n-1) grow exponentially).
Recall how 3/179 essentially "lived off the land" for most of its
run.  The interesting question is whether there might be some "break-
even point", so that a fraction like 3/(500!-1) might have enough
initial divisibility to boost it into a sequence where, at least
probabilistically, we would expect it to be able to continue
generating the factors it needs indefinitely.

I did some checking, and found that for fractions of the form
3/(2m-1) with m=500! we are able to cover 32 of the 64 primes
between 500 and 1000.  Similarly, with m=100! we are able to cover
10 of the 20 primes between 100 and 200, and with m=50! we can
cover 6 of the 10 primes between 50 and 100.  I'm not sure off
hand why we seem to be able to cover exactly half the primes.

Just for fun, I checked to see how many residues for the initial
m value (mod p) are "favorable" for covering p, meaning that by
the time we reach a numerator of p we can continue the odd-greedy
expansion. Obviously a residue of 0 (mod p) for the initial m
guarantees that we can cover p, but I was curious to know how many
other residues are favorable for each prime.  Here's a little table
showing the number of favorable m residues (mod p) for numerators
from 1 to 10.

Table:  Number of Favorable Initial m Residues (mod p)

Numerator (initial n)

p       1   2   3   4   5   6   7   8   9  10
--      --  --  --  --  --  --  --  --  --  --
5       3   3   2   0   0   0   0   0   0   0
7       5   4   4   4   2   0   0   0   0   0
11       5   7   8   9   9   6   4   2   2   0
13       5   5   6   5   4   4   6   6   3   2
17       5   5   7   6   5   3   2   3   4   4
19       1   6   5   4   4   2   7   5   8   8
23       9   6   6   6   6   7   8   9   7   6
29      21  19  21  17  16  16  14  11   8  13
31      27  24  19  18  15  14  15  15  14  12
37      21  18  15  14  13  16  15  18  22  22
41      17  22  20  18  19  19  21  20  22  22
43      17  19  22  24  25  30  33  34  33  33
47      33  33  31  30  33  36  36  32  37  32
53      47  49  47  49  49  45  45  43  47  43
59      31  37  37  35  34  31  27  33  28  17
61      39  33  34  34  28  32  26  29  28  31
67      25  28  29  35  32  26  25  24  32  40
71      19  24  20  24  26  28  28  32  30  22
73      21  18  20  19  17  19  18  28  26  28
79      47  52  47  55  50  47  45  53  53  57
83      41  42  51  58  63  59  59  55  55  53
89      43  29  29  34  39  30  38  46  45  51
97      81  71  71  71  76  71  75  73  77  73
101      21  16  18  24  24  30  23  23  32  35
103      21  22  21  22  16  16  12   9  10  12
107      63  58  50  46  42  44  45  55  54  49
109       7   4   2   4   6   4   4   4   9  12
113      81  85  85  87  85  91  97  93  88  89
127      93 100  91  95  91  91  97  91  91  88
131      31  33  33  34  29  33  34  36  40  40
137      63  64  68  64  66  69  71  71  66  66
139      73  79  85  90  94 100  94  91  93 103
149     105 103 103  96  93  95  92  92  89  87
151      17  20  19  17  14  14  10  10   8  15
157      29  24  25  28  34  36  46  47  46  48
163      47  40  40  39  35  34  30  30  24  24
167      25  22  20  23  20  18  17  16  14  14
173      97  95  92  97  94  88  76  77  75  80
179     151 153 155 155 155 151 149 148 145 144
181     173 175 175 177 177 177 179 179 179 175
191     109 104  96  84  85  77  81  82  84  82
193      47  44  40  48  45  59  59  55  54  44
197      93 100  89  88  86  78  79  83  80  87
199     161 163 159 148 143 148 148 141 133 128

The average ratio of favorable residues to total number of residues
seems to be close to 1/2.  Also, notice that 109 is evidently a
"sticky wicket", especially for fractions with numerator 3, because
the only way past is to either make the initial m value a multiple
of 109 or make it congruent to -1 (mod 109).  In contrast p=181 has
over 96% favorable.