WARNING: The text below provides a guidance for a Project Euler problem.

  • If you pride yourself in tackling problems entirely on your own, you are encouraged to exit this post right now.

  • If you are simply looking for a hint for the problem, please visit the »Project Euler’s official forum«. You may find some hints here, but if you don’t want your problem spoiled, scroll cautiously.

  • If you are looking for a readily available copy/paste answer, you will not find it here. All of the code snippets in the post have been stripped of some crucial lines (these are clearly marked). It is my aim that anyone able to replicate the answer based on such snippets will have to understand the solution conceptually. At that point, by virtue of learning something new, I believe he deserves it anyway.

  • Guidance for future problems will not be published before 100 people have solved the problem and there are at least two more recent problems.

Creative numbers

The problem asks us to sum up so-called creative numbers. Number is creative if, starting from list , any integer greater than one is reachable via sequence of steps of two types:

  • Remove from and substitute them by . (For example )
  • Remove any integer of the form from the list and substitute it by . (For example )

We need to get a better grasp on which numbers are creative. Well, for starters, any number that is not on the form cannot be creative, as we will get stuck in the beginning. So we consider only numbers of this form. What if both and are prime? In such case the only course of action available to us is:

and we are stuck again. What if the exponent is composite? Then we find ourselves able to reach:

What if the number we are taking power of is composite? Then we can reach:

After these simple observations we arrive at the claim that is the backbone of the whole problem.

Claim. Any number is reachable from , unless .
Proof. In case , we are stuck as the only reachable lists are . So let from now on . We may obtain:

By the following chain of steps we can grow our number in magnitude:

Eventually, we can reach, for any , some number where . Then we simply do:

whereupon we have reached .

Finally, the problem tasks us with finding (Where is if is creative and otherwise.) which is by the previous discussion equal to (Any with at least one of composite can be written as where is composite and prime.):

A straightforward implementation seems to be fast enough with PyPy3 runtime just below one second.

def solve(lim):
    sqrtlim = round(lim ** 0.5) + 1
    # primes, composites
    P, C = primes(sqrtlim), [False, False] + [True for _ in range(sqrtlim)]
    for p in P:
        C[p] = False
    result = set()
    # <REMOVED>
        if C[b]:
            cand, next_prime = b * b, 1
            while cand <= lim:
                # <REMOVED>
                next_prime += 1
    return sum(result)