The Greedy Algorithm for Unit Fractions
Suppose we want to write the simple fraction 2/3 as a sum of
unit fractions with distinct odd denominators. If we apply the
"greedy algorithm", which consists of taking the largest qualifying
unit fraction at each stage, we would begin with the term 1/3,
leaving a remainder of 1/3. Since we require distinct denominators
we can't use 1/3 for our second term, so we go on to the next
largest odd unit fraction, which is 1/5. This leaves a remainder
of 2/15, and the largest odd unit fraction less than 2/15 is 1/9,
so that is our third term, leaving a remainder of exactly 1/45.
So,the odd greedy expansion of 2/3 terminates after four steps,
giving the result
2/3 = 1/3 + 1/5 + 1/9 + 1/45
The non-zero remainders we encountered during this process were 1/3,
2/15, and 1/45, with the numerators 1, 2, 1.
There are some interesting unsolved problems related to odd greedy
expansions. One open question is whether every fraction is guaranteed
to terminate in a finite number of steps. This is not a trivial question,
as shown by the odd greedy expansion of 1 (not using 1/1 on the first
step). The result is
1 = 1/3 + 1/5 + 1/7 + 1/9 + 1/11 + 1/13 + 1/23 + 1/721 + 1/979007
+ 1/661211444787 + ...
It isn't known whether this eventually terminates. Incidentally, if
we restrict ourselves to prime denominators we have
1 = 1/2 + 1/3 + 1/7 + 1/43 + 1/1811 + 1/654149 + ...
Most fractions terminate quickly under the application of the odd greedy
algorithm, but some require quite a large number of terms. For example, if
the fraction 3/179 is converted into a sum of unit fractions with odd
denominators using the greedy algorithm, it takes 19 terms. Also, the
numerators of the sequence of remainders is
3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 2, 3, 4, 1
Of course, if we don't require the use of the greedy algorithm, then
the fraction 3/179 has the 3-term expansion with odd denominators
1/63 + 1/1611 + 1/3759, and conversely if allow both odd and even
denominators then the greedy algorithm yields the 2-term expansion
1/60 + 1/10740. It is only the simultaneous imposition of BOTH
requirements (odd AND greedy) that leads to the unusually lengthy
expansion. Note also that the numerators of successive terms are
consecutive integers from 3 to 17. (This raises the question of
whether you could "construct" examples by working backwards from a
given sequence of remainders.)
In general, if we have a fraction N/D we 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 again the fraction 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
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,
and evidently f_3(61)=13. Of course, this doesn't completly describe an
expansion, because once the integers break down we can start over again
with the new N/D, as illustrated by the case 3/179:
3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 2, 3, 4, 1
|---------------------------------------------------| |--------| |-|
By the way, there may be some connection with a sequence studied by
Sylvester, 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.
We might try to estimate, on a naive probabilistic basis, the expected
value of f_N(n) for any given N and n, because it seems to depend only
on whether each d[k] is or is not congruent to +-1 (mod N+k). If d[k]
were equally likely to be in any of the N+k equivalence classes mod N+k,
this would give a probability of 2/(N+k) that the kth step will give an
integer. Thus we might infer that small numerators N will give the best
chance for long strings, and the probability of j consecutive integers
would be something like
N!
------ 2^j
(N+j)!
However, if this were correct, the case 3/179 would have a probability
of about 1 in 425,675,250. Evidently the assumption of equi-probable
equivalence classes is wrong.
Here's a short of list of fractions that act somewhat like 3/179 under
iterations of
x[k-1]^2 - 1
x[k] = x[k-1]^2 - x[k-1] + 1 - ------------ (1)
N+k
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 "stubborn" fraction with numerator 5 is 5/139.
The next is 5/1399, and so on. Each of these gives integer values for
AT LEAST the initial 9 steps of the recurrence. To go beyond this, we
can evaluates the recurrence (mod p) for various primes p, which enables
us to determine how long the sequence goes on giving integers (although
it won't tell what those integers are).
Obviously every one of these stubborn fractions N/D has D=-1 (mod 2N).
In addition, it seems that if N = 1 (or 0) (mod 3) then D=-1 (mod 6N).
I didn't include N=1 in the above table, but it's interesting to determine
the persistent denominators for that case as well. It seems that the
most persistent are D = 19, 61, 73, 151, 181, 193, 271, 283, 379, and
so on.
The first 10 denominators of the odd-greedy expansion for
5/139 = 1/29 + 1/673 + ...etc.
are given here. The sequence terminates after 19 steps, and the
numerators of the remainders are
5,6,7,8,9,10,11,12,13,14,15,16,17,26,51,2,3,4,1
We would like to efficiently determine an upper limit for the number of
consecutive iterations of (1) that could possibly yield integers, beginning
with the initial value x[0] = (D+1)/N + 1 for any given fraction N/D.
The only simple way of doing this that I can see is by evaluating the
iteration (mod p) for various primes p > N+1. If x[p-N-1] is not congruent
to +1 or -1 (mod p), then the string must be broken at (or before) the
point when N+k reaches p.
The limiting primes by which point the string must break down for various
fractions are listed below
3/179 17 5/139 17
3/197 17 5/1399 19
3/377 13 5/2209 19
3/629 13 5/2699 17
3/827 13 5/3649 17
3/1079 13 5/4909 17
3/1367 41 5/5039 17
3/1619 17 5/5809 31
3/1817 19 5/5849 17
3/1997 13 5/7289 17
3/2069 29 5/8549 17
3/2249 13
3/2267 13
3/2447 19
3/2699 13
3/2879 23
3/2897 13
3/2969 13
This suggests that 3/1367, 3/2069, 3/2879, and 5/5809 would be good
candidate for highly "stubborn" odd greedy expansions, since the
sequences of uniformly increasing remainders in these cases don't
*necessarily* break down until N+k equals 41, 29, 23, and 31 respectively.
Of course, they COULD break down much sooner. The others (the 13's and
17's) definitely won't yield expansions of length greater than 17.
Another interesting approach to this problem is to determine the
sufficient condition for greediness of a sequence. Clearly if 1/n is
a term in the sequence, then the sum of all later terms in the sequence
must be less than the difference
1/n - 1/(n+2) = ((n+2)-(n))/(n(n+2)) = 2/(n(n+2))
Now, for all odd n (greater than 1) we have the inequality
2/(n(n+2)) > 1/n^2 + 1/n^4 + 1/n^8 + ...
from which it follows that if each denominator is more than the square
of the preceeding one, then the sequence is greedy. The question is
whether the sum of an infinite greedy sequence can ever be rational.
(Of course, I haven't shown that this is a *sufficient condition* for
greed, but merely a necessary condition. Thus, there could be greedy
sequences that do not satisfy the "quadratic condition".) This question
is answered in Irrationality of Quadratic Sums. Also, a method of
constructing fractions with arbitrarily long odd greedy expansions
with consecutive integer remainder numerators is presented in
Odd-Greedy Unit Fraction Expansions.
Return to MathPages Main Menu