Finding Egyptian fractions with A* search I've written an A* search to find the optimal solution to the equation

$$ \dfrac{4}{n} = \dfrac{1}{x} + \dfrac{1}{y} + \dfrac{1}{z} $$

with \$n, x, y, z\$ positive integers, and \$n\$ given; the optimal solution being the one with smallest sum \$ x + y + z \$.

(The Erdős–Straus conjecture states that there are solutions to this equation for all \$n&gt;2\$.)

My working version:

def evaluate(option):
    return sum(option)


def generate_options(option):
    def option_valid(o):
        prev = o[0]
        for el in o[1:]:
            if el &lt; prev:
                return False
            prev = el
        return True

    x, y, z = option
    opt = (x + 1, y, z)
    if option_valid(opt): yield opt
    opt = (x, y + 1, z)
    if option_valid(opt): yield opt
    opt = (x, y, z + 1)
    if option_valid(opt): yield opt


def is_solution(current, n):
    x, y, z = current
    if (4 / n) == (1 / x + 1 / y + 1 / z):
        return True
    return False


def A(option, generate_options, evaluate, is_solution):
    done = set()
    paths = PriorityQueue()
    paths.put((evaluate(option), option))
    done.add(option)
    while not paths.empty():
        price, current = paths.get()
        if is_solution(current):
            return price, current
        for gp in generate_options(current):
            if gp not in done:
                done.add(gp)
                paths.put((evaluate(gp), gp))
    return None


def main():
    def solution(x):
        return is_solution(x, n=18)

    print(A(
        (1, 1, 1),
        generate_options=generate_options,
        evaluate=evaluate,
        is_solution=solution))


The problem I see with this code would be that since I store all the checked solutions into a set, I could potentially run out of memory for an \$n\$ that would require a large amount of checked options. In my mind, I could fix this by clearing the entire set every \$m\$ iterations, but that could lead back to some options being checked more than once.

I'm fairly new to Python, and I also wonder if there's a better way to write my generate_options function. I do know there was no need to make it into a generator, but I did it that way for the sake of seeing how they work.
There's a bug in is_solution:

&gt;&gt;&gt; is_solution((2, 3, 6), 4)
False


even though $$ {1\over2} + {1\over3} + {1\over6} = 1 = {4\over4}. $$

This is because \${1\over3}\$ and \${1\over6}\$ can't be exactly represented as floating-point numbers:

&gt;&gt;&gt; 1/2 + 1/3 + 1/6
0.9999999999999999


The way to solve this is to represent fractions using the fractions.Fraction class:

&gt;&gt;&gt; Fraction(1, 2) + Fraction(1, 3) + Fraction(1, 6) == Fraction(4, 4)
True

The question claims the algorithm is "A*", but that's not true. The A* search algorithm tries to find the least-cost path to an identifiable goal in a directed graph. But here you can't identify the goal (because you're looking for a minimum, you won't know what it is until the search is complete), and you don't care about the cost of the path taken to get there.

It would be better to call the algorithm "best-first search".
You're basically searching over all triples of integers looking for one that happens to add up to your target. This is a waste of time, because after you've picked \$y\$ and \$z\$, say, then you can know that $$ x = {1 \over {4\over n} - {1\over y} - {1\over z}} $$ and all you have to do is compute this and check that it's an integer.

So a (slightly) better strategy looks like this:

from collections import namedtuple
from fractions import Fraction
from itertools import chain, count, takewhile
from math import floor

Triple = namedtuple('Triple', 'x y z')

def egyptian_triples(n):
    """All solutions to 1/x + 1/y + 1/z = 4/n in lexicographic order."""
    tz = Fraction(4, n)
    for z in count(floor(1 / tz) + 1):
        ty = tz - Fraction(1, z)
        for y in range(floor(1 / ty) + 1, z + 1):
            tx = ty - Fraction(1, y)
            if tx.numerator == 1 and tx.denominator &lt;= y:
                yield Triple(tx.denominator, y, z)

def min_egyptian_triple(n):
    """Return the solution to 1/x + 1/y + 1/z = 4/n with minimum x + y + z."""
    triples = egyptian_triples(n)

    # First solution in lexicographic order.
    first = next(triples)
    max_z = sum(first) - 2

    # Return minimum solution.
    return min(chain((first,), takewhile(lambda t: t.z &lt;= max_z, triples)),
               key=sum)


This is substantially faster:

&gt;&gt;&gt; from timeit import timeit
&gt;&gt;&gt; timeit(lambda:main(115), number=1)
(290, (60, 92, 138))
19.941934717004187
&gt;&gt;&gt; timeit(lambda:print(min_egyptian_triple(115)), number=1)
Triple(x=60, y=92, z=138)
0.46365413605235517