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.
Return to MathPages Main Menu