Project Euler 1-100 in 49 hours

20 January 2021

Project Euler is how I taught myself Python in high school, and so I find it incredibly nostalgic. It took 13-year-old me a lot of Googling and a few months to get through the first 100 problems. Why 100 specifically? Because I wanted to write this post honestly and those are the ones I’m allowed to talk about without them locking my account or something.

10-odd years and a graduate degree later, I decided to come back and solve them as fast as I could. I’m no competitive programmer, but 24 hours seemed reasonable. Fortunately, I lack the stamina to code for that long, so I did it over a few days instead. I started on 19 January a little after 1400 and finished two days later at 1500, and probably spent less than half of that time coding, but who knows.

How this was possible in the first place

Having solved them all before helped a lot — otherwise I wouldn’t be sure this was possible to do quickly at all. Problems after 100 tend to very quickly become about number theory; I’ve solved more than one by appeal to my copy of Hardy and Wright.

I wrote my solutions in Python, as before. Having just done Advent of Code in plain C, I came to miss my dictionaries, lists, and not having to write unsigned long long everywhere.

Useful things from my graduate algorithms class

Problem 67 was how I learned about dynamic programming in high school.

Utility algorithms

If you’re trying this in another language, these are the things I would implement first.

Converting between a number and its digits

def digits(n):
    return [int(d) for d in str(n)]

def from_digits(digits):
    return int(''.join(str(d) for d in digits))

Euclid’s GCD algorithm

def gcd(a, b):
    return a if b == 0 else gcd(b, a % b)

Primality testing

def is_prime(n):
    if n < 2:
        return False
    max_d = int(n ** 0.5)
    for d in range(2, max_d + 1):
        if n % d == 0:
            return False
    return True

Sieve of Eratosthenes

def sieve(max_n):
    sv = [None for n in range(max_n + 1)]
    sv[0] = False
    sv[1] = False

    max_p = int(max_n ** 0.5)
    for p in range(2, max_p + 1):
        if sv[p] is None:
            sv[p] = True
        for c in range(p * p, max_n + 1, p):
            sv[c] = False
    for p in range(max_p + 1, max_n + 1):
        if sv[p] is None:
            sv[p] = True

    return sv

Sieving other things was also appropriate; for instance, Euler’s totient function, in view of the identity \[ \varphi(n) = n \cdot \prod_{\substack{p \mid n}} \frac{p-1}p. \]


def factors(n):
    n_ = n
    max_d = int(n ** 0.5)
    for d in range(2, max_d + 1):
        if n_ < d:
        if is_prime(d) and n_ % d == 0:
            mult = 0
            while n_ % d == 0:
                n_ //= d
                mult += 1
            yield (d, mult)
    if n_ > 1:
        yield (n_, 1)

Generating Pythagorean triples

They really like their Pythagorean triples at Project Euler. The code below generates all the primitive triples \((a, b, c)\) with \(c\) less than a provided bound, then their multiples.

def pyth(max_c):
    max_m = int((max_c / 2) ** 0.5)

    for m in range(1, max_m + 1):
        for n in range(1, m):
            a = m * m - n * n
            b = 2 * m * n
            c = m * m + n * n
            max_k = max_c // c
            for k in range(1, max_k + 1):
                yield (k * a, k * b, k * c)


The extended Euclidean algorithm, which is convenient for generating modular inverses for something like the Chinese Remainder Theorem (which wasn’t necessary here, but definitely is later on.)

Generating continued fractions, particularly of quadratic surds.

For later problems, a fast primality test is a good idea. Here’s the Miller-Rabin test:

def is_probably_prime(n, witnesses=None):
    if n < 2:
        return False

    if not witnesses:
        witnesses = [2, 3, 5, 7, 11, 13, 17]

    if n in witnesses:
        return True

    odd_divisor = n - 1
    power_of_two = 0
    while odd_divisor & 1 == 0:
        power_of_two += 1
        odd_divisor //= 2

    for witness in witnesses:
        x = pow(witness, odd_divisor, n)
        if x not in [1, n - 1]:
            for _ in range(power_of_two - 1):
                x = (x * x) % n
                if x == n - 1:
                return False
    return True

This is valid up to about \(n = 3.4 \times 10^{14},\) which exceeds most of the answer bounds in early problems. Using the witness set \(\{2, 7, 61\}\) may provide a slight speed boost, but if you’re hyperoptimizing your solutions like that this post probably isn’t for you.