## 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