## Table of Contents

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. \]

### Factorization

```
def factors(n):
n_ = n
max_d = int(n ** 0.5)
for d in range(2, max_d + 1):
if n_ < d:
break
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)
```

### Others

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:
break
else:
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.