The Greedy Algorithm

I started browsing a book by David Wells called The Penguin Book of Curious and Interesting Puzzles. The first book that I encountered by this author was Prime Numbers:  The Most Mysterious Figures in Math and it is a most interesting book. A brief biography at the start of the this Penguin book informs us that:

David Wells was born in 1940. He had the rare distinction of being a Cambridge scholar in mathematics and failing his degree. He subsequently trained as a teacher and, after working on computers and teaching machines, taught mathematics and science in a primary school and mathematics in secondary schools. He is still involved with education through writing and working with teachers. While at university he became British under-21 chess champion, and in the mIddle seventies was a game inventor, devising 'Guerilla' and 'Checkpoint Danger', a puzzle composer, and the puzzle editor of Games & Puzzles magazine. From 1981 to 1983 he published The Problem Solver, a magazine of mathematical problems for secondary pupils. He has published several books of problems and popular mathematics, including Can You Solve These? and Hidden Connections, Double Meanings, and also Russia and England, and the Transformations of European Culture. He has written The Penguin Dictionary of Curious and Interesting Numbers and The Penguin Dictionary of Curious and Interesting Geometry, and is currently writing a book on the nature, learning and teaching of mathematics.

One of the first topics he deals with is Egyptian Fractions which consist only of unit fractions, meaning fractions with a numerator of 1. For example, the Egyptians would have expressed the fraction \( \frac{7}{10} \) as \( \frac{1}{2}+ \frac{1}{5} \).

The author then asks the question: 

Can all proper fractions be expressed as the sum of unit fractions, without repetition? 

The answer is: 

Yes, as Fibonacci showed, also in his Liber Abaci, where he described what is now called the greedy algorithm. Subtract the largest possible unit fraction, then do the same again, and so on. Sylvester proved in 1880 that applying this greedy algorithm to the fraction \( \frac{p}{q} \), where \(p\) is less than \(q,\) produces a sequence of no more than \(p\) unit fractions.

The site CODESDOPE provides the Python code to generate an Egyptian fraction from an improper fraction. Here is the code, applied to the fraction \( \frac{5}{7} \), together with its output:

import math

unit_den_array = [0]*10

iter = 0

def gcd(a, b):

  c = a%b

  while(c > 0):

    a = b

    b = c

    c = a % b

  return b

def greedy_egyptian_fraction(num, den):

  global iter

  if(num == 1):

    #appending list unit_den_array

    iter = iter+1 # storing in unit_den_array from index 1 not 0

    unit_den_array[iter] = den

  else:

    unit_den = math.ceil(den/num)

    iter = iter+1

    unit_den_array[iter] = unit_den

    gcd_of_numbers = gcd((num*unit_den) - den, den*unit_den)

    greedy_egyptian_fraction(((num*unit_den) - den)//gcd_of_numbers, (den*unit_den)//gcd_of_numbers)

if __name__ == '__main__':

  greedy_egyptian_fraction(5, 7)

  for i in range(1, iter+1):

    print(unit_den_array[i])

2

5

70

There is a lot of code and the contrast with the amount of code needed for SageMath could not be more stark. Here is code required for SageMath to accomplish exactly the same task:

L=[]

n=5/7

while n>0:

    bottom=ceil(denominator(n)/numerator(n))

    L.append(bottom)

    n=n-1/bottom

print(L)

[2, 5, 70]

While I am inclined to become more proficient in the use of Python, I am at the same time aware of how much more SageMath is suited to performing mathematical tasks, as the example of Egyptian fractions illustrate. Why go through a painful Python procedure to generate an outcome that SageMath can achieve almost effortlessly. It took me a few minutes to generate the SageMath code but I'm sure I would have struggled for much longer if I had only Python code to rely on. Here is the permalink to SageMathCell.

As the CODESDOPE observes in Figure 1:

Figure 1

My SageMath algorithm has provided the first representation but not the second. The latter is preferable in one way because the maximum denominator is much smaller (21 versus 70). Another way to generate an Egyptian fraction is by determining the Engel expansion for the proper fraction. I posted about the Engel expansion on the 26th September 2016. For an explanation of what this expansion is all about, see Figure 2.

Figure 2

The algorithm I developed to generate the Engel expansion for any positive real number is shown below, using \( \frac{5}{7} \) as an example (permalink):

x=5/7

u=x

E=[1]

F=[]

product=1

sum=0

for i in [1..10]:

    if u==0:

        break

    else:

        a=ceil(1/u)

    u=u*a-1

    E.append(a)

    product=product*a

    sum+=1/product

    F.append(1/product)

print("Engel expansion is",E)

print("Fraction expression is",F)

Engel expansion is [1, 2, 3, 4, 7]

Fraction expression is [1/2, 1/6, 1/24, 1/168]

So additionally \( \frac{5}{7}= \frac{1}{2}+ \frac{1}{6}+ \frac{1}{24}+ \frac{1}{168} \). Interestingly, I discovered on this website about proper fractions of the form \( \frac{4}{n} \) and \( \frac{3}{n} \). To quote from the site:

In the 1940s, the mathematicians Paul Erdos and Ernst G. Straus conjectured that every fraction with numerator = 4 can be written as an Egyptian fraction sum with three terms. If you have found an example that appears to need more than three, can you find an alternative sum? Can you find a reason why it must work, or a counter-example - the conjecture isn't yet proved. It is proved for \( \frac{3}{n} \).

Testing this out on \( \frac{3}{7} \), we find an Egyptian fraction of \( \frac{1}{3}+ \frac{1}{11}+\frac{1}{231}\). I'm sure there's a lot more that can be said about Egyptian fractions but I'll finish up here and maybe return to the topic at a later date. Figure 3 shows how the Egyptians connected the senses with fractions that had powers of 2 as denominators.

Figure 3

It can be noted that \( \frac{1}{2}+\frac{1}{4}+\frac{1}{8}+\frac{1}{16}+\frac{1}{32}+\frac{1}{64}=\frac{63}{64}\)