Computing Egyptian fractions

The ancient Egyptians expressed all fractions as sums of fractions with unit numerators. For example, they might express tex2html_wrap_inline90 as tex2html_wrap_inline92. (In point of fact, the Egyptians also had a symbol for the fraction tex2html_wrap_inline94 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 tex2html_wrap_inline90 note that tex2html_wrap_inline98 but tex2html_wrap_inline100 so start with tex2html_wrap_inline102. Then consider tex2html_wrap_inline104. Note that tex2html_wrap_inline106 but that tex2html_wrap_inline108. Hence the second term provided by the Greedy Algorith is tex2html_wrap_inline110. Next, consider tex2html_wrap_inline112. The Greedy Algorithm therefore yields tex2html_wrap_inline114.

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 tex2html_wrap_inline116. 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 tex2html_wrap_inline90 you would type Egyptian([],3/7) and the output would be the list tex2html_wrap_inline120.

What Egyptian representation does your procedure yield for the fraction tex2html_wrap_inline122 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 tex2html_wrap_inline122 is to first split it as a sum -- for example, tex2html_wrap_inline126. Write a procedure wich finds the Egyptian decompositions for tex2html_wrap_inline122 using the Greedy Algorithm for both sides of the sum tex2html_wrap_inline130 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?


Juris Steprans
email address:
Department of Mathematics and Statistics.
Ross 536 North, ext. 33921
York University
Back to Department's Public Page