{ "cells": [ { "cell_type": "markdown", "id": "cell-002", "metadata": {}, "source": [ "
code and commentary by Claude Fable 5
July 2026
\n", "\n", "# Project Euler 1–100: Claude Fable 5 Edition\n", "\n", "This notebook is a companion to [Euler.ipynb](Euler.ipynb) (Peter Norvig's solutions, which include commentary) and\n", "[Euler-Opus.ipynb](Euler-Opus.ipynb) (an AI edition by Claude Opus 4.8). The brief for this edition, written by Claude Fable 5: solve\n", "Project Euler problems 1–100 with **every solution running in under one second**. The whole\n", "notebook runs in about two seconds. Getting there is mostly about algorithms, not\n", "micro-optimization:\n", "\n", "- **Sieves over tests**: bulk primality and divisor-sum questions use numpy sieves; individual\n", " queries use deterministic Miller-Rabin.\n", "- **Count classes, not instances**: several problems (74, 92) group the numbers below ten\n", " million by digit multiset, shrinking 10,000,000 cases to about 10,000.\n", "- **Exact math over search or simulation**: closed forms (1, 6, 28), Pell equations (66, 94),\n", " a Markov chain rather than a Monte Carlo simulation (84), and the totient summatory\n", " recurrence (72).\n", "- **Prune the search space first**: mod-3 classes cut the prime-pair graph in half (60);\n", " divisibility chains the pandigital construction (43).\n", "\n", "Each solution is a function `euler_N()` that returns the answer; `run(euler_N)` checks it\n", "against the expected answer and records the run time. Data files and the harness live in\n", "[euler_data.py](euler_data.py)." ] }, { "cell_type": "code", "execution_count": 1, "id": "cell-001", "metadata": {}, "outputs": [], "source": [ "from euler_data import DATA, run, runs" ] }, { "cell_type": "markdown", "id": "cell-003", "metadata": {}, "source": [ "## Setup" ] }, { "cell_type": "code", "execution_count": 2, "id": "cell-004", "metadata": {}, "outputs": [], "source": [ "\"\"\"Utility functions shared by the solutions.\n", "\n", "The goal throughout is speed: every problem should run in well under a\n", "second. Numpy handles sieves and other bulk array work; a deterministic\n", "Miller-Rabin test handles individual primality queries.\n", "\"\"\"\n", "\n", "from collections import Counter, defaultdict\n", "from datetime import date\n", "from fractions import Fraction\n", "from functools import lru_cache\n", "from itertools import combinations, combinations_with_replacement, count, permutations\n", "from math import comb, factorial, gcd, inf, isqrt, lcm, log, prodtw\n", "import heapq\n", "\n", "import numpy as np\n", "\n", "\n", "def prime_sieve(n):\n", " \"\"\"Numpy boolean array where sieve[i] is True iff i is prime (0 <= i <= n).\"\"\"\n", " sieve = np.ones(n + 1, dtype=bool)\n", " sieve[:2] = False\n", " for i in range(2, isqrt(n) + 1):\n", " if sieve[i]:\n", " sieve[i * i::i] = False\n", " return sieve\n", "\n", "\n", "def primes_upto(n):\n", " \"\"\"List of all primes <= n.\"\"\"\n", " return np.flatnonzero(prime_sieve(n)).tolist()\n", "\n", "\n", "def is_prime(n) -> bool:\n", " \"\"\"Deterministic Miller-Rabin primality test.\"\"\"\n", " if n < 2:\n", " return False\n", " for p in (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37):\n", " if n % p == 0:\n", " return n == p\n", " if n < 41 * 41:\n", " return True\n", " bases = (2, 3, 5, 7) if n < 3_215_031_751 else (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37)\n", " d, r = n - 1, 0\n", " while d % 2 == 0:\n", " d, r = d // 2, r + 1\n", " for a in bases:\n", " x = pow(a, d, n)\n", " if x == 1 or x == n - 1:\n", " continue\n", " for _ in range(r - 1):\n", " x = x * x % n\n", " if x == n - 1:\n", " break\n", " else:\n", " return False\n", " return True\n", "\n", "\n", "def factorize(n):\n", " \"\"\"Prime factorization of n as a dict of {prime: exponent}.\"\"\"\n", " f = {}\n", " while n % 2 == 0:\n", " f[2] = f.get(2, 0) + 1\n", " n //= 2\n", " p = 3\n", " while p * p <= n:\n", " while n % p == 0:\n", " f[p] = f.get(p, 0) + 1\n", " n //= p\n", " p += 2\n", " if n > 1:\n", " f[n] = f.get(n, 0) + 1\n", " return f\n", "\n", "\n", "def num_divisors(n):\n", " \"\"\"d(n): the number of divisors of n.\"\"\"\n", " return prod(e + 1 for e in factorize(n).values())\n", "\n", "\n", "def sum_divisors(n):\n", " \"\"\"sigma(n): the sum of all divisors of n (including n).\"\"\"\n", " return prod((p ** (e + 1) - 1) // (p - 1) for p, e in factorize(n).items())\n", "\n", "\n", "def proper_divisor_sum(n):\n", " \"\"\"Sum of the proper divisors of n (excluding n itself).\"\"\"\n", " return sum_divisors(n) - n\n", "\n", "\n", "def divisor_sum_sieve(n):\n", " \"\"\"Numpy array s where s[i] = sum of the proper divisors of i (0 <= i <= n).\"\"\"\n", " s = np.zeros(n + 1, dtype=np.int64)\n", " for d in range(1, isqrt(n) + 1):\n", " k = np.arange(d, n // d + 1) # cofactors of d, so that d*k <= n\n", " s[d * k] += d + k # add the divisor pair (d, k) to d*k\n", " s[d * d] -= d # d*d got d added twice just above\n", " return s - np.arange(n + 1) # make it proper: remove i itself\n", "\n", "\n", "def digit_sum(n):\n", " \"\"\"Sum of the decimal digits of n.\"\"\"\n", " return sum(map(int, str(n)))\n", "\n", "\n", "def is_palindrome(n):\n", " \"\"\"Does n (or its string form) read the same forward and backward?\"\"\"\n", " s = str(n)\n", " return s == s[::-1]\n", "\n", "\n", "def is_permutation(a, b):\n", " \"\"\"Are a and b digit-permutations of each other?\"\"\"\n", " return sorted(str(a)) == sorted(str(b))\n", "\n", "\n", "def read_matrix(text):\n", " \"\"\"Parse a grid of numbers (comma- or space-separated) into a list of rows.\"\"\"\n", " return [[int(x) for x in line.replace(',', ' ').split()]\n", " for line in text.strip().splitlines()]\n", "\n", "\n", "def max_path(rows):\n", " \"\"\"Maximum top-to-bottom path sum in a triangle of numbers.\"\"\"\n", " dp = rows[-1][:]\n", " for row in reversed(rows[:-1]):\n", " dp = [x + max(a, b) for x, a, b in zip(row, dp, dp[1:])]\n", " return dp[0]\n", "\n", "\n", "def triangle(n): return n * (n + 1) // 2\n", "def pentagon(n): return n * (3 * n - 1) // 2\n", "def hexagon(n): return n * (2 * n - 1)\n", "\n", "\n", "def is_pentagonal(p):\n", " \"\"\"Is p a pentagonal number?\"\"\"\n", " r = isqrt(24 * p + 1)\n", " return r * r == 24 * p + 1 and r % 6 == 5" ] }, { "cell_type": "markdown", "id": "cell-005", "metadata": {}, "source": [ "## [Problem 1](https://projecteuler.net/problem=1)\n", "\n", "*Closed-form arithmetic series with inclusion-exclusion: no loop needed.*" ] }, { "cell_type": "code", "execution_count": 3, "id": "cell-006", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 1: Multiples of 3 or 5 0 msec ⇒ 233168 ✅ " ] }, "execution_count": 3, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_1():\n", " \"\"\"Multiples of 3 or 5\"\"\"\n", " def multiples_sum(k, limit=999):\n", " m = limit // k\n", " return k * m * (m + 1) // 2\n", " return multiples_sum(3) + multiples_sum(5) - multiples_sum(15)\n", "\n", "\n", "run(euler_1)" ] }, { "cell_type": "markdown", "id": "cell-007", "metadata": {}, "source": [ "## [Problem 2](https://projecteuler.net/problem=2)\n", "\n", "*Iterate the Fibonacci sequence, summing the even terms.*" ] }, { "cell_type": "code", "execution_count": 4, "id": "cell-008", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 2: Even Fibonacci Numbers 0 msec ⇒ 4613732 ✅ " ] }, "execution_count": 4, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_2():\n", " \"\"\"Even Fibonacci Numbers\"\"\"\n", " total, a, b = 0, 1, 2\n", " while b <= 4_000_000:\n", " if b % 2 == 0:\n", " total += b\n", " a, b = b, a + b\n", " return total\n", "\n", "\n", "run(euler_2)" ] }, { "cell_type": "markdown", "id": "cell-009", "metadata": {}, "source": [ "## [Problem 3](https://projecteuler.net/problem=3)\n", "\n", "*Trial-division factorization; the answer is the largest prime found.*" ] }, { "cell_type": "code", "execution_count": 5, "id": "cell-010", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 3: Largest Prime Factor 0 msec ⇒ 6857 ✅ " ] }, "execution_count": 5, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_3():\n", " \"\"\"Largest Prime Factor\"\"\"\n", " return max(factorize(600851475143))\n", "\n", "\n", "run(euler_3)" ] }, { "cell_type": "markdown", "id": "cell-011", "metadata": {}, "source": [ "## [Problem 4](https://projecteuler.net/problem=4)\n", "\n", "*Descending double loop with early breaks once no product can beat the best.*" ] }, { "cell_type": "code", "execution_count": 6, "id": "cell-012", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 4: Largest Palindrome Product 0 msec ⇒ 906609 ✅ " ] }, "execution_count": 6, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_4():\n", " \"\"\"Largest Palindrome Product\"\"\"\n", " best = 0\n", " for a in range(999, 99, -1):\n", " if a * 999 <= best:\n", " break\n", " for b in range(999, a - 1, -1):\n", " p = a * b\n", " if p <= best:\n", " break\n", " if is_palindrome(p):\n", " best = p\n", " return best\n", "\n", "\n", "run(euler_4)" ] }, { "cell_type": "markdown", "id": "cell-013", "metadata": {}, "source": [ "## [Problem 5](https://projecteuler.net/problem=5)\n", "\n", "*The answer is exactly lcm(1..20).*" ] }, { "cell_type": "code", "execution_count": 7, "id": "cell-014", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 5: Smallest Multiple 0 msec ⇒ 232792560 ✅ " ] }, "execution_count": 7, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_5():\n", " \"\"\"Smallest Multiple\"\"\"\n", " return lcm(*range(1, 21))\n", "\n", "\n", "run(euler_5)" ] }, { "cell_type": "markdown", "id": "cell-015", "metadata": {}, "source": [ "## [Problem 6](https://projecteuler.net/problem=6)\n", "\n", "*Closed forms for the sum and the sum of squares.*" ] }, { "cell_type": "code", "execution_count": 8, "id": "cell-016", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 6: Sum Square Difference 0 msec ⇒ 25164150 ✅ " ] }, "execution_count": 8, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_6():\n", " \"\"\"Sum Square Difference\"\"\"\n", " n = 100\n", " return (n * (n + 1) // 2) ** 2 - n * (n + 1) * (2 * n + 1) // 6\n", "\n", "\n", "run(euler_6)" ] }, { "cell_type": "markdown", "id": "cell-017", "metadata": {}, "source": [ "## [Problem 7](https://projecteuler.net/problem=7)\n", "\n", "*Sieve a comfortable upper bound and index into the list of primes.*" ] }, { "cell_type": "code", "execution_count": 9, "id": "cell-018", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 7: 10001st Prime 1 msec ⇒ 104743 ✅ " ] }, "execution_count": 9, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_7():\n", " \"\"\"10001st Prime\"\"\"\n", " return primes_upto(120_000)[10_000]\n", "\n", "\n", "run(euler_7)" ] }, { "cell_type": "markdown", "id": "cell-019", "metadata": {}, "source": [ "## [Problem 8](https://projecteuler.net/problem=8)\n", "\n", "*Slide a window of 13 digits across the series, taking the max product.*" ] }, { "cell_type": "code", "execution_count": 10, "id": "cell-020", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 8: Largest Product in a Series 0 msec ⇒ 23514624000 ✅ " ] }, "execution_count": 10, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_8():\n", " \"\"\"Largest Product in a Series\"\"\"\n", " digits = [int(c) for c in ''.join(DATA[8].split())]\n", " return max(prod(digits[i:i + 13]) for i in range(len(digits) - 12))\n", "\n", "\n", "run(euler_8)" ] }, { "cell_type": "markdown", "id": "cell-021", "metadata": {}, "source": [ "## [Problem 9](https://projecteuler.net/problem=9)\n", "\n", "*Loop over a and b; c is determined by the perimeter.*" ] }, { "cell_type": "code", "execution_count": 11, "id": "cell-022", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 9: Special Pythagorean Triplet 4 msec ⇒ 31875000 ✅ " ] }, "execution_count": 11, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_9():\n", " \"\"\"Special Pythagorean Triplet\"\"\"\n", " for a in range(1, 333):\n", " for b in range(a + 1, (1000 - a) // 2):\n", " c = 1000 - a - b\n", " if a * a + b * b == c * c:\n", " return a * b * c\n", "\n", "\n", "run(euler_9)" ] }, { "cell_type": "markdown", "id": "cell-023", "metadata": {}, "source": [ "## [Problem 10](https://projecteuler.net/problem=10)\n", "\n", "*Numpy sieve of Eratosthenes; sum the surviving indexes.*" ] }, { "cell_type": "code", "execution_count": 12, "id": "cell-024", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 10: Summation of Primes 4 msec ⇒ 142913828922 ✅ " ] }, "execution_count": 12, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_10():\n", " \"\"\"Summation of Primes\"\"\"\n", " return int(np.flatnonzero(prime_sieve(2_000_000)).sum())\n", "\n", "\n", "run(euler_10)" ] }, { "cell_type": "markdown", "id": "cell-025", "metadata": {}, "source": [ "## [Problem 11](https://projecteuler.net/problem=11)\n", "\n", "*Check the product of 4 in a row in each of the 4 directions from every cell.*" ] }, { "cell_type": "code", "execution_count": 13, "id": "cell-026", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 11: Largest Product in a Grid 0 msec ⇒ 70600674 ✅ " ] }, "execution_count": 13, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_11():\n", " \"\"\"Largest Product in a Grid\"\"\"\n", " g = read_matrix(DATA[11])\n", " best = 0\n", " for r in range(20):\n", " for c in range(20):\n", " for dr, dc in ((0, 1), (1, 0), (1, 1), (1, -1)):\n", " if 0 <= r + 3 * dr < 20 and 0 <= c + 3 * dc < 20:\n", " best = max(best, prod(g[r + i * dr][c + i * dc] for i in range(4)))\n", " return best\n", "\n", "\n", "run(euler_11)" ] }, { "cell_type": "markdown", "id": "cell-027", "metadata": {}, "source": [ "## [Problem 12](https://projecteuler.net/problem=12)\n", "\n", "*triangle(n) = n(n+1)/2 splits into two coprime halves, so d(a*b) = d(a)*d(b).*" ] }, { "cell_type": "code", "execution_count": 14, "id": "cell-028", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 12: Highly Divisible Triangular Number 27 msec ⇒ 76576500 ✅ " ] }, "execution_count": 14, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_12():\n", " \"\"\"Highly Divisible Triangular Number\"\"\"\n", " for n in count(2):\n", " a, b = (n // 2, n + 1) if n % 2 == 0 else (n, (n + 1) // 2)\n", " if num_divisors(a) * num_divisors(b) > 500:\n", " return a * b\n", "\n", "\n", "run(euler_12)" ] }, { "cell_type": "markdown", "id": "cell-029", "metadata": {}, "source": [ "## [Problem 13](https://projecteuler.net/problem=13)\n", "\n", "*Python big ints make this a one-liner.*" ] }, { "cell_type": "code", "execution_count": 15, "id": "cell-030", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 13: Large Sum 0 msec ⇒ 5537376230 ✅ " ] }, "execution_count": 15, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_13():\n", " \"\"\"Large Sum\"\"\"\n", " return int(str(sum(int(line) for line in DATA[13].split()))[:10])\n", "\n", "\n", "run(euler_13)" ] }, { "cell_type": "markdown", "id": "cell-031", "metadata": {}, "source": [ "## [Problem 14](https://projecteuler.net/problem=14)\n", "\n", "*Chain lengths for even n cost O(1); odd n walk down to a smaller cached value.*" ] }, { "cell_type": "code", "execution_count": 16, "id": "cell-032", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 14: Longest Collatz Sequence 192 msec ⇒ 837799 ✅ " ] }, "execution_count": 16, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_14():\n", " \"\"\"Longest Collatz Sequence\"\"\"\n", " N = 1_000_000\n", " L = [0] * N\n", " L[1] = 1\n", " best_n, best = 1, 1\n", " for n in range(2, N):\n", " if n & 1:\n", " m, steps = (3 * n + 1) >> 1, 2\n", " while m >= n: # walk until below n (already cached)\n", " if m & 1:\n", " m, steps = (3 * m + 1) >> 1, steps + 2\n", " else:\n", " m, steps = m >> 1, steps + 1\n", " v = L[m] + steps\n", " else:\n", " v = L[n >> 1] + 1\n", " L[n] = v\n", " if v > best:\n", " best_n, best = n, v\n", " return best_n\n", "\n", "\n", "run(euler_14)" ] }, { "cell_type": "markdown", "id": "cell-033", "metadata": {}, "source": [ "## [Problem 15](https://projecteuler.net/problem=15)\n", "\n", "*The paths are exactly the ways to arrange 20 rights and 20 downs: C(40, 20).*" ] }, { "cell_type": "code", "execution_count": 17, "id": "cell-034", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 15: Lattice Paths 0 msec ⇒ 137846528820 ✅ " ] }, "execution_count": 17, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_15():\n", " \"\"\"Lattice Paths\"\"\"\n", " return comb(40, 20)\n", "\n", "\n", "run(euler_15)" ] }, { "cell_type": "markdown", "id": "cell-035", "metadata": {}, "source": [ "## [Problem 16](https://projecteuler.net/problem=16)\n", "\n", "*Python big ints again.*" ] }, { "cell_type": "code", "execution_count": 18, "id": "cell-036", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 16: Power Digit Sum 0 msec ⇒ 1366 ✅ " ] }, "execution_count": 18, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_16():\n", " \"\"\"Power Digit Sum\"\"\"\n", " return digit_sum(2 ** 1000)\n", "\n", "\n", "run(euler_16)" ] }, { "cell_type": "markdown", "id": "cell-037", "metadata": {}, "source": [ "## [Problem 17](https://projecteuler.net/problem=17)\n", "\n", "*Table of letter counts for the number words; assemble counts positionally.*" ] }, { "cell_type": "code", "execution_count": 19, "id": "cell-038", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 17: Number Letter Counts 0 msec ⇒ 21124 ✅ " ] }, "execution_count": 19, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_17():\n", " \"\"\"Number Letter Counts\"\"\"\n", " ones = [0, 3, 3, 5, 4, 4, 3, 5, 5, 4, # zero .. nine\n", " 3, 6, 6, 8, 8, 7, 7, 9, 8, 8] # ten .. nineteen\n", " tens = [0, 0, 6, 6, 5, 5, 5, 7, 6, 6] # -, -, twenty .. ninety\n", " def letters(n):\n", " if n == 1000:\n", " return 3 + 8 # \"one\" + \"thousand\"\n", " h, r = divmod(n, 100)\n", " total = ones[h] + 7 + (3 if r else 0) if h else 0 # \"hundred\" (+ \"and\")\n", " return total + (ones[r] if r < 20 else tens[r // 10] + ones[r % 10])\n", " return sum(letters(n) for n in range(1, 1001))\n", "\n", "\n", "run(euler_17)" ] }, { "cell_type": "markdown", "id": "cell-039", "metadata": {}, "source": [ "## [Problem 18](https://projecteuler.net/problem=18)\n", "\n", "*Bottom-up dynamic programming over the triangle.*" ] }, { "cell_type": "code", "execution_count": 20, "id": "cell-040", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 18: Maximum Path Sum I 0 msec ⇒ 1074 ✅ " ] }, "execution_count": 20, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_18():\n", " \"\"\"Maximum Path Sum I\"\"\"\n", " return max_path(read_matrix(DATA[18]))\n", "\n", "\n", "run(euler_18)" ] }, { "cell_type": "markdown", "id": "cell-041", "metadata": {}, "source": [ "## [Problem 19](https://projecteuler.net/problem=19)\n", "\n", "*Let the datetime module do the calendar arithmetic.*" ] }, { "cell_type": "code", "execution_count": 21, "id": "cell-042", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 19: Counting Sundays 0 msec ⇒ 171 ✅ " ] }, "execution_count": 21, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_19():\n", " \"\"\"Counting Sundays\"\"\"\n", " return sum(date(y, m, 1).weekday() == 6\n", " for y in range(1901, 2001) for m in range(1, 13))\n", "\n", "\n", "run(euler_19)" ] }, { "cell_type": "markdown", "id": "cell-043", "metadata": {}, "source": [ "## [Problem 20](https://projecteuler.net/problem=20)\n", "\n", "*Big ints once more.*" ] }, { "cell_type": "code", "execution_count": 22, "id": "cell-044", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 20: Factorial Digit Sum 0 msec ⇒ 648 ✅ " ] }, "execution_count": 22, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_20():\n", " \"\"\"Factorial Digit Sum\"\"\"\n", " return digit_sum(factorial(100))\n", "\n", "\n", "run(euler_20)" ] }, { "cell_type": "markdown", "id": "cell-045", "metadata": {}, "source": [ "## [Problem 21](https://projecteuler.net/problem=21)\n", "\n", "*Proper-divisor sums from factorization; check the amicable condition.*" ] }, { "cell_type": "code", "execution_count": 23, "id": "cell-046", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 21: Amicable Numbers 21 msec ⇒ 31626 ✅ " ] }, "execution_count": 23, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_21():\n", " \"\"\"Amicable Numbers\"\"\"\n", " total = 0\n", " for n in range(2, 10000):\n", " m = proper_divisor_sum(n)\n", " if m != n and proper_divisor_sum(m) == n:\n", " total += n\n", " return total\n", "\n", "\n", "run(euler_21)" ] }, { "cell_type": "markdown", "id": "cell-047", "metadata": {}, "source": [ "## [Problem 22](https://projecteuler.net/problem=22)\n", "\n", "*Sort the names; score = position times alphabetical value.*" ] }, { "cell_type": "code", "execution_count": 24, "id": "cell-048", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 22: Names Scores 2 msec ⇒ 871198282 ✅ " ] }, "execution_count": 24, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_22():\n", " \"\"\"Names Scores\"\"\"\n", " names = sorted(DATA[22].replace('\"', '').split(','))\n", " return sum(i * sum(ord(c) - 64 for c in name)\n", " for i, name in enumerate(names, 1))\n", "\n", "\n", "run(euler_22)" ] }, { "cell_type": "markdown", "id": "cell-049", "metadata": {}, "source": [ "## [Problem 23](https://projecteuler.net/problem=23)\n", "\n", "*Big-int bitset: OR together shifted copies to mark all abundant-pair sums at C speed.*" ] }, { "cell_type": "code", "execution_count": 25, "id": "cell-050", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 23: Non-Abundant Sums 11 msec ⇒ 4179871 ✅ " ] }, "execution_count": 25, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_23():\n", " \"\"\"Non-Abundant Sums\"\"\"\n", " LIMIT = 28123\n", " s = divisor_sum_sieve(LIMIT)\n", " abundant = [int(n) for n in np.flatnonzero(s > np.arange(LIMIT + 1))]\n", " mask = 0\n", " for a in abundant:\n", " mask |= 1 << a\n", " sums = 0\n", " for a in abundant:\n", " sums |= mask << a # marks every abundant + a in one big-int OR\n", " bits = bin(sums)[2:][::-1] # bits[n] == '1' iff n is a sum of two abundants\n", " return sum(n for n in range(1, LIMIT + 1)\n", " if n >= len(bits) or bits[n] == '0')\n", "\n", "\n", "run(euler_23)" ] }, { "cell_type": "markdown", "id": "cell-051", "metadata": {}, "source": [ "## [Problem 24](https://projecteuler.net/problem=24)\n", "\n", "*Factorial number system: pick each digit directly, no enumeration.*" ] }, { "cell_type": "code", "execution_count": 26, "id": "cell-052", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 24: Lexicographic Permutations 0 msec ⇒ 2783915460 ✅ " ] }, "execution_count": 26, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_24():\n", " \"\"\"Lexicographic Permutations\"\"\"\n", " digits, n, out = list('0123456789'), 999_999, ''\n", " for k in range(9, -1, -1):\n", " i, n = divmod(n, factorial(k))\n", " out += digits.pop(i)\n", " return int(out)\n", "\n", "\n", "run(euler_24)" ] }, { "cell_type": "markdown", "id": "cell-053", "metadata": {}, "source": [ "## [Problem 25](https://projecteuler.net/problem=25)\n", "\n", "*Iterate Fibonacci until it reaches 10^999.*" ] }, { "cell_type": "code", "execution_count": 27, "id": "cell-054", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 25: 1000-digit Fibonacci Number 0 msec ⇒ 4782 ✅ " ] }, "execution_count": 27, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_25():\n", " \"\"\"1000-digit Fibonacci Number\"\"\"\n", " target = 10 ** 999\n", " a, b, n = 1, 1, 2\n", " while b < target:\n", " a, b, n = b, a + b, n + 1\n", " return n\n", "\n", "\n", "run(euler_25)" ] }, { "cell_type": "markdown", "id": "cell-055", "metadata": {}, "source": [ "## [Problem 26](https://projecteuler.net/problem=26)\n", "\n", "*The cycle length is the multiplicative order of 10 mod d (after removing 2s and 5s).*" ] }, { "cell_type": "code", "execution_count": 28, "id": "cell-056", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 26: Reciprocal Cycles 4 msec ⇒ 983 ✅ " ] }, "execution_count": 28, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_26():\n", " \"\"\"Reciprocal Cycles\"\"\"\n", " def cycle_length(d):\n", " while d % 2 == 0: d //= 2\n", " while d % 5 == 0: d //= 5\n", " if d == 1:\n", " return 0\n", " k, r = 1, 10 % d\n", " while r != 1:\n", " k, r = k + 1, r * 10 % d\n", " return k\n", " return max(range(2, 1000), key=cycle_length)\n", "\n", "\n", "run(euler_26)" ] }, { "cell_type": "markdown", "id": "cell-057", "metadata": {}, "source": [ "## [Problem 27](https://projecteuler.net/problem=27)\n", "\n", "*b must be prime; test chains against a precomputed sieve (as bytes, for fast lookup).*" ] }, { "cell_type": "code", "execution_count": 29, "id": "cell-058", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 27: Quadratic Primes 28 msec ⇒ -59231 ✅ " ] }, "execution_count": 29, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_27():\n", " \"\"\"Quadratic Primes\"\"\"\n", " sieve = prime_sieve(2_000_000).tobytes()\n", " def chain(a, b):\n", " n = 0\n", " while (v := n * n + a * n + b) > 1 and sieve[v]:\n", " n += 1\n", " return n\n", " _, a, b = max((chain(a, b), a, b)\n", " for b in primes_upto(999) for a in range(-999, 1000, 2))\n", " return a * b\n", "\n", "\n", "run(euler_27)" ] }, { "cell_type": "markdown", "id": "cell-059", "metadata": {}, "source": [ "## [Problem 28](https://projecteuler.net/problem=28)\n", "\n", "*The ring at distance k contributes 4(2k+1)^2 - 12k; sum the closed form.*" ] }, { "cell_type": "code", "execution_count": 30, "id": "cell-060", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 28: Number Spiral Diagonals 0 msec ⇒ 669171001 ✅ " ] }, "execution_count": 30, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_28():\n", " \"\"\"Number Spiral Diagonals\"\"\"\n", " return 1 + sum(4 * (2 * k + 1) ** 2 - 12 * k for k in range(1, 501))\n", "\n", "\n", "run(euler_28)" ] }, { "cell_type": "markdown", "id": "cell-061", "metadata": {}, "source": [ "## [Problem 29](https://projecteuler.net/problem=29)\n", "\n", "*A set comprehension over all 99 x 99 powers.*" ] }, { "cell_type": "code", "execution_count": 31, "id": "cell-062", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 29: Distinct Powers 2 msec ⇒ 9183 ✅ " ] }, "execution_count": 31, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_29():\n", " \"\"\"Distinct Powers\"\"\"\n", " return len({a ** b for a in range(2, 101) for b in range(2, 101)})\n", "\n", "\n", "run(euler_29)" ] }, { "cell_type": "markdown", "id": "cell-063", "metadata": {}, "source": [ "## [Problem 30](https://projecteuler.net/problem=30)\n", "\n", "*Enumerate digit multisets (order is irrelevant to the sum), not all numbers.*" ] }, { "cell_type": "code", "execution_count": 32, "id": "cell-064", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 30: Digit Fifth Powers 11 msec ⇒ 443839 ✅ " ] }, "execution_count": 32, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_30():\n", " \"\"\"Digit Fifth Powers\"\"\"\n", " p5 = [d ** 5 for d in range(10)]\n", " total = 0\n", " for k in range(2, 8):\n", " for combo in combinations_with_replacement(range(10), k):\n", " s = sum(p5[d] for d in combo)\n", " if sorted(map(int, str(s))) == list(combo):\n", " total += s\n", " return total\n", "\n", "\n", "run(euler_30)" ] }, { "cell_type": "markdown", "id": "cell-065", "metadata": {}, "source": [ "## [Problem 31](https://projecteuler.net/problem=31)\n", "\n", "*Classic coin-counting dynamic program.*" ] }, { "cell_type": "code", "execution_count": 33, "id": "cell-066", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 31: Coin Sums 0 msec ⇒ 73682 ✅ " ] }, "execution_count": 33, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_31():\n", " \"\"\"Coin Sums\"\"\"\n", " ways = [1] + [0] * 200\n", " for c in (1, 2, 5, 10, 20, 50, 100, 200):\n", " for v in range(c, 201):\n", " ways[v] += ways[v - c]\n", " return ways[200]\n", "\n", "\n", "run(euler_31)" ] }, { "cell_type": "markdown", "id": "cell-067", "metadata": {}, "source": [ "## [Problem 32](https://projecteuler.net/problem=32)\n", "\n", "*Only 1x4 and 2x3 digit splits can make 9 digits total; collect distinct products.*" ] }, { "cell_type": "code", "execution_count": 34, "id": "cell-068", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 32: Pandigital Products 8 msec ⇒ 45228 ✅ " ] }, "execution_count": 34, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_32():\n", " \"\"\"Pandigital Products\"\"\"\n", " products = set()\n", " for a in range(2, 100):\n", " start = 1234 if a < 10 else 123\n", " for b in range(start, 10000 // a + 1):\n", " s = f'{a}{b}{a * b}'\n", " if len(s) == 9 and set(s) == set('123456789'):\n", " products.add(a * b)\n", " return sum(products)\n", "\n", "\n", "run(euler_32)" ] }, { "cell_type": "markdown", "id": "cell-069", "metadata": {}, "source": [ "## [Problem 33](https://projecteuler.net/problem=33)\n", "\n", "*Try cancelling each shared nonzero digit; keep fractions where it works.*" ] }, { "cell_type": "code", "execution_count": 35, "id": "cell-070", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 33: Digit Cancelling Fractions 1 msec ⇒ 100 ✅ " ] }, "execution_count": 35, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_33():\n", " \"\"\"Digit Cancelling Fractions\"\"\"\n", " found = []\n", " for n in range(10, 100):\n", " for d in range(n + 1, 100):\n", " for c in set(str(n)) & set(str(d)) - {'0'}:\n", " n2 = int(str(n).replace(c, '', 1))\n", " d2 = int(str(d).replace(c, '', 1))\n", " if d2 and n * d2 == n2 * d:\n", " found.append(Fraction(n, d))\n", " break\n", " return prod(found).denominator\n", "\n", "\n", "run(euler_33)" ] }, { "cell_type": "markdown", "id": "cell-071", "metadata": {}, "source": [ "## [Problem 34](https://projecteuler.net/problem=34)\n", "\n", "*Same digit-multiset trick as Problem 30, with factorials.*" ] }, { "cell_type": "code", "execution_count": 36, "id": "cell-072", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 34: Digit Factorials 12 msec ⇒ 40730 ✅ " ] }, "execution_count": 36, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_34():\n", " \"\"\"Digit Factorials\"\"\"\n", " f = [factorial(d) for d in range(10)]\n", " total = 0\n", " for k in range(2, 8):\n", " for combo in combinations_with_replacement(range(10), k):\n", " s = sum(f[d] for d in combo)\n", " if sorted(map(int, str(s))) == list(combo):\n", " total += s\n", " return total\n", "\n", "\n", "run(euler_34)" ] }, { "cell_type": "markdown", "id": "cell-073", "metadata": {}, "source": [ "## [Problem 35](https://projecteuler.net/problem=35)\n", "\n", "*Sieve once; multi-digit candidates may only use digits 1, 3, 7, 9.*" ] }, { "cell_type": "code", "execution_count": 37, "id": "cell-074", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 35: Circular Primes 30 msec ⇒ 55 ✅ " ] }, "execution_count": 37, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_35():\n", " \"\"\"Circular Primes\"\"\"\n", " sieve = prime_sieve(1_000_000).tobytes()\n", " total = 0\n", " for p in primes_upto(999_999):\n", " s = str(p)\n", " if len(s) > 1 and set(s) & set('024568'):\n", " continue\n", " if all(sieve[int(s[i:] + s[:i])] for i in range(1, len(s))):\n", " total += 1\n", " return total\n", "\n", "\n", "run(euler_35)" ] }, { "cell_type": "markdown", "id": "cell-075", "metadata": {}, "source": [ "## [Problem 36](https://projecteuler.net/problem=36)\n", "\n", "*Generate the ~2000 decimal palindromes below a million; test each in binary.*" ] }, { "cell_type": "code", "execution_count": 38, "id": "cell-076", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 36: Double-base Palindromes 0 msec ⇒ 872187 ✅ " ] }, "execution_count": 38, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_36():\n", " \"\"\"Double-base Palindromes\"\"\"\n", " total = 0\n", " for half in range(1, 1000):\n", " h = str(half)\n", " for pal in (h + h[::-1], h + h[::-1][1:]): # even and odd lengths\n", " v = int(pal)\n", " if v < 1_000_000 and bin(v)[2:] == bin(v)[:1:-1]:\n", " total += v\n", " return total\n", "\n", "\n", "run(euler_36)" ] }, { "cell_type": "markdown", "id": "cell-077", "metadata": {}, "source": [ "## [Problem 37](https://projecteuler.net/problem=37)\n", "\n", "*Grow right-truncatable primes digit by digit; test each for left-truncatability.*" ] }, { "cell_type": "code", "execution_count": 39, "id": "cell-078", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 37: Truncatable Primes 0 msec ⇒ 748317 ✅ " ] }, "execution_count": 39, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_37():\n", " \"\"\"Truncatable Primes\"\"\"\n", " total, frontier = 0, [2, 3, 5, 7]\n", " while frontier:\n", " new = []\n", " for p in frontier:\n", " for d in (1, 3, 7, 9):\n", " q = p * 10 + d\n", " if is_prime(q):\n", " new.append(q)\n", " s = str(q)\n", " if all(is_prime(int(s[i:])) for i in range(1, len(s))):\n", " total += q\n", " frontier = new\n", " return total\n", "\n", "\n", "run(euler_37)" ] }, { "cell_type": "markdown", "id": "cell-079", "metadata": {}, "source": [ "## [Problem 38](https://projecteuler.net/problem=38)\n", "\n", "*For each multiplier count n, x can have at most 9//n digits.*" ] }, { "cell_type": "code", "execution_count": 40, "id": "cell-080", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 38: Pandigital Multiples 4 msec ⇒ 932718654 ✅ " ] }, "execution_count": 40, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_38():\n", " \"\"\"Pandigital Multiples\"\"\"\n", " best = 0\n", " for n in range(2, 10):\n", " for x in range(1, 10 ** (9 // n)):\n", " s = ''.join(str(x * i) for i in range(1, n + 1))\n", " if len(s) == 9 and set(s) == set('123456789'):\n", " best = max(best, int(s))\n", " return best\n", "\n", "\n", "run(euler_38)" ] }, { "cell_type": "markdown", "id": "cell-081", "metadata": {}, "source": [ "## [Problem 39](https://projecteuler.net/problem=39)\n", "\n", "*Generate primitive triples with Euclid's formula; count all multiples per perimeter.*" ] }, { "cell_type": "code", "execution_count": 41, "id": "cell-082", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 39: Integer Right Triangles 0 msec ⇒ 840 ✅ " ] }, "execution_count": 41, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_39():\n", " \"\"\"Integer Right Triangles\"\"\"\n", " counts = Counter()\n", " for m in range(2, isqrt(500) + 1):\n", " for n in range(1 + m % 2, m, 2):\n", " if gcd(m, n) == 1:\n", " p = 2 * m * (m + n)\n", " for q in range(p, 1001, p):\n", " counts[q] += 1\n", " return counts.most_common(1)[0][0]\n", "\n", "\n", "run(euler_39)" ] }, { "cell_type": "markdown", "id": "cell-083", "metadata": {}, "source": [ "## [Problem 40](https://projecteuler.net/problem=40)\n", "\n", "*Jump straight to the k-th digit by skipping whole blocks of same-length numbers.*" ] }, { "cell_type": "code", "execution_count": 42, "id": "cell-084", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 40: Champernowne's Constant 0 msec ⇒ 210 ✅ " ] }, "execution_count": 42, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_40():\n", " \"\"\"Champernowne's Constant\"\"\"\n", " def digit(k):\n", " length, first, block = 1, 1, 9\n", " while k > length * block:\n", " k -= length * block\n", " length, first, block = length + 1, first * 10, block * 10\n", " num = first + (k - 1) // length\n", " return int(str(num)[(k - 1) % length])\n", " return prod(digit(10 ** i) for i in range(7))\n", "\n", "\n", "run(euler_40)" ] }, { "cell_type": "markdown", "id": "cell-085", "metadata": {}, "source": [ "## [Problem 41](https://projecteuler.net/problem=41)\n", "\n", "*8- and 9-digit pandigitals are divisible by 3, so try 7 digits (then 4) in descending order.*" ] }, { "cell_type": "code", "execution_count": 43, "id": "cell-086", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 41: Pandigital Prime 0 msec ⇒ 7652413 ✅ " ] }, "execution_count": 43, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_41():\n", " \"\"\"Pandigital Prime\"\"\"\n", " for k in (7, 4):\n", " for p in permutations('7654321'[7 - k:]):\n", " v = int(''.join(p))\n", " if is_prime(v):\n", " return v\n", "\n", "\n", "run(euler_41)" ] }, { "cell_type": "markdown", "id": "cell-087", "metadata": {}, "source": [ "## [Problem 42](https://projecteuler.net/problem=42)\n", "\n", "*Score each word; check membership in a set of triangle numbers.*" ] }, { "cell_type": "code", "execution_count": 44, "id": "cell-088", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 42: Coded Triangle Numbers 1 msec ⇒ 162 ✅ " ] }, "execution_count": 44, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_42():\n", " \"\"\"Coded Triangle Numbers\"\"\"\n", " words = DATA[42].replace('\"', '').split(',')\n", " triangles = {triangle(n) for n in range(1, 30)}\n", " return sum(sum(ord(c) - 64 for c in w) in triangles for w in words)\n", "\n", "\n", "run(euler_42)" ] }, { "cell_type": "markdown", "id": "cell-089", "metadata": {}, "source": [ "## [Problem 43](https://projecteuler.net/problem=43)\n", "\n", "*Build the number right to left, keeping only prefixes that satisfy each divisibility test.*" ] }, { "cell_type": "code", "execution_count": 45, "id": "cell-090", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 43: Sub-string Divisibility 0 msec ⇒ 16695334890 ✅ " ] }, "execution_count": 45, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_43():\n", " \"\"\"Sub-string Divisibility\"\"\"\n", " strings = [f'{m:03d}' for m in range(0, 1000, 17) if len(set(f'{m:03d}')) == 3]\n", " for p in (13, 11, 7, 5, 3, 2):\n", " strings = [d + s for s in strings for d in '0123456789'\n", " if d not in s and int(d + s[:2]) % p == 0]\n", " return sum(int((set('0123456789') - set(s)).pop() + s) for s in strings)\n", "\n", "\n", "run(euler_43)" ] }, { "cell_type": "markdown", "id": "cell-091", "metadata": {}, "source": [ "## [Problem 44](https://projecteuler.net/problem=44)\n", "\n", "*Scan pairs in order of difference-candidate k, breaking once no pair can improve.*" ] }, { "cell_type": "code", "execution_count": 46, "id": "cell-092", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 44: Pentagon Numbers 86 msec ⇒ 5482660 ✅ " ] }, "execution_count": 46, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_44():\n", " \"\"\"Pentagon Numbers\"\"\"\n", " pentagons = [pentagon(n) for n in range(1, 2500)]\n", " pset = set(pentagons)\n", " best = None\n", " for k in range(1, len(pentagons)):\n", " pk = pentagons[k]\n", " for j in range(k - 1, -1, -1):\n", " d = pk - pentagons[j]\n", " if best and d >= best:\n", " break\n", " if d in pset and pk + pentagons[j] in pset:\n", " best = d\n", " return best\n", "\n", "\n", "run(euler_44)" ] }, { "cell_type": "markdown", "id": "cell-093", "metadata": {}, "source": [ "## [Problem 45](https://projecteuler.net/problem=45)\n", "\n", "*Every hexagonal number is triangular, so just scan hexagonals for pentagonality.*" ] }, { "cell_type": "code", "execution_count": 47, "id": "cell-094", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 45: Triangular, Pentagonal, and Hexagonal 4 msec ⇒ 1533776805 ✅ " ] }, "execution_count": 47, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_45():\n", " \"\"\"Triangular, Pentagonal, and Hexagonal\"\"\"\n", " for n in count(144):\n", " h = hexagon(n)\n", " if is_pentagonal(h):\n", " return h\n", "\n", "\n", "run(euler_45)" ] }, { "cell_type": "markdown", "id": "cell-095", "metadata": {}, "source": [ "## [Problem 46](https://projecteuler.net/problem=46)\n", "\n", "*For each odd composite, try subtracting twice a square and testing for primality.*" ] }, { "cell_type": "code", "execution_count": 48, "id": "cell-096", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 46: Goldbach's Other Conjecture 6 msec ⇒ 5777 ✅ " ] }, "execution_count": 48, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_46():\n", " \"\"\"Goldbach's Other Conjecture\"\"\"\n", " for n in count(9, 2):\n", " if not is_prime(n):\n", " if not any(is_prime(n - 2 * k * k)\n", " for k in range(1, isqrt(n // 2) + 1)):\n", " return n\n", "\n", "\n", "run(euler_46)" ] }, { "cell_type": "markdown", "id": "cell-097", "metadata": {}, "source": [ "## [Problem 47](https://projecteuler.net/problem=47)\n", "\n", "*Sieve the count of distinct prime factors; find 4 consecutive 4s with numpy.*" ] }, { "cell_type": "code", "execution_count": 49, "id": "cell-098", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 47: Distinct Primes Factors 24 msec ⇒ 134043 ✅ " ] }, "execution_count": 49, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_47():\n", " \"\"\"Distinct Primes Factors\"\"\"\n", " N = 200_000\n", " counts = np.zeros(N, dtype=np.int8)\n", " for p in range(2, N):\n", " if counts[p] == 0:\n", " counts[p::p] += 1\n", " ok = counts == 4\n", " hits = ok[:-3] & ok[1:-2] & ok[2:-1] & ok[3:]\n", " return int(np.flatnonzero(hits)[0])\n", "\n", "\n", "run(euler_47)" ] }, { "cell_type": "markdown", "id": "cell-099", "metadata": {}, "source": [ "## [Problem 48](https://projecteuler.net/problem=48)\n", "\n", "*Modular exponentiation keeps every term to 10 digits.*" ] }, { "cell_type": "code", "execution_count": 50, "id": "cell-100", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 48: Self Powers 1 msec ⇒ 9110846700 ✅ " ] }, "execution_count": 50, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_48():\n", " \"\"\"Self Powers\"\"\"\n", " M = 10 ** 10\n", " return sum(pow(n, n, M) for n in range(1, 1001)) % M\n", "\n", "\n", "run(euler_48)" ] }, { "cell_type": "markdown", "id": "cell-101", "metadata": {}, "source": [ "## [Problem 49](https://projecteuler.net/problem=49)\n", "\n", "*Group 4-digit primes by digit signature; look for an arithmetic triple in each group.*" ] }, { "cell_type": "code", "execution_count": 51, "id": "cell-102", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 49: Prime Permutations 1 msec ⇒ 296962999629 ✅ " ] }, "execution_count": 51, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_49():\n", " \"\"\"Prime Permutations\"\"\"\n", " groups = defaultdict(list)\n", " for p in primes_upto(9999):\n", " if p >= 1000:\n", " groups[''.join(sorted(str(p)))].append(p)\n", " for group in groups.values():\n", " gset = set(group)\n", " for a, b in combinations(group, 2):\n", " if 2 * b - a in gset and a != 1487:\n", " return int(f'{a}{b}{2 * b - a}')\n", "\n", "\n", "run(euler_49)" ] }, { "cell_type": "markdown", "id": "cell-103", "metadata": {}, "source": [ "## [Problem 50](https://projecteuler.net/problem=50)\n", "\n", "*Prefix sums of primes; try window lengths from longest possible downward.*" ] }, { "cell_type": "code", "execution_count": 52, "id": "cell-104", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 50: Consecutive Prime Sum 7 msec ⇒ 997651 ✅ " ] }, "execution_count": 52, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_50():\n", " \"\"\"Consecutive Prime Sum\"\"\"\n", " N = 1_000_000\n", " ps = primes_upto(N)\n", " pset = set(ps)\n", " prefix = [0]\n", " for p in ps:\n", " prefix.append(prefix[-1] + p)\n", " max_len = next(l for l in range(len(prefix) - 1, 0, -1) if prefix[l] < N)\n", " for length in range(max_len, 0, -1):\n", " for i in range(len(ps) - length + 1):\n", " s = prefix[i + length] - prefix[i]\n", " if s >= N:\n", " break\n", " if s in pset:\n", " return s\n", "\n", "\n", "run(euler_50)" ] }, { "cell_type": "markdown", "id": "cell-105", "metadata": {}, "source": [ "## [Problem 51](https://projecteuler.net/problem=51)\n", "\n", "*An 8-family must replace a digit occurring 3 (or 6) times, and that digit must be 0, 1, or 2.*" ] }, { "cell_type": "code", "execution_count": 53, "id": "cell-106", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 51: Prime Digit Replacements 6 msec ⇒ 121313 ✅ " ] }, "execution_count": 53, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_51():\n", " \"\"\"Prime Digit Replacements\"\"\"\n", " sieve = prime_sieve(1_000_000).tobytes()\n", " for p in primes_upto(999_999):\n", " s = str(p)\n", " for d in '012':\n", " if s.count(d) in (3, 6):\n", " family = [int(s.replace(d, r)) for r in '0123456789']\n", " members = [q for q in family if len(str(q)) == len(s) and sieve[q]]\n", " if len(members) == 8:\n", " return members[0]\n", "\n", "\n", "run(euler_51)" ] }, { "cell_type": "markdown", "id": "cell-107", "metadata": {}, "source": [ "## [Problem 52](https://projecteuler.net/problem=52)\n", "\n", "*x and 6x must have the same digit count, so only scan [10^k, 10^(k+1)/6).*" ] }, { "cell_type": "code", "execution_count": 54, "id": "cell-108", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 52: Permuted Multiples 20 msec ⇒ 142857 ✅ " ] }, "execution_count": 54, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_52():\n", " \"\"\"Permuted Multiples\"\"\"\n", " for k in count(5):\n", " for n in range(10 ** k, 10 ** (k + 1) // 6 + 1):\n", " if all(is_permutation(n, m * n) for m in range(2, 7)):\n", " return n\n", "\n", "\n", "run(euler_52)" ] }, { "cell_type": "markdown", "id": "cell-109", "metadata": {}, "source": [ "## [Problem 53](https://projecteuler.net/problem=53)\n", "\n", "*math.comb is exact; just count.*" ] }, { "cell_type": "code", "execution_count": 55, "id": "cell-110", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 53: Combinatoric Selections 0 msec ⇒ 4075 ✅ " ] }, "execution_count": 55, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_53():\n", " \"\"\"Combinatoric Selections\"\"\"\n", " return sum(comb(n, r) > 1_000_000\n", " for n in range(1, 101) for r in range(n + 1))\n", "\n", "\n", "run(euler_53)" ] }, { "cell_type": "markdown", "id": "cell-111", "metadata": {}, "source": [ "## [Problem 54](https://projecteuler.net/problem=54)\n", "\n", "*Rank each hand as (category, tiebreak values); compare the tuples.*" ] }, { "cell_type": "code", "execution_count": 56, "id": "cell-112", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 54: Poker Hands 4 msec ⇒ 376 ✅ " ] }, "execution_count": 56, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_54():\n", " \"\"\"Poker Hands\"\"\"\n", " def rank(hand):\n", " values = sorted(('23456789TJQKA'.index(c[0]) for c in hand), reverse=True)\n", " groups = Counter(values)\n", " by_count = sorted(groups.items(), key=lambda kv: (kv[1], kv[0]), reverse=True)\n", " counts = tuple(c for v, c in by_count)\n", " order = tuple(v for v, c in by_count)\n", " flush = len({c[1] for c in hand}) == 1\n", " straight = counts == (1, 1, 1, 1, 1) and values[0] - values[4] == 4\n", " category = (8 if straight and flush else\n", " 7 if counts == (4, 1) else\n", " 6 if counts == (3, 2) else\n", " 5 if flush else\n", " 4 if straight else\n", " 3 if counts == (3, 1, 1) else\n", " 2 if counts == (2, 2, 1) else\n", " 1 if counts == (2, 1, 1, 1) else 0)\n", " return (category, order)\n", " return sum(rank(cards[:5]) > rank(cards[5:])\n", " for line in DATA[54].splitlines()\n", " for cards in [line.split()])\n", "\n", "\n", "run(euler_54)" ] }, { "cell_type": "markdown", "id": "cell-113", "metadata": {}, "source": [ "## [Problem 55](https://projecteuler.net/problem=55)\n", "\n", "*Direct simulation: at most 50 reverse-and-add steps for each of 10000 numbers.*" ] }, { "cell_type": "code", "execution_count": 57, "id": "cell-114", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 55: Lychrel Numbers 9 msec ⇒ 249 ✅ " ] }, "execution_count": 57, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_55():\n", " \"\"\"Lychrel Numbers\"\"\"\n", " def is_lychrel(n):\n", " for _ in range(50):\n", " n += int(str(n)[::-1])\n", " if is_palindrome(n):\n", " return False\n", " return True\n", " return sum(is_lychrel(n) for n in range(1, 10000))\n", "\n", "\n", "run(euler_55)" ] }, { "cell_type": "markdown", "id": "cell-115", "metadata": {}, "source": [ "## [Problem 56](https://projecteuler.net/problem=56)\n", "\n", "*Brute force over all 99 x 99 powers; big ints keep it exact.*" ] }, { "cell_type": "code", "execution_count": 58, "id": "cell-116", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 56: Powerful Digit Sum 23 msec ⇒ 972 ✅ " ] }, "execution_count": 58, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_56():\n", " \"\"\"Powerful Digit Sum\"\"\"\n", " return max(digit_sum(a ** b) for a in range(1, 100) for b in range(1, 100))\n", "\n", "\n", "run(euler_56)" ] }, { "cell_type": "markdown", "id": "cell-117", "metadata": {}, "source": [ "## [Problem 57](https://projecteuler.net/problem=57)\n", "\n", "*Iterate the convergent recurrence; compare digit counts.*" ] }, { "cell_type": "code", "execution_count": 59, "id": "cell-118", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 57: Square Root Convergents 1 msec ⇒ 153 ✅ " ] }, "execution_count": 59, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_57():\n", " \"\"\"Square Root Convergents\"\"\"\n", " n, d, total = 3, 2, 0\n", " for _ in range(1000):\n", " if len(str(n)) > len(str(d)):\n", " total += 1\n", " n, d = n + 2 * d, n + d\n", " return total\n", "\n", "\n", "run(euler_57)" ] }, { "cell_type": "markdown", "id": "cell-119", "metadata": {}, "source": [ "## [Problem 58](https://projecteuler.net/problem=58)\n", "\n", "*Only 3 of the 4 corners can be prime (the 4th is a square); Miller-Rabin each corner.*" ] }, { "cell_type": "code", "execution_count": 60, "id": "cell-120", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 58: Spiral Primes 35 msec ⇒ 26241 ✅ " ] }, "execution_count": 60, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_58():\n", " \"\"\"Spiral Primes\"\"\"\n", " nprimes, ncorners, side = 0, 1, 1\n", " while True:\n", " side += 2\n", " sq = side * side\n", " nprimes += sum(is_prime(sq - k * (side - 1)) for k in (1, 2, 3))\n", " ncorners += 4\n", " if nprimes * 10 < ncorners:\n", " return side\n", "\n", "\n", "run(euler_58)" ] }, { "cell_type": "markdown", "id": "cell-121", "metadata": {}, "source": [ "## [Problem 59](https://projecteuler.net/problem=59)\n", "\n", "*Each key byte acts on every 3rd character independently: pick the one making the most spaces.*" ] }, { "cell_type": "code", "execution_count": 61, "id": "cell-122", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 59: XOR Decryption 1 msec ⇒ 107359 ✅ " ] }, "execution_count": 61, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_59():\n", " \"\"\"XOR Decryption\"\"\"\n", " codes = [int(x) for x in DATA[59].split(',')]\n", " key = [max(range(97, 123), key=lambda k: sum(c ^ k == 32 for c in codes[off::3]))\n", " for off in range(3)]\n", " return sum(c ^ key[i % 3] for i, c in enumerate(codes))\n", "\n", "\n", "run(euler_59)" ] }, { "cell_type": "markdown", "id": "cell-123", "metadata": {}, "source": [ "## [Problem 60](https://projecteuler.net/problem=60)\n", "\n", "*Primes pair only within their residue class mod 3; DFS with sum-based pruning.*" ] }, { "cell_type": "code", "execution_count": 62, "id": "cell-124", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 60: Prime Pair Sets 472 msec ⇒ 26033 ✅ " ] }, "execution_count": 62, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_60():\n", " \"\"\"Prime Pair Sets\"\"\"\n", " candidates = [p for p in primes_upto(9000) if p not in (2, 5)]\n", " @lru_cache(maxsize=None)\n", " def pair(p, q):\n", " return (is_prime(int(f'{p}{q}')) and is_prime(int(f'{q}{p}')))\n", " best = inf\n", " def extend(chain, total, cands):\n", " nonlocal best\n", " if len(chain) == 5:\n", " best = min(best, total)\n", " return\n", " need = 5 - len(chain)\n", " for i, p in enumerate(cands):\n", " if total + p * need >= best:\n", " break\n", " extend(chain + [p], total + p,\n", " [q for q in cands[i + 1:] if pair(p, q)])\n", " for cls in (1, 2):\n", " group = [p for p in candidates if p % 3 == cls or p == 3]\n", " extend([], 0, group)\n", " return best\n", "\n", "\n", "run(euler_60)" ] }, { "cell_type": "markdown", "id": "cell-125", "metadata": {}, "source": [ "## [Problem 61](https://projecteuler.net/problem=61)\n", "\n", "*DFS over which figurate type comes next, linking on the 2-digit overlap.*" ] }, { "cell_type": "code", "execution_count": 63, "id": "cell-126", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 61: Cyclical Figurate Numbers 0 msec ⇒ 28684 ✅ " ] }, "execution_count": 63, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_61():\n", " \"\"\"Cyclical Figurate Numbers\"\"\"\n", " def figurates(k):\n", " out, n = [], 1\n", " while (v := n * ((k - 2) * n - (k - 4)) // 2) < 10000:\n", " if v >= 1000:\n", " out.append(v)\n", " n += 1\n", " return out\n", " sets = {k: figurates(k) for k in range(3, 9)}\n", " def dfs(chain, remaining):\n", " if not remaining:\n", " if chain[-1] % 100 == chain[0] // 100:\n", " return sum(chain)\n", " return None\n", " for k in remaining:\n", " for v in sets[k]:\n", " if v // 100 == chain[-1] % 100:\n", " if (answer := dfs(chain + [v], remaining - {k})) is not None:\n", " return answer\n", " return None\n", " for start in sets[8]:\n", " if (answer := dfs([start], frozenset({3, 4, 5, 6, 7}))) is not None:\n", " return answer\n", "\n", "\n", "run(euler_61)" ] }, { "cell_type": "markdown", "id": "cell-127", "metadata": {}, "source": [ "## [Problem 62](https://projecteuler.net/problem=62)\n", "\n", "*Group cubes by digit signature; stop at the first signature with 5 cubes.*" ] }, { "cell_type": "code", "execution_count": 64, "id": "cell-128", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 62: Cubic Permutations 4 msec ⇒ 127035954683 ✅ " ] }, "execution_count": 64, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_62():\n", " \"\"\"Cubic Permutations\"\"\"\n", " groups = defaultdict(list)\n", " for n in count(1):\n", " c = n ** 3\n", " sig = ''.join(sorted(str(c)))\n", " groups[sig].append(c)\n", " if len(groups[sig]) == 5:\n", " return groups[sig][0]\n", "\n", "\n", "run(euler_62)" ] }, { "cell_type": "markdown", "id": "cell-129", "metadata": {}, "source": [ "## [Problem 63](https://projecteuler.net/problem=63)\n", "\n", "*Only bases 1-9 can work (10^n has n+1 digits); count directly.*" ] }, { "cell_type": "code", "execution_count": 65, "id": "cell-130", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 63: Powerful Digit Counts 0 msec ⇒ 49 ✅ " ] }, "execution_count": 65, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_63():\n", " \"\"\"Powerful Digit Counts\"\"\"\n", " return sum(len(str(a ** n)) == n\n", " for a in range(1, 10) for n in range(1, 100))\n", "\n", "\n", "run(euler_63)" ] }, { "cell_type": "markdown", "id": "cell-131", "metadata": {}, "source": [ "## [Problem 64](https://projecteuler.net/problem=64)\n", "\n", "*Standard continued-fraction expansion; the period ends when a = 2*a0.*" ] }, { "cell_type": "code", "execution_count": 66, "id": "cell-132", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 64: Odd Period Square Roots 19 msec ⇒ 1322 ✅ " ] }, "execution_count": 66, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_64():\n", " \"\"\"Odd Period Square Roots\"\"\"\n", " def period(n):\n", " a0 = isqrt(n)\n", " if a0 * a0 == n:\n", " return 0\n", " m, d, a, length = 0, 1, a0, 0\n", " while a != 2 * a0:\n", " m = d * a - m\n", " d = (n - m * m) // d\n", " a = (a0 + m) // d\n", " length += 1\n", " return length\n", " return sum(period(n) % 2 == 1 for n in range(2, 10001))\n", "\n", "\n", "run(euler_64)" ] }, { "cell_type": "markdown", "id": "cell-133", "metadata": {}, "source": [ "## [Problem 65](https://projecteuler.net/problem=65)\n", "\n", "*e = [2; 1, 2, 1, 1, 4, 1, ...]; run the convergent numerator recurrence.*" ] }, { "cell_type": "code", "execution_count": 67, "id": "cell-134", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 65: Convergents of e 0 msec ⇒ 272 ✅ " ] }, "execution_count": 67, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_65():\n", " \"\"\"Convergents of e\"\"\"\n", " p_prev, p = 1, 2\n", " for k in range(2, 101):\n", " a = 2 * k // 3 if k % 3 == 0 else 1\n", " p_prev, p = p, a * p + p_prev\n", " return digit_sum(p)\n", "\n", "\n", "run(euler_65)" ] }, { "cell_type": "markdown", "id": "cell-135", "metadata": {}, "source": [ "## [Problem 66](https://projecteuler.net/problem=66)\n", "\n", "*Solve each Pell equation exactly with continued-fraction convergents.*" ] }, { "cell_type": "code", "execution_count": 68, "id": "cell-136", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 66: Diophantine Equation 2 msec ⇒ 661 ✅ " ] }, "execution_count": 68, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_66():\n", " \"\"\"Diophantine Equation\"\"\"\n", " def pell_x(D):\n", " a0 = isqrt(D)\n", " m, d, a = 0, 1, a0\n", " p_prev, p, q_prev, q = 1, a0, 0, 1\n", " while p * p - D * q * q != 1:\n", " m = d * a - m\n", " d = (D - m * m) // d\n", " a = (a0 + m) // d\n", " p_prev, p = p, a * p + p_prev\n", " q_prev, q = q, a * q + q_prev\n", " return p\n", " return max((D for D in range(2, 1001) if isqrt(D) ** 2 != D), key=pell_x)\n", "\n", "\n", "run(euler_66)" ] }, { "cell_type": "markdown", "id": "cell-137", "metadata": {}, "source": [ "## [Problem 67](https://projecteuler.net/problem=67)\n", "\n", "*The same dynamic program as Problem 18 handles 100 rows instantly.*" ] }, { "cell_type": "code", "execution_count": 69, "id": "cell-138", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 67: Maximum Path Sum II 0 msec ⇒ 7273 ✅ " ] }, "execution_count": 69, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_67():\n", " \"\"\"Maximum Path Sum II\"\"\"\n", " return max_path(read_matrix(DATA[67]))\n", "\n", "\n", "run(euler_67)" ] }, { "cell_type": "markdown", "id": "cell-139", "metadata": {}, "source": [ "## [Problem 68](https://projecteuler.net/problem=68)\n", "\n", "*Choose the inner ring; the line sum then determines the outer ring completely.*" ] }, { "cell_type": "code", "execution_count": 70, "id": "cell-140", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 68: Magic 5-gon Ring 6 msec ⇒ 6531031914842725 ✅ " ] }, "execution_count": 70, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_68():\n", " \"\"\"Magic 5-gon Ring\"\"\"\n", " best = 0\n", " everything = set(range(1, 11))\n", " for inner in permutations(range(1, 11), 5):\n", " if (55 + sum(inner)) % 5:\n", " continue\n", " line = (55 + sum(inner)) // 5\n", " outer = [line - inner[i] - inner[(i + 1) % 5] for i in range(5)]\n", " if sorted(outer) == sorted(everything - set(inner)):\n", " i0 = min(range(5), key=lambda i: outer[i])\n", " s = ''.join(f'{outer[i]}{inner[i]}{inner[(i + 1) % 5]}'\n", " for i in ((i0 + j) % 5 for j in range(5)))\n", " if len(s) == 16:\n", " best = max(best, int(s))\n", " return best\n", "\n", "\n", "run(euler_68)" ] }, { "cell_type": "markdown", "id": "cell-141", "metadata": {}, "source": [ "## [Problem 69](https://projecteuler.net/problem=69)\n", "\n", "*n/phi(n) is maximized by the product of the smallest primes.*" ] }, { "cell_type": "code", "execution_count": 71, "id": "cell-142", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 69: Totient Maximum 0 msec ⇒ 510510 ✅ " ] }, "execution_count": 71, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_69():\n", " \"\"\"Totient Maximum\"\"\"\n", " n = 1\n", " for p in primes_upto(20):\n", " if n * p > 1_000_000:\n", " return n\n", " n *= p\n", "\n", "\n", "run(euler_69)" ] }, { "cell_type": "markdown", "id": "cell-143", "metadata": {}, "source": [ "## [Problem 70](https://projecteuler.net/problem=70)\n", "\n", "*The best n is a product of two primes near sqrt(10^7); search that window.*" ] }, { "cell_type": "code", "execution_count": 72, "id": "cell-144", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 70: Totient Permutation 25 msec ⇒ 8319823 ✅ " ] }, "execution_count": 72, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_70():\n", " \"\"\"Totient Permutation\"\"\"\n", " N = 10 ** 7\n", " ps = [p for p in primes_upto(5000) if p > 1000]\n", " best, best_ratio = 0, inf\n", " for i, p in enumerate(ps):\n", " for q in ps[i + 1:]:\n", " n = p * q\n", " if n >= N:\n", " break\n", " phi = (p - 1) * (q - 1)\n", " if n / phi < best_ratio and is_permutation(n, phi):\n", " best, best_ratio = n, n / phi\n", " return best\n", "\n", "\n", "run(euler_70)" ] }, { "cell_type": "markdown", "id": "cell-145", "metadata": {}, "source": [ "## [Problem 71](https://projecteuler.net/problem=71)\n", "\n", "*The neighbor of 3/7 has 3q = 1 (mod 7); take the largest such denominator.*" ] }, { "cell_type": "code", "execution_count": 73, "id": "cell-146", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 71: Ordered Fractions 0 msec ⇒ 428570 ✅ " ] }, "execution_count": 73, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_71():\n", " \"\"\"Ordered Fractions\"\"\"\n", " q = 1_000_000\n", " while (3 * q) % 7 != 1:\n", " q -= 1\n", " return (3 * q - 1) // 7\n", "\n", "\n", "run(euler_71)" ] }, { "cell_type": "markdown", "id": "cell-147", "metadata": {}, "source": [ "## [Problem 72](https://projecteuler.net/problem=72)\n", "\n", "*The totient summatory function via its O(n^(3/4)) divide-and-conquer recurrence.*" ] }, { "cell_type": "code", "execution_count": 74, "id": "cell-148", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 72: Counting Fractions 16 msec ⇒ 303963552391 ✅ " ] }, "execution_count": 74, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_72():\n", " \"\"\"Counting Fractions\"\"\"\n", " cache = {}\n", " def Phi(n):\n", " \"\"\"Sum of phi(k) for k = 1..n.\"\"\"\n", " if n == 1:\n", " return 1\n", " if n in cache:\n", " return cache[n]\n", " total = n * (n + 1) // 2\n", " d = 2\n", " while d <= n:\n", " q = n // d\n", " d_next = n // q + 1\n", " total -= (d_next - d) * Phi(q)\n", " d = d_next\n", " cache[n] = total\n", " return total\n", " return Phi(1_000_000) - 1\n", "\n", "\n", "run(euler_72)" ] }, { "cell_type": "markdown", "id": "cell-149", "metadata": {}, "source": [ "## [Problem 73](https://projecteuler.net/problem=73)\n", "\n", "*Count all fractions in range per denominator, then sieve away unreduced ones.*" ] }, { "cell_type": "code", "execution_count": 75, "id": "cell-150", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 73: Counting Fractions in a Range 5 msec ⇒ 7295372 ✅ " ] }, "execution_count": 75, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_73():\n", " \"\"\"Counting Fractions in a Range\"\"\"\n", " N = 12000\n", " F = [(d - 1) // 2 - d // 3 for d in range(N + 1)]\n", " for d in range(1, N + 1):\n", " for m in range(2 * d, N + 1, d):\n", " F[m] -= F[d]\n", " return sum(F[2:])\n", "\n", "\n", "run(euler_73)" ] }, { "cell_type": "markdown", "id": "cell-151", "metadata": {}, "source": [ "## [Problem 74](https://projecteuler.net/problem=74)\n", "\n", "*Numbers with the same digit multiset have the same chain; count arrangements.*" ] }, { "cell_type": "code", "execution_count": 76, "id": "cell-152", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 74: Digit Factorial Chains 9 msec ⇒ 402 ✅ " ] }, "execution_count": 76, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_74():\n", " \"\"\"Digit Factorial Chains\"\"\"\n", " FACT = [factorial(d) for d in range(10)]\n", " def fsum(n):\n", " s = 0\n", " while n:\n", " s += FACT[n % 10]\n", " n //= 10\n", " return s\n", " L = {}\n", " def chain_length(n0):\n", " \"\"\"Number of distinct terms in the chain starting at n0 (memoized).\"\"\"\n", " path, pos = [], {}\n", " n = n0\n", " while n not in L and n not in pos:\n", " pos[n] = len(path)\n", " path.append(n)\n", " n = fsum(n)\n", " if n in L:\n", " base, tail = L[n], path\n", " else: # found a new cycle within path\n", " i = pos[n]\n", " base, tail = len(path) - i, path[:i]\n", " for m in path[i:]:\n", " L[m] = base\n", " for j, m in enumerate(reversed(tail), 1):\n", " L[m] = base + j\n", " return L[n0]\n", " total = 0\n", " for k in range(1, 7):\n", " for combo in combinations_with_replacement(range(10), k):\n", " if max(combo) == 0:\n", " continue\n", " rep = int(''.join(map(str, sorted(combo, reverse=True))))\n", " if 1 + chain_length(fsum(rep)) == 60:\n", " counts = Counter(combo)\n", " arrangements = factorial(k)\n", " for c in counts.values():\n", " arrangements //= factorial(c)\n", " if counts[0]: # no leading zero\n", " arrangements = arrangements * (k - counts[0]) // k\n", " total += arrangements\n", " return total\n", "\n", "\n", "run(euler_74)" ] }, { "cell_type": "markdown", "id": "cell-153", "metadata": {}, "source": [ "## [Problem 75](https://projecteuler.net/problem=75)\n", "\n", "*Euclid's formula for primitive triples; mark all multiples of each perimeter.*" ] }, { "cell_type": "code", "execution_count": 77, "id": "cell-154", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 75: Singular Integer Right Triangles 94 msec ⇒ 161667 ✅ " ] }, "execution_count": 77, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_75():\n", " \"\"\"Singular Integer Right Triangles\"\"\"\n", " L = 1_500_000\n", " times_hit = bytearray(L + 1)\n", " for m in range(2, isqrt(L // 2) + 1):\n", " for n in range(1 + m % 2, m, 2):\n", " if gcd(m, n) == 1:\n", " p = 2 * m * (m + n)\n", " if p > L:\n", " break\n", " for q in range(p, L + 1, p):\n", " times_hit[q] += 1\n", " return sum(v == 1 for v in times_hit)\n", "\n", "\n", "run(euler_75)" ] }, { "cell_type": "markdown", "id": "cell-155", "metadata": {}, "source": [ "## [Problem 76](https://projecteuler.net/problem=76)\n", "\n", "*Partition-counting dynamic program with parts 1..99.*" ] }, { "cell_type": "code", "execution_count": 78, "id": "cell-156", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 76: Counting Summations 0 msec ⇒ 190569291 ✅ " ] }, "execution_count": 78, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_76():\n", " \"\"\"Counting Summations\"\"\"\n", " ways = [1] + [0] * 100\n", " for part in range(1, 100):\n", " for v in range(part, 101):\n", " ways[v] += ways[v - part]\n", " return ways[100]\n", "\n", "\n", "run(euler_76)" ] }, { "cell_type": "markdown", "id": "cell-157", "metadata": {}, "source": [ "## [Problem 77](https://projecteuler.net/problem=77)\n", "\n", "*The same dynamic program, restricted to prime parts.*" ] }, { "cell_type": "code", "execution_count": 79, "id": "cell-158", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 77: Prime Summations 0 msec ⇒ 71 ✅ " ] }, "execution_count": 79, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_77():\n", " \"\"\"Prime Summations\"\"\"\n", " ways = [1] + [0] * 100\n", " for p in primes_upto(100):\n", " for v in range(p, 101):\n", " ways[v] += ways[v - p]\n", " return next(n for n in range(2, 101) if ways[n] > 5000)\n", "\n", "\n", "run(euler_77)" ] }, { "cell_type": "markdown", "id": "cell-159", "metadata": {}, "source": [ "## [Problem 78](https://projecteuler.net/problem=78)\n", "\n", "*Euler's pentagonal-number recurrence for p(n), mod 10^6, vectorized with numpy.*" ] }, { "cell_type": "code", "execution_count": 80, "id": "cell-160", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 78: Coin Partitions 119 msec ⇒ 55374 ✅ " ] }, "execution_count": 80, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_78():\n", " \"\"\"Coin Partitions\"\"\"\n", " N = 100_000\n", " pents, signs = [], []\n", " j = 1\n", " while j * (3 * j - 1) // 2 <= N:\n", " sign = 1 if j % 2 == 1 else -1\n", " for g in (j * (3 * j - 1) // 2, j * (3 * j + 1) // 2):\n", " if g <= N:\n", " pents.append(g)\n", " signs.append(sign)\n", " j += 1\n", " pents = np.array(pents)\n", " signs = np.array(signs, dtype=np.int64)\n", " p = np.zeros(N + 1, dtype=np.int64)\n", " p[0] = 1\n", " m = 0\n", " for n in range(1, N + 1):\n", " while m < len(pents) and pents[m] <= n:\n", " m += 1\n", " v = int((signs[:m] * p[n - pents[:m]]).sum()) % 1_000_000\n", " p[n] = v\n", " if v == 0:\n", " return n\n", "\n", "\n", "run(euler_78)" ] }, { "cell_type": "markdown", "id": "cell-161", "metadata": {}, "source": [ "## [Problem 79](https://projecteuler.net/problem=79)\n", "\n", "*Each digit's set of successors gives a total order: sort by out-degree.*" ] }, { "cell_type": "code", "execution_count": 81, "id": "cell-162", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 79: Passcode Derivation 0 msec ⇒ 73162890 ✅ " ] }, "execution_count": 81, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_79():\n", " \"\"\"Passcode Derivation\"\"\"\n", " keys = DATA[79].split()\n", " after = defaultdict(set)\n", " digits = set()\n", " for k in keys:\n", " digits.update(k)\n", " after[k[0]].update(k[1:])\n", " after[k[1]].add(k[2])\n", " order = sorted(digits, key=lambda d: len(after[d]), reverse=True)\n", " return int(''.join(order))\n", "\n", "\n", "run(euler_79)" ] }, { "cell_type": "markdown", "id": "cell-163", "metadata": {}, "source": [ "## [Problem 80](https://projecteuler.net/problem=80)\n", "\n", "*isqrt of n * 10^198 yields the first 100 digits exactly, no floating point.*" ] }, { "cell_type": "code", "execution_count": 82, "id": "cell-164", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 80: Square Root Digital Expansion 0 msec ⇒ 40886 ✅ " ] }, "execution_count": 82, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_80():\n", " \"\"\"Square Root Digital Expansion\"\"\"\n", " total = 0\n", " for n in range(1, 101):\n", " if isqrt(n) ** 2 != n:\n", " total += digit_sum(isqrt(n * 10 ** 198))\n", " return total\n", "\n", "\n", "run(euler_80)" ] }, { "cell_type": "markdown", "id": "cell-165", "metadata": {}, "source": [ "## [Problem 81](https://projecteuler.net/problem=81)\n", "\n", "*Row-by-row dynamic program.*" ] }, { "cell_type": "code", "execution_count": 83, "id": "cell-166", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 81: Path Sum 1 msec ⇒ 427337 ✅ " ] }, "execution_count": 83, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_81():\n", " \"\"\"Path Sum: Two Ways\"\"\"\n", " m = read_matrix(DATA[81])\n", " dp = list(m[0])\n", " for j in range(1, len(dp)):\n", " dp[j] += dp[j - 1]\n", " for row in m[1:]:\n", " dp[0] += row[0]\n", " for j in range(1, len(row)):\n", " dp[j] = row[j] + min(dp[j], dp[j - 1])\n", " return dp[-1]\n", "\n", "\n", "run(euler_81)" ] }, { "cell_type": "markdown", "id": "cell-167", "metadata": {}, "source": [ "## [Problem 82](https://projecteuler.net/problem=82)\n", "\n", "*Column-by-column dynamic program with an up-pass and a down-pass.*" ] }, { "cell_type": "code", "execution_count": 84, "id": "cell-168", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 82: Path Sum 1 msec ⇒ 260324 ✅ " ] }, "execution_count": 84, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_82():\n", " \"\"\"Path Sum: Three Ways\"\"\"\n", " m = read_matrix(DATA[82])\n", " n = len(m)\n", " col = [m[i][0] for i in range(n)]\n", " for j in range(1, n):\n", " new = [0] * n\n", " new[0] = col[0] + m[0][j]\n", " for i in range(1, n):\n", " new[i] = m[i][j] + min(col[i], new[i - 1])\n", " for i in range(n - 2, -1, -1):\n", " new[i] = min(new[i], new[i + 1] + m[i][j])\n", " col = new\n", " return min(col)\n", "\n", "\n", "run(euler_82)" ] }, { "cell_type": "markdown", "id": "cell-169", "metadata": {}, "source": [ "## [Problem 83](https://projecteuler.net/problem=83)\n", "\n", "*Dijkstra's algorithm over the 80x80 grid.*" ] }, { "cell_type": "code", "execution_count": 85, "id": "cell-170", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 83: Path Sum 5 msec ⇒ 425185 ✅ " ] }, "execution_count": 85, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_83():\n", " \"\"\"Path Sum: Four Ways\"\"\"\n", " m = read_matrix(DATA[83])\n", " n = len(m)\n", " dist = [[inf] * n for _ in range(n)]\n", " dist[0][0] = m[0][0]\n", " frontier = [(m[0][0], 0, 0)]\n", " while frontier:\n", " d, r, c = heapq.heappop(frontier)\n", " if (r, c) == (n - 1, n - 1):\n", " return d\n", " if d > dist[r][c]:\n", " continue\n", " for r2, c2 in ((r-1, c), (r+1, c), (r, c-1), (r, c+1)):\n", " if 0 <= r2 < n and 0 <= c2 < n:\n", " d2 = d + m[r2][c2]\n", " if d2 < dist[r2][c2]:\n", " dist[r2][c2] = d2\n", " heapq.heappush(frontier, (d2, r2, c2))\n", "\n", "\n", "run(euler_83)" ] }, { "cell_type": "markdown", "id": "cell-171", "metadata": {}, "source": [ "## [Problem 84](https://projecteuler.net/problem=84)\n", "\n", "*Exact 120-state Markov chain (square x consecutive doubles); no simulation.*" ] }, { "cell_type": "code", "execution_count": 86, "id": "cell-172", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 84: Monopoly Odds 2 msec ⇒ 101524 ✅ " ] }, "execution_count": 86, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_84():\n", " \"\"\"Monopoly Odds\"\"\"\n", " CH, CC, RAILS, UTILS = {7, 22, 36}, {2, 17, 33}, [5, 15, 25, 35], [12, 28]\n", " def resolve(sq):\n", " \"\"\"Distribution over final squares after landing on sq (cards, G2J).\"\"\"\n", " if sq == 30:\n", " return {10: 1.0}\n", " out = defaultdict(float)\n", " if sq in CC:\n", " out[0] += 1/16; out[10] += 1/16; out[sq] += 14/16\n", " elif sq in CH:\n", " next_rail = next(r for r in RAILS + [45] if r > sq) % 40\n", " next_util = next(u for u in UTILS + [52] if u > sq) % 40\n", " for target in (0, 10, 11, 24, 39, 5):\n", " out[target] += 1/16\n", " out[next_rail] += 2/16\n", " out[next_util] += 1/16\n", " for target, p in resolve((sq - 3) % 40).items():\n", " out[target] += p / 16\n", " out[sq] += 6/16\n", " else:\n", " out[sq] = 1.0\n", " return out\n", " T = np.zeros((120, 120))\n", " for sq in range(40):\n", " for dbl in range(3):\n", " state = sq * 3 + dbl\n", " for i in range(1, 5):\n", " for j in range(1, 5):\n", " if i == j and dbl == 2:\n", " T[state, 10 * 3] += 1/16 # third double: go to jail\n", " continue\n", " dbl2 = dbl + 1 if i == j else 0\n", " for target, p in resolve((sq + i + j) % 40).items():\n", " T[state, target * 3 + (0 if target == 10 else dbl2)] += p / 16\n", " v = np.ones(120) / 120\n", " for _ in range(200):\n", " v = v @ T\n", " popularity = v.reshape(40, 3).sum(axis=1)\n", " top3 = popularity.argsort()[::-1][:3]\n", " return int(''.join(f'{sq:02d}' for sq in top3))\n", "\n", "\n", "run(euler_84)" ] }, { "cell_type": "markdown", "id": "cell-173", "metadata": {}, "source": [ "## [Problem 85](https://projecteuler.net/problem=85)\n", "\n", "*Grid a x b contains T(a)×T(b) rectangles; scan for the closest to 2 million.*" ] }, { "cell_type": "code", "execution_count": 87, "id": "cell-174", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 85: Counting Rectangles 1 msec ⇒ 2772 ✅ " ] }, "execution_count": 87, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_85():\n", " \"\"\"Counting Rectangles\"\"\"\n", " TARGET = 2_000_000\n", " best = (inf, 0)\n", " for a in count(1):\n", " if triangle(a) ** 2 > 2 * TARGET:\n", " break\n", " for b in count(a):\n", " r = triangle(a) * triangle(b)\n", " best = min(best, (abs(r - TARGET), a * b))\n", " if r > TARGET:\n", " break\n", " return best[1]\n", "\n", "\n", "run(euler_85)" ] }, { "cell_type": "markdown", "id": "cell-175", "metadata": {}, "source": [ "## [Problem 86](https://projecteuler.net/problem=86)\n", "\n", "*For each cuboid dimension M, count integer shortest paths with one numpy sweep.*" ] }, { "cell_type": "code", "execution_count": 88, "id": "cell-176", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 86: Cuboid Route 27 msec ⇒ 1818 ✅ " ] }, "execution_count": 88, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_86():\n", " \"\"\"Cuboid Route\"\"\"\n", " total, M = 0, 0\n", " while total < 1_000_000:\n", " M += 1\n", " ab = np.arange(2, 2 * M + 1) # a + b, where 1 <= a <= b <= M\n", " d2 = ab * ab + M * M\n", " root = np.rint(np.sqrt(d2)).astype(np.int64)\n", " ok = root * root == d2\n", " pairs = ab // 2 - np.maximum(1, ab - M) + 1\n", " total += int(pairs[ok].sum())\n", " return M\n", "\n", "\n", "run(euler_86)" ] }, { "cell_type": "markdown", "id": "cell-177", "metadata": {}, "source": [ "## [Problem 87](https://projecteuler.net/problem=87)\n", "\n", "*Mark every square+cube+fourth sum in one 50-million-element boolean array.*" ] }, { "cell_type": "code", "execution_count": 89, "id": "cell-178", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 87: Prime Power Triples 22 msec ⇒ 1097343 ✅ " ] }, "execution_count": 89, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_87():\n", " \"\"\"Prime Power Triples\"\"\"\n", " N = 50_000_000\n", " ps = primes_upto(isqrt(N))\n", " squares = np.array([p * p for p in ps])\n", " cubes = [p ** 3 for p in ps if p ** 3 < N]\n", " fourths = [p ** 4 for p in ps if p ** 4 < N]\n", " seen = np.zeros(N, dtype=bool)\n", " for f in fourths:\n", " for c in cubes:\n", " if c + f >= N:\n", " break\n", " s = squares + (c + f)\n", " seen[s[s < N]] = True\n", " return int(seen.sum())\n", "\n", "\n", "run(euler_87)" ] }, { "cell_type": "markdown", "id": "cell-179", "metadata": {}, "source": [ "## [Problem 88](https://projecteuler.net/problem=88)\n", "\n", "*DFS over nondecreasing factor lists; k is determined by padding with 1s.*" ] }, { "cell_type": "code", "execution_count": 90, "id": "cell-180", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 88: Product-sum Numbers 50 msec ⇒ 7587457 ✅ " ] }, "execution_count": 90, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_88():\n", " \"\"\"Product-sum Numbers\"\"\"\n", " K = 12000\n", " best = [2 * K] * (K + 1)\n", " def dfs(product, total, nfactors, start):\n", " k = product - total + nfactors\n", " if k > K:\n", " return\n", " if nfactors >= 2 and product < best[k]:\n", " best[k] = product\n", " f = start\n", " while product * f <= 2 * K:\n", " dfs(product * f, total + f, nfactors + 1, f)\n", " f += 1\n", " dfs(1, 0, 0, 2)\n", " return sum(set(best[2:]))\n", "\n", "\n", "run(euler_88)" ] }, { "cell_type": "markdown", "id": "cell-181", "metadata": {}, "source": [ "## [Problem 89](https://projecteuler.net/problem=89)\n", "\n", "*Only 6 patterns are ever written suboptimally; count characters saved by replacement.*" ] }, { "cell_type": "code", "execution_count": 91, "id": "cell-182", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 89: Roman Numerals 0 msec ⇒ 743 ✅ " ] }, "execution_count": 91, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_89():\n", " \"\"\"Roman Numerals\"\"\"\n", " saved = 0\n", " for numeral in DATA[89].split():\n", " s = numeral\n", " for old, new in (('DCCCC', 'CM'), ('CCCC', 'CD'), ('LXXXX', 'XC'),\n", " ('XXXX', 'XL'), ('VIIII', 'IX'), ('IIII', 'IV')):\n", " s = s.replace(old, new)\n", " saved += len(numeral) - len(s)\n", " return saved\n", "\n", "\n", "run(euler_89)" ] }, { "cell_type": "markdown", "id": "cell-183", "metadata": {}, "source": [ "## [Problem 90](https://projecteuler.net/problem=90)\n", "\n", "*210 possible cubes; test every pair against the 9 squares (with 6 and 9 interchangeable).*" ] }, { "cell_type": "code", "execution_count": 92, "id": "cell-184", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 90: Cube Digit Pairs 5 msec ⇒ 1217 ✅ " ] }, "execution_count": 92, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_90():\n", " \"\"\"Cube Digit Pairs\"\"\"\n", " SQUARES = [(0, 1), (0, 4), (0, 9), (1, 6), (2, 5), (3, 6), (4, 9), (6, 4), (8, 1)]\n", " dice = [set(c) | ({6, 9} if {6, 9} & set(c) else set())\n", " for c in combinations(range(10), 6)]\n", " return sum(all((a in d1 and b in d2) or (a in d2 and b in d1)\n", " for a, b in SQUARES)\n", " for d1, d2 in combinations(dice, 2))\n", "\n", "\n", "run(euler_90)" ] }, { "cell_type": "markdown", "id": "cell-185", "metadata": {}, "source": [ "## [Problem 91](https://projecteuler.net/problem=91)\n", "\n", "*3N^2 axis-aligned cases; for the rest, walk perpendicular steps from each point P.*" ] }, { "cell_type": "code", "execution_count": 93, "id": "cell-186", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 91: Right Triangles with Integer Coordinates 0 msec ⇒ 14234 ✅ " ] }, "execution_count": 93, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_91():\n", " \"\"\"Right Triangles with Integer Coordinates\"\"\"\n", " N = 50\n", " total = 3 * N * N\n", " for x in range(1, N + 1):\n", " for y in range(1, N + 1):\n", " g = gcd(x, y)\n", " dx, dy = x // g, y // g \n", " total += min((N - x) * g // y, y * g // x) # step (dy, -dx)\n", " total += min(x * g // y, (N - y) * g // x) # step (-dy, dx)\n", " return total\n", "\n", "\n", "run(euler_91)" ] }, { "cell_type": "markdown", "id": "cell-187", "metadata": {}, "source": [ "## [Problem 92](https://projecteuler.net/problem=92)\n", "\n", "*Numbers with the same digit multiset behave identically; count multisets, not numbers.*" ] }, { "cell_type": "code", "execution_count": 94, "id": "cell-188", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 92: Square Digit Chains 25 msec ⇒ 8581146 ✅ " ] }, "execution_count": 94, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_92():\n", " \"\"\"Square Digit Chains\"\"\"\n", " def arrives_at_89(n):\n", " while n not in (1, 89):\n", " n = sum(int(d) ** 2 for d in str(n))\n", " return n == 89\n", " total = 0\n", " for combo in combinations_with_replacement(range(10), 7):\n", " s = sum(d * d for d in combo)\n", " if s and arrives_at_89(s):\n", " arrangements = factorial(7)\n", " for c in Counter(combo).values():\n", " arrangements //= factorial(c)\n", " total += arrangements\n", " return total\n", "\n", "\n", "run(euler_92)" ] }, { "cell_type": "markdown", "id": "cell-189", "metadata": {}, "source": [ "## [Problem 93](https://projecteuler.net/problem=93)\n", "\n", "*Combine value-sets of digit subsets bottom-up, memoized across all digit choices.*" ] }, { "cell_type": "code", "execution_count": 95, "id": "cell-190", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 93: Arithmetic Expressions 23 msec ⇒ 1258 ✅ " ] }, "execution_count": 95, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_93():\n", " \"\"\"Arithmetic Expressions\"\"\"\n", " memo = {}\n", " def values(digits):\n", " \"\"\"All values reachable using every digit in the frozenset exactly once.\"\"\"\n", " if digits in memo:\n", " return memo[digits]\n", " if len(digits) == 1:\n", " result = {float(next(iter(digits)))}\n", " else:\n", " result = set()\n", " smallest = min(digits)\n", " members = list(digits)\n", " for r in range(1, len(members)):\n", " for left in combinations(members, r):\n", " if smallest not in left:\n", " continue\n", " A, B = frozenset(left), digits - frozenset(left)\n", " for a in values(A):\n", " for b in values(B):\n", " result.update((a + b, a - b, b - a, a * b))\n", " if abs(b) > 1e-9:\n", " result.add(a / b)\n", " if abs(a) > 1e-9:\n", " result.add(b / a)\n", " memo[digits] = result\n", " return result\n", " best, best_digits = 0, None\n", " for c in combinations(range(1, 10), 4):\n", " reachable = {round(v) for v in values(frozenset(c))\n", " if v > 0.5 and abs(v - round(v)) < 1e-6}\n", " n = 1\n", " while n in reachable:\n", " n += 1\n", " if n - 1 > best:\n", " best, best_digits = n - 1, c\n", " return int(''.join(map(str, best_digits)))\n", "\n", "\n", "run(euler_93)" ] }, { "cell_type": "markdown", "id": "cell-191", "metadata": {}, "source": [ "## [Problem 94](https://projecteuler.net/problem=94)\n", "\n", "*Both families come from Pell solutions of u^2 - 3v^2 = 1; no search at all.*" ] }, { "cell_type": "code", "execution_count": 96, "id": "cell-192", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 94: Almost Equilateral Triangles 0 msec ⇒ 518408346 ✅ " ] }, "execution_count": 96, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_94():\n", " \"\"\"Almost Equilateral Triangles\"\"\"\n", " LIMIT = 10 ** 9\n", " total = 0\n", " u, v = 2, 1\n", " while True:\n", " pA = 3 * (u * u + v * v) + 1 # sides (a, a, a+1)\n", " m = u + 2 * v\n", " pB = 3 * (m * m + v * v) - 1 # sides (a, a, a-1)\n", " if pA > LIMIT and pB > LIMIT:\n", " return total\n", " if pA <= LIMIT:\n", " total += pA\n", " if pB <= LIMIT:\n", " total += pB\n", " u, v = 2 * u + 3 * v, u + 2 * v\n", "\n", "\n", "run(euler_94)" ] }, { "cell_type": "markdown", "id": "cell-193", "metadata": {}, "source": [ "## [Problem 95](https://projecteuler.net/problem=95)\n", "\n", "*Numpy divisor-sum sieve, then walk chains, only crediting cycles at their minimum.*" ] }, { "cell_type": "code", "execution_count": 97, "id": "cell-194", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 95: Amicable Chains 153 msec ⇒ 14316 ✅ " ] }, "execution_count": 97, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_95():\n", " \"\"\"Amicable Chains\"\"\"\n", " N = 1_000_000\n", " s = divisor_sum_sieve(N).tolist()\n", " best_len, best_min = 0, 0\n", " for n in range(2, N + 1):\n", " chain_len, m = 1, s[n]\n", " while n < m <= N and chain_len <= 60:\n", " chain_len += 1\n", " m = s[m]\n", " if m == n and chain_len > best_len: # a cycle whose minimum element is n\n", " best_len, best_min = chain_len, n\n", " return best_min\n", "\n", "\n", "run(euler_95)" ] }, { "cell_type": "markdown", "id": "cell-195", "metadata": {}, "source": [ "## [Problem 96](https://projecteuler.net/problem=96)\n", "\n", "*Bitmask backtracking with the minimum-remaining-values heuristic.*" ] }, { "cell_type": "code", "execution_count": 98, "id": "cell-196", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 96: Su Doku 26 msec ⇒ 24702 ✅ " ] }, "execution_count": 98, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_96():\n", " \"\"\"Su Doku\"\"\"\n", " def solve(board):\n", " rows, cols, boxes = [0] * 9, [0] * 9, [0] * 9\n", " for i, v in enumerate(board):\n", " if v:\n", " r, c = divmod(i, 9)\n", " bit = 1 << v\n", " rows[r] |= bit; cols[c] |= bit; boxes[r // 3 * 3 + c // 3] |= bit\n", " def backtrack():\n", " best_i, best_cand, best_count = -1, 0, 10\n", " for i in range(81):\n", " if board[i] == 0:\n", " r, c = divmod(i, 9)\n", " cand = ~(rows[r] | cols[c] | boxes[r // 3 * 3 + c // 3]) & 0b1111111110\n", " cnt = cand.bit_count()\n", " if cnt < best_count:\n", " best_i, best_cand, best_count = i, cand, cnt\n", " if cnt <= 1:\n", " break\n", " if best_i == -1:\n", " return True\n", " r, c = divmod(best_i, 9)\n", " b = r // 3 * 3 + c // 3\n", " cand = best_cand\n", " while cand:\n", " bit = cand & -cand\n", " cand -= bit\n", " board[best_i] = bit.bit_length() - 1\n", " rows[r] |= bit; cols[c] |= bit; boxes[b] |= bit\n", " if backtrack():\n", " return True\n", " rows[r] ^= bit; cols[c] ^= bit; boxes[b] ^= bit\n", " board[best_i] = 0\n", " return False\n", " backtrack()\n", " return board\n", " lines = [line for line in DATA[96].splitlines() if not line.startswith('Grid')]\n", " total = 0\n", " for i in range(0, len(lines), 9):\n", " board = [int(ch) for row in lines[i:i + 9] for ch in row]\n", " solve(board)\n", " total += board[0] * 100 + board[1] * 10 + board[2]\n", " return total\n", "\n", "\n", "run(euler_96)" ] }, { "cell_type": "markdown", "id": "cell-197", "metadata": {}, "source": [ "## [Problem 97](https://projecteuler.net/problem=97)\n", "\n", "*Modular exponentiation: the last ten digits never require the full number.*" ] }, { "cell_type": "code", "execution_count": 99, "id": "cell-198", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 97: Large Non-Mersenne Prime 0 msec ⇒ 8739992577 ✅ " ] }, "execution_count": 99, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_97():\n", " \"\"\"Large Non-Mersenne Prime\"\"\"\n", " M = 10 ** 10\n", " return (28433 * pow(2, 7830457, M) + 1) % M\n", "\n", "\n", "run(euler_97)" ] }, { "cell_type": "markdown", "id": "cell-199", "metadata": {}, "source": [ "## [Problem 98](https://projecteuler.net/problem=98)\n", "\n", "*Group words into anagram pairs; try mapping each onto squares of the right length.*" ] }, { "cell_type": "code", "execution_count": 100, "id": "cell-200", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 98: Anagramic Squares 19 msec ⇒ 18769 ✅ " ] }, "execution_count": 100, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_98():\n", " \"\"\"Anagramic Squares\"\"\"\n", " words = DATA[98].replace('\"', '').split(',')\n", " groups = defaultdict(list)\n", " for w in words:\n", " groups[''.join(sorted(w))].append(w)\n", " pairs = [(a, b) for g in groups.values() if len(g) > 1\n", " for a, b in combinations(g, 2)]\n", " lengths = {len(a) for a, b in pairs}\n", " squares_by_len = defaultdict(set)\n", " for k in count(1):\n", " sq = str(k * k)\n", " if len(sq) > max(lengths):\n", " break\n", " if len(sq) in lengths:\n", " squares_by_len[len(sq)].add(sq)\n", " best = 0\n", " for a, b in pairs:\n", " for sq in squares_by_len[len(a)]:\n", " mapping = {}\n", " if (len(set(sq)) == len(set(a))\n", " and all(mapping.setdefault(ch, d) == d for ch, d in zip(a, sq))):\n", " t = ''.join(mapping[ch] for ch in b)\n", " if t[0] != '0' and t in squares_by_len[len(b)]:\n", " best = max(best, int(sq), int(t))\n", " return best\n", "\n", "\n", "run(euler_98)" ] }, { "cell_type": "markdown", "id": "cell-201", "metadata": {}, "source": [ "## [Problem 99](https://projecteuler.net/problem=99)\n", "\n", "*Compare b×log(a) instead of computing the towers.*" ] }, { "cell_type": "code", "execution_count": 101, "id": "cell-202", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 99: Largest Exponential 0 msec ⇒ 709 ✅ " ] }, "execution_count": 101, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_99():\n", " \"\"\"Largest Exponential\"\"\"\n", " lines = DATA[99].splitlines()\n", " def key(i):\n", " a, b = map(int, lines[i].split(','))\n", " return b * log(a)\n", " return 1 + max(range(len(lines)), key=key)\n", "\n", "\n", "run(euler_99)" ] }, { "cell_type": "markdown", "id": "cell-203", "metadata": {}, "source": [ "## [Problem 100](https://projecteuler.net/problem=100)\n", "\n", "*The recurrence for solutions of 2b(b-1) = n(n-1); jump straight past 10^12.*" ] }, { "cell_type": "code", "execution_count": 102, "id": "cell-204", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "100: Arranged Probability 0 msec ⇒ 756872327473 ✅ " ] }, "execution_count": 102, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_100():\n", " \"\"\"Arranged Probability\"\"\"\n", " b, n = 15, 21\n", " while n <= 10 ** 12:\n", " b, n = 3 * b + 2 * n - 2, 4 * b + 3 * n - 3\n", " return b\n", "\n", "\n", "run(euler_100)" ] }, { "cell_type": "markdown", "id": "cell-205", "metadata": {}, "source": [ "# Summary of Runs" ] }, { "cell_type": "code", "execution_count": 103, "id": "cell-206", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Problems: 100\n", "Run time in seconds: total: 1.7, max: 0.5, mean: 0.017, median: 0.001\n", "\n", " 1: Multiples of 3 or 5 0 msec ⇒ 233168 ✅ \n", " 2: Even Fibonacci Numbers 0 msec ⇒ 4613732 ✅ \n", " 3: Largest Prime Factor 0 msec ⇒ 6857 ✅ \n", " 4: Largest Palindrome Product 0 msec ⇒ 906609 ✅ \n", " 5: Smallest Multiple 0 msec ⇒ 232792560 ✅ \n", " 6: Sum Square Difference 0 msec ⇒ 25164150 ✅ \n", " 7: 10001st Prime 1 msec ⇒ 104743 ✅ \n", " 8: Largest Product in a Series 0 msec ⇒ 23514624000 ✅ \n", " 9: Special Pythagorean Triplet 4 msec ⇒ 31875000 ✅ \n", " 10: Summation of Primes 4 msec ⇒ 142913828922 ✅ \n", " 11: Largest Product in a Grid 0 msec ⇒ 70600674 ✅ \n", " 12: Highly Divisible Triangular Number 27 msec ⇒ 76576500 ✅ \n", " 13: Large Sum 0 msec ⇒ 5537376230 ✅ \n", " 14: Longest Collatz Sequence 192 msec ⇒ 837799 ✅ \n", " 15: Lattice Paths 0 msec ⇒ 137846528820 ✅ \n", " 16: Power Digit Sum 0 msec ⇒ 1366 ✅ \n", " 17: Number Letter Counts 0 msec ⇒ 21124 ✅ \n", " 18: Maximum Path Sum I 0 msec ⇒ 1074 ✅ \n", " 19: Counting Sundays 0 msec ⇒ 171 ✅ \n", " 20: Factorial Digit Sum 0 msec ⇒ 648 ✅ \n", " 21: Amicable Numbers 21 msec ⇒ 31626 ✅ \n", " 22: Names Scores 2 msec ⇒ 871198282 ✅ \n", " 23: Non-Abundant Sums 11 msec ⇒ 4179871 ✅ \n", " 24: Lexicographic Permutations 0 msec ⇒ 2783915460 ✅ \n", " 25: 1000-digit Fibonacci Number 0 msec ⇒ 4782 ✅ \n", " 26: Reciprocal Cycles 4 msec ⇒ 983 ✅ \n", " 27: Quadratic Primes 28 msec ⇒ -59231 ✅ \n", " 28: Number Spiral Diagonals 0 msec ⇒ 669171001 ✅ \n", " 29: Distinct Powers 2 msec ⇒ 9183 ✅ \n", " 30: Digit Fifth Powers 11 msec ⇒ 443839 ✅ \n", " 31: Coin Sums 0 msec ⇒ 73682 ✅ \n", " 32: Pandigital Products 8 msec ⇒ 45228 ✅ \n", " 33: Digit Cancelling Fractions 1 msec ⇒ 100 ✅ \n", " 34: Digit Factorials 12 msec ⇒ 40730 ✅ \n", " 35: Circular Primes 30 msec ⇒ 55 ✅ \n", " 36: Double-base Palindromes 0 msec ⇒ 872187 ✅ \n", " 37: Truncatable Primes 0 msec ⇒ 748317 ✅ \n", " 38: Pandigital Multiples 4 msec ⇒ 932718654 ✅ \n", " 39: Integer Right Triangles 0 msec ⇒ 840 ✅ \n", " 40: Champernowne's Constant 0 msec ⇒ 210 ✅ \n", " 41: Pandigital Prime 0 msec ⇒ 7652413 ✅ \n", " 42: Coded Triangle Numbers 1 msec ⇒ 162 ✅ \n", " 43: Sub-string Divisibility 0 msec ⇒ 16695334890 ✅ \n", " 44: Pentagon Numbers 86 msec ⇒ 5482660 ✅ \n", " 45: Triangular, Pentagonal, and Hexagonal 4 msec ⇒ 1533776805 ✅ \n", " 46: Goldbach's Other Conjecture 6 msec ⇒ 5777 ✅ \n", " 47: Distinct Primes Factors 24 msec ⇒ 134043 ✅ \n", " 48: Self Powers 1 msec ⇒ 9110846700 ✅ \n", " 49: Prime Permutations 1 msec ⇒ 296962999629 ✅ \n", " 50: Consecutive Prime Sum 7 msec ⇒ 997651 ✅ \n", " 51: Prime Digit Replacements 6 msec ⇒ 121313 ✅ \n", " 52: Permuted Multiples 20 msec ⇒ 142857 ✅ \n", " 53: Combinatoric Selections 0 msec ⇒ 4075 ✅ \n", " 54: Poker Hands 4 msec ⇒ 376 ✅ \n", " 55: Lychrel Numbers 9 msec ⇒ 249 ✅ \n", " 56: Powerful Digit Sum 23 msec ⇒ 972 ✅ \n", " 57: Square Root Convergents 1 msec ⇒ 153 ✅ \n", " 58: Spiral Primes 35 msec ⇒ 26241 ✅ \n", " 59: XOR Decryption 1 msec ⇒ 107359 ✅ \n", " 60: Prime Pair Sets 472 msec ⇒ 26033 ✅ \n", " 61: Cyclical Figurate Numbers 0 msec ⇒ 28684 ✅ \n", " 62: Cubic Permutations 4 msec ⇒ 127035954683 ✅ \n", " 63: Powerful Digit Counts 0 msec ⇒ 49 ✅ \n", " 64: Odd Period Square Roots 19 msec ⇒ 1322 ✅ \n", " 65: Convergents of e 0 msec ⇒ 272 ✅ \n", " 66: Diophantine Equation 2 msec ⇒ 661 ✅ \n", " 67: Maximum Path Sum II 0 msec ⇒ 7273 ✅ \n", " 68: Magic 5-gon Ring 6 msec ⇒ 6531031914842725 ✅ \n", " 69: Totient Maximum 0 msec ⇒ 510510 ✅ \n", " 70: Totient Permutation 25 msec ⇒ 8319823 ✅ \n", " 71: Ordered Fractions 0 msec ⇒ 428570 ✅ \n", " 72: Counting Fractions 16 msec ⇒ 303963552391 ✅ \n", " 73: Counting Fractions in a Range 5 msec ⇒ 7295372 ✅ \n", " 74: Digit Factorial Chains 9 msec ⇒ 402 ✅ \n", " 75: Singular Integer Right Triangles 94 msec ⇒ 161667 ✅ \n", " 76: Counting Summations 0 msec ⇒ 190569291 ✅ \n", " 77: Prime Summations 0 msec ⇒ 71 ✅ \n", " 78: Coin Partitions 119 msec ⇒ 55374 ✅ \n", " 79: Passcode Derivation 0 msec ⇒ 73162890 ✅ \n", " 80: Square Root Digital Expansion 0 msec ⇒ 40886 ✅ \n", " 81: Path Sum 1 msec ⇒ 427337 ✅ \n", " 82: Path Sum 1 msec ⇒ 260324 ✅ \n", " 83: Path Sum 5 msec ⇒ 425185 ✅ \n", " 84: Monopoly Odds 2 msec ⇒ 101524 ✅ \n", " 85: Counting Rectangles 1 msec ⇒ 2772 ✅ \n", " 86: Cuboid Route 27 msec ⇒ 1818 ✅ \n", " 87: Prime Power Triples 22 msec ⇒ 1097343 ✅ \n", " 88: Product-sum Numbers 50 msec ⇒ 7587457 ✅ \n", " 89: Roman Numerals 0 msec ⇒ 743 ✅ \n", " 90: Cube Digit Pairs 5 msec ⇒ 1217 ✅ \n", " 91: Right Triangles with Integer Coordinates 0 msec ⇒ 14234 ✅ \n", " 92: Square Digit Chains 25 msec ⇒ 8581146 ✅ \n", " 93: Arithmetic Expressions 23 msec ⇒ 1258 ✅ \n", " 94: Almost Equilateral Triangles 0 msec ⇒ 518408346 ✅ \n", " 95: Amicable Chains 153 msec ⇒ 14316 ✅ \n", " 96: Su Doku 26 msec ⇒ 24702 ✅ \n", " 97: Large Non-Mersenne Prime 0 msec ⇒ 8739992577 ✅ \n", " 98: Anagramic Squares 19 msec ⇒ 18769 ✅ \n", " 99: Largest Exponential 0 msec ⇒ 709 ✅ \n", "100: Arranged Probability 0 msec ⇒ 756872327473 ✅ \n" ] } ], "source": [ "runs()" ] } ], "metadata": { "kernelspec": { "display_name": "Python [conda env:base] *", "language": "python", "name": "conda-base-py" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.13.9" } }, "nbformat": 4, "nbformat_minor": 5 }