Egyptian fractions in Python

Question

Here's my code for the Egyptian fraction written in Python. I need your feedback if there is any room for improvement.

def eg_fr(n, d):
    ls = []
    ls_str = []
    fraction = n / d
    total = 0
    for i in range(1, 1000):
        ls.append((1/i, str(1) + '/' + str(i)))
    for i in ls:
        while i[0] + total <= fraction:
            ls_str.append(i[1])
            total += i[0]
            if total >= fraction:
                break
    print('%s/%s = ' % (n, d), end='')
    for i in range(len(ls_str) - 1):
        print('', ls_str[i], '+ ', end='')
    print(ls_str[-1], end='')
    return ls_str


if __name__ == '__main__':
    eg_fr(7, 133)

Answer 1

Names

What should your code do? Neither your code (by good names) nor your documentation inside the code (docstrings) nor your question does state the task in detail. So I cannot tell if your code is delivering the right results (but I don't think it does). So fix your names, there is no need to save characters. The bigger the scope the better the names have to be. Also add some docstring with a more detailed description of the task the function tries to solve.

Correctness of the results

>>> _ = eg_fr(7, 133)
7/133 = 1/19
>>> _ = eg_fr(7, 132)
7/132 = 1/19

That surprises at least me. At least the print statement lies to me. there is no equality in the second expression

Functions returning values vs. I/O

>>> eg_fr(7, 133)
7/133 = 1/19
['1/19']

Functions usually should either return values and have no other side effects like print or they should do tasks with side effect and return nothing (None) or success/error codes only. Your function does both. Either call the function print_egypti... and remove the return value or do remove the print from inside the function.

I strongly suggest to do printing outside the algorithm to have a testable function that is not cluttering the output.

Printing

A single test is no test.

If you did

if __name__ == '__main__':
    eg_fr(7, 133)
    eg_fr(7, 132)

you would have noticed not only the interesting results but also that you missed a line feed.

Looping

In Python you never do

for i in range(len(something)):
    do(something[i])

You always do

for element in something:
    do(element)

in your case

for element in ls_str[:-1]:
    print('', element, '+ ', end='')

that is less error prone.

String concatenation

You do concatenate the string output via printing in a loop. Use join() here. Instead of

for element in ls_str[:-1]:
    print('', element, '+ ', end='')
print(ls_str[-1])

you do

print(' + '.join(ls_str))

Testability

As mentioned before we split algorithm from I/O to get a nice and testable function

def egyptian_fractions(nominator, denominator):
    # [...]

def print_egyptian_fractions(nominator, denominator):
    print('{}/{} = '.format(nominator, denominator), end='')
    print(' + '.join(egyptian_fractions(nominator, denominator)))

Go for purity

We squeeze out all stuff from the algorithm that does not belong there. That is the string representation and also the nominator which is always 1. The final algorithm shall return only a list of denominators.

The remaining algorithm is

def egyptian_fractions_(nominator, denominator):
    denominators = []
    fraction = nominator / denominator
    total = 0
    for i in range(1, 1000):
        while 1/i + total <= fraction:
            denominators.append(i)
            total += 1/i
            if total >= fraction:
                break
    return denominators

The fitting print function is

def print_egyptian_fractions(nominator, denominator):
    ls_str = ['1/' + str(e) for e in egyptian_fractions(nominator, denominator)]
    print('{}/{} = '.format(nominator, denominator), end='')
    print(' + '.join(ls_str))

Algorithm

Depending on your task, I cannot know for sure, your algorithm is erroneous and inefficient.

• You do prepare a lengthy fractions for a later test where you could calculate straightforward.
• you do prepare string representations where you could leave this to the output functions
• You limited yourself to a smallest fraction of 1/1000. Why?
• You use float numbers for calculation and testing inside your algorithm and will get precision errors

I should mention there is the module fractions that is providing fractional math. As this is an exercise we will try to do it by hand.

First we try to lay out the algorithm

1. We try to find the biggest fraction f that is smaller or equal to the given fraction g

2. We keep the denominator from the fraction f

3a. we subtract fraction f from the given fraction g to get the remainder

So far this is what you did, now the change

3b. we try to find a fractional expression for the remainder (nominator, denominator)

4. we repeat from step 1

For step 1 you did a simple loop testing to find the biggest fraction. We do it a little more advanced, we divide the given denominator by the given nominator to find the new egyptian denominator. We use integer division for that step to work without precision loss. If the remainder of this division is 0 we are done, if not we have to increment the new denominator.

For step 3 we do some basic math to do the subtraction with the help of a common denominator to avoid precision loss and stick to a nominator/denominator fraction format.

What do we do for step 4? the task is the very same - solve the same problem for a new pair of nominator/denominator. We do a simple recursion and call the same function again appending that result to that from the current recursion depth.

def egyptian_fractions(nominator, denominator):
    if nominator == 1:
        return [denominator]    # exactly fitting fraction (was normalized)
    else:
        d = denominator // nominator
        r = denominator % nominator
        if r == 0:
            return [d]          # exactly fitting fraction (wasn't normalized)
        else:
            d += 1              # increment to get the biggest fitting fraction
                                # keep the result and add the result of the subproblem
            return [d] + egyptian_fractions(nominator*d-denominator, denominator*d)

Answer 2

Code readability and style

---

You should use f-strings -

To create an f-string, prefix the string with the letter “ f ”. The string itself can be formatted in much the same way that you would with str.format(). f-strings provide a concise and convenient way to embed python expressions inside string literals for formatting.

Which means, instead of using the outdated way of formatting strings -

print('%s/%s = ' % (n, d), end='')

You can make it more concise -

print(f'{n}/{d} = ', end='')

Here, this -

 print('', ls_str[i], '+ ', end='')

could be written as -

print(f'{ls_str[i]} + ', end='')

NOTE - Requires Python 3.6 and above.

If you don't have Python 3.6 and above, you could use str.format() -

str.format() is one of the string formatting methods in Python 3, which allows multiple substitutions and value formatting. This method lets us concatenate elements within a string through positional formatting.

So you could write it like this -

print('{}/{} = '.format(n, d), end='')

And -

print('{} + '.format(ls_str[i]), end='')

---

You should have a more descriptive name for your function, so it that it is easy to figure out what your program does, like this -

def egyptian_fraction(n, d):

The same would go for variable names -

ls = []

could be -

fraction_list = []

And -

ls_str = []

could just be -

list_str = []

since it does not affect Python's inbuilt list() function.

---

So, overall, your code would then look like this (in terms of code readability and style) -

def egyptian_fraction(n, d):
    fraction_list = []
    list_str = []
    fraction = n / d
    total = 0
    for i in range(1, 1000):
        fraction_list.append((1/i, str(1) + '/' + str(i)))
    for i in fraction_list:
        while i[0] + total <= fraction:
            list_str.append(i[1])
            total += i[0]
            if total >= fraction:
                break
    print(f'{n}/{d} = ', end='')
    for i in range(len(list_str) - 1):
        print(f'{list_str[i]} + ', end='')
    print(list_str[-1], end='')
    return list_str


if __name__ == '__main__':
    egyptian_fraction(7, 133)

---

Also, good use of the if __name__ == __'main__': guard. Most people don't even attempt to use it.

---

To remain concise and immaculate in writing Python programs, I suggest you have a look at PEP 8, which is Python's official style guide.

Hope this helps!