as 
. (In point of fact, the Egyptians also had a symbol for
the fraction 
but to keep things simple this will be ignored.)
It should be noted that not all fractions have a unique Egyptian
representations. One way of obtaining an Egyptian representation of a fraction
is known as the Greedy Algorithm. This algorithm simply adds to the
sum so far the largest possible unit fraction which does not make
the sume exceed the given fraction.
For example, to find the Egyptian represention of note
that 
but 
so start with 
. Then consider 
. Note that 
but that
. Hence the second term provided by
the Greedy Algorith is 
. Next, consider 
. The Greedy Algorithm
therefore yields 
.
Implement the Greedy Algorithm in a procedure which calculates the
Egyptian representation of any function. In order to do this, consider
the problem of finding the largest fraction with unit numerator less
than or equal to 
. Find an efficient way of doing this
with the Maple function ceil. A good strategy for your procedure
would be to use recursion. One way of doing this is to define a
procedure, which we will call Egyptian, which takes two inputs. The
first input is a list of the fractions obtained so far by the Greedy
Algorithm and the second variable is the fraction to be represented.
So, for example, to find the representation of you would
type Egyptian([],3/7) and the output would be the list
.
What Egyptian representation does your procedure yield for the
fraction 
Does the Greedy Algorithm always yield the
shortest possible Egyptian
represenation of a fraction? Does it always yield the smallest
denominators? One way of getting other representations for a fraction
such as is to first split it as a sum -- for
example,
. Write a
procedure wich finds the Egyptian decompositions for
using the Greedy Algorithm for both sides of the sum 
where A+ B = 65 and both A and B are positive.
A question which has not been addressed is why the Greedy Algorithm is
guaranteed to stop. Might there not be a fraction which results in the
Greedy Algorithm computing an infinite sequence of increasingly
smaller fractions with unit numerator? The negative answer to this
question was established by Fibonacci in 1202. How did he prove this?
To provide at least a partial answer to this question, write a
procedure which calculates the remainders of each step of the
Greedy Algorithm and apply it to various fractions. You should be able to
arrive at a conjecture about the behaviour of the sequence of
numerators of these remainders. If this conjecture were true, how
could it be used to establish Finonacci's theorem on the the Greedy
Algorithm? Can you provide a proof of your conjecture and thereby
prove Finonacci's theorem?
