Engel expansion! How did I overlook this in my previous investigations of how to generate Egyptian fractions? As I just finished including in that article, this technique was apparently known to Fibonacci, who also investigated the more well known greedy method for Egyptian fractions.

Anyway, my Egyptian fraction Python code now knows how to generate expansions of this type. If you run, e.g.,

egypt.py 7/17 engel

you will get the expansion

1/3 + 1/15 + 1/90 + 1/1530

where each denominator is a multiple of the previous one: \( 3 \), \( 3\times 5 \), \( 3\times 5\times 6 \), \( 3\times 5\times 6\times 17 \). By default it generates the standard expansion in which these multipliers \( 3, 5, 6, 17 \) are nondecreasing, but it can also generate infinitely many other expansions without this nondecreasing property, so the -a option should only be used in conjunction with -d or -l.




Comments:

leonardo_m:
2006-09-28T11:43:33Z

Nice. Few notes to the code:

When the user doesn't give any input, the program can show a tiny usage demo, that shows what the module is capable of (like your 7/17 engel example).

In singleSolution function the final return seems useless.

When Python 2.5 will be more widespread, the itemCounts function can be written like:

from collections import defaultdict
items = defaultdict(int)
for x in S: items[x] += 1

But now lot of people don't have Python 2.5 so your code is better.

This line:

yield reduce(operator.mul,[x**i for x,i in dd.items()],1)

Is probably better like this:

yield reduce(mul, (x**i for x,i in dd.iteritems()), 1)
11011110:
2006-09-28T14:00:14Z

Thanks. Note that I'm still running Python 2.3, so I can't use the comprehension without brackets.