One begins to wonder if...
Playing with more examples will make one wonder if one always gets a
final representation
, and one comes to realise that one particular approach (the '
greedy
' approach, first noted evidently by Fibonacci, 1202AD) stands out: something
rather special
and
fruitful
happens if one systematically determines the '?' substitutes by always chosing the '
first possible unit fraction
' (in the sense of what we did above). Here is the important, simple result:
Theorem
(the first step of the
greedy algorithm
). Let
a
and
b
be natural numbers with
(that's just to ensure that
lies between 0 and 1). If
a
divides
b
, then (trivially)
is already a unit fraction, otherwise

let
be the
nearest
unit fraction to
from below
(meaning:
, while
, for some natural number
n
, with
);
then the numerator of the fraction
( =
, which is, of course, positive)
is
smaller
than the numerator of the fraction
(in other words,
a >
> 0)
Proof. (It's simply a matter of dividing
b
by
a
, and
choosing
the remainder to be
positive
and
less
than
a
.)
Let
b
=
aq
+
r
, with quotient
q
and remainder
r
, chosen so that 0 <
r
<
a
. (The '
n
' of the theorem is simply the 'ceiling' (in Maple 'ceil') of
, which, since
, will be
.) Then
=
and the numerator
=
=
, the numerator of
. [end of proof]
Note these 'ceil' commands:
>
ceil(14/3);
>
ceil(1/(3/14));
>
ceil(1/(1/14));
>
We want a nice working procedure, and it is easy to make one if one just works up to it from an actual example.
If one started with (e.g.)
, it would already be a unit fraction (
), and so we want to cover that kind of thing... , but if we started with (e.g.)
(which lies between
and
) then we set:
+ (a bit extra) =
+
and define
(which we will use in place of
) and
by setting:
>
r[0] := 171/3391;
n[1] := ceil(1/r[0]);
>
We now define
, and from it,
, the denominator of the second unit fraction:
>
r[1]:= r[0]  1/n[1];
n[2]:= ceil(1/r[1]);
>
Thus far we then have
, and let's (unthinkingly) continue in the obvious manner:

define define
, and from it,
, the denominator of the third unit fraction

define
, and from it,
, the denominator of the fourth unit fraction
... until we find we've come to the end
>
r[2]:= r[1]  1/n[2];
n[3]:= ceil(1/r[2]);
>
r[3]:= r[2]  1/n[3];
n[4]:= ceil(1/r[3]);
>
r[4]:= r[3]  1/n[4];
n[5]:= ceil(1/r[4]);
>
r[5]:= r[4]  1/n[5];
n[6]:= ceil(1/r[5]);
Error, division by zero
>
Thus, the above led to
=
(with
, and )
That, clearly, is the point at which we STOP, since
is a
unit
fraction, and we see that we have
is:
>
1/n[1] + 1/n[2] + 1/n[3] + 1/n[4] + 1/n[5];
>
We now want Maple to
recognise
in a general setting that we have reached the stopping point... ; that's where the use of 'while' will come to our rescue. You've already seen that in other circumstances (gcd, binary, etc). It's clear that the
appropriate program lines
are these (with 'k' starting at 1):
r[k] := r[k1]  1/n[k];
n[k+1] := ceil(1/r[k]);
The above single case
may
be tidied up as follows (first note the use of Maple's (type, integer) command):
>
type(8.75, integer);
>
type(27/4, integer);
>
type(28/4, integer);
>
r[0] := 171/3391;
n[1] := ceil(1/r[0]);
for k while type(1/r[k1], integer) = false do
r[k] := r[k1]  1/n[k];
n[k+1] := ceil(1/r[k]);
od;
seq(1/n[m], m=1..k);
>
If we suppress the semicolons we will just see the unit fractions:
>
r[0] := 171/3391:
n[1] := ceil(1/r[0]):
for k while type(1/r[k1], integer) = false do
r[k]:= r[k1]  1/n[k]:
n[k+1]:= ceil(1/r[k]):
od:
seq(1/n[m], m=1..k);
>