{ "cells": [ { "cell_type": "markdown", "id": "cell-001", "metadata": {}, "source": [ "
notebook by Claude Opus 4.8
June 2026
\n", "\n", "# Project Euler 1–100: Claude Opus 4.8 Edition\n", "\n", "This notebook contains solutions to Project Euler problems 1–100 written by **Claude Opus 4.8**. \n", "\n", "It uses the [`euler_data.py`](euler_data.py) framework from [**Peter Norvig's notebook**](Euler.ipynb)." ] }, { "cell_type": "markdown", "id": "cell-002", "metadata": {}, "source": [ "## Setup" ] }, { "cell_type": "code", "execution_count": 1, "id": "f8b71294-9b3a-478c-86d2-aef418b13acc", "metadata": {}, "outputs": [], "source": [ "from euler_data import DATA, run, runs" ] }, { "cell_type": "code", "execution_count": 106, "id": "cell-003", "metadata": {}, "outputs": [], "source": [ "\"\"\"Utility functions for Project Euler problems 1-100.\n", "\n", "Covers the recurring themes in the first 100 problems: primes & factorization,\n", "divisors & multiplicative functions, digits & palindromes & pandigitals,\n", "combinatorics, figurate numbers, fractions/continued fractions, and a few\n", "miscellaneous helpers.\n", "\n", "Standard library is preferred for the classics so the functions are\n", "self-contained and fast; sympy and numpy are used where they clearly help.\n", "\"\"\"\n", "\n", "\n", "from statistics import mean, median\n", "\n", "\n", "import sys\n", "\n", "\n", "import time\n", "\n", "\n", "from bisect import bisect_left, bisect_right\n", "\n", "\n", "from collections import Counter, defaultdict, deque\n", "\n", "\n", "from fractions import Fraction\n", "\n", "\n", "from functools import lru_cache, reduce\n", "\n", "\n", "from heapq import heappush, heappop\n", "\n", "\n", "from itertools import (\n", " accumulate,\n", " combinations,\n", " combinations_with_replacement,\n", " count,\n", " permutations,\n", " product,\n", " takewhile,\n", ")\n", "\n", "\n", "from math import (\n", " comb,\n", " factorial,\n", " floor,\n", " gcd,\n", " isqrt,\n", " lcm,\n", " perm,\n", " prod,\n", " sqrt,\n", ")\n", "\n", "\n", "import numpy as np\n", "\n", "\n", "import sympy\n", "\n", "\n", "sys.setrecursionlimit(1_000_000)\n", "\n", "\n", "def primes_up_to(n):\n", " \"\"\"Return a list of all primes <= n using a sieve of Eratosthenes.\"\"\"\n", " if n < 2:\n", " return []\n", " sieve = bytearray([1]) * (n + 1)\n", " sieve[0] = sieve[1] = 0\n", " for i in range(2, isqrt(n) + 1):\n", " if sieve[i]:\n", " sieve[i * i::i] = bytearray(len(sieve[i * i::i]))\n", " return [i for i in range(n + 1) if sieve[i]]\n", "\n", "\n", "def prime_sieve(n):\n", " \"\"\"Boolean sieve: index i is True iff i is prime, for 0 <= i <= n.\"\"\"\n", " if n < 2:\n", " return bytearray(n + 1)\n", " sieve = bytearray([1]) * (n + 1)\n", " sieve[0] = sieve[1] = 0\n", " for i in range(2, isqrt(n) + 1):\n", " if sieve[i]:\n", " sieve[i * i::i] = bytearray(len(sieve[i * i::i]))\n", " return sieve\n", "\n", "\n", "def is_prime(n):\n", " \"\"\"Deterministic primality test (Miller-Rabin) good for all 64-bit n.\"\"\"\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", " d = n - 1\n", " r = 0\n", " while d % 2 == 0:\n", " d //= 2\n", " r += 1\n", " for a in (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37):\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 nth_prime(n):\n", " \"\"\"Return the n-th prime (1-indexed): nth_prime(1) == 2.\"\"\"\n", " return sympy.prime(n)\n", "\n", "\n", "def primes_in_range(lo, hi):\n", " \"\"\"Primes p with lo <= p <= hi (inclusive).\"\"\"\n", " return list(sympy.primerange(lo, hi + 1))\n", "\n", "\n", "def factorize(n):\n", " \"\"\"Return prime factorization as a dict {prime: exponent}.\"\"\"\n", " factors = {}\n", " while n % 2 == 0:\n", " factors[2] = factors.get(2, 0) + 1\n", " n //= 2\n", " p = 3\n", " while p * p <= n:\n", " while n % p == 0:\n", " factors[p] = factors.get(p, 0) + 1\n", " n //= p\n", " p += 2\n", " if n > 1:\n", " factors[n] = factors.get(n, 0) + 1\n", " return factors\n", "\n", "\n", "def divisors(n):\n", " \"\"\"Return a sorted list of all positive divisors of n.\"\"\"\n", " small, large = [], []\n", " for i in range(1, isqrt(n) + 1):\n", " if n % i == 0:\n", " small.append(i)\n", " if i != n // i:\n", " large.append(n // i)\n", " return small + large[::-1]\n", "\n", "\n", "def num_divisors(n):\n", " \"\"\"Number of positive divisors, d(n).\"\"\"\n", " result = 1\n", " for exp in factorize(n).values():\n", " result *= exp + 1\n", " return result\n", "\n", "\n", "def sum_divisors(n):\n", " \"\"\"Sum of all positive divisors, sigma(n) (includes n itself).\"\"\"\n", " result = 1\n", " for p, exp in factorize(n).items():\n", " result *= (p ** (exp + 1) - 1) // (p - 1)\n", " return result\n", "\n", "\n", "def proper_divisor_sum(n):\n", " \"\"\"Sum of proper divisors of n (divisors excluding n itself).\"\"\"\n", " if n <= 1:\n", " return 0\n", " return sum_divisors(n) - n\n", "\n", "\n", "def divisor_sum_sieve(n):\n", " \"\"\"Array s where s[i] == sum of proper divisors of i, for i <= n.\n", "\n", " Useful for amicable numbers, abundant/deficient (problems 21, 23).\n", " \"\"\"\n", " s = [0] * (n + 1)\n", " for d in range(1, n // 2 + 1):\n", " for multiple in range(2 * d, n + 1, d):\n", " s[multiple] += d\n", " return s\n", "\n", "\n", "def totient(n):\n", " \"\"\"Euler's totient phi(n).\"\"\"\n", " result = n\n", " for p in factorize(n):\n", " result -= result // p\n", " return result\n", "\n", "\n", "def totient_sieve(n):\n", " \"\"\"Array phi where phi[i] == totient(i) for 0 <= i <= n.\"\"\"\n", " phi = list(range(n + 1))\n", " for i in range(2, n + 1):\n", " if phi[i] == i: # i is prime\n", " for j in range(i, n + 1, i):\n", " phi[j] -= phi[j] // i\n", " return phi\n", "\n", "\n", "def digits(n, base=10):\n", " \"\"\"Return list of digits of n, most-significant first.\"\"\"\n", " if n == 0:\n", " return [0]\n", " n = abs(n)\n", " out = []\n", " while n:\n", " out.append(n % base)\n", " n //= base\n", " return out[::-1]\n", "\n", "\n", "def from_digits(ds, base=10):\n", " \"\"\"Inverse of digits(): build an integer from a list of digits.\"\"\"\n", " return reduce(lambda acc, d: acc * base + d, ds, 0)\n", "\n", "\n", "def digit_sum(n, base=10):\n", " \"\"\"Sum of the digits of n.\"\"\"\n", " return sum(digits(n, base))\n", "\n", "\n", "def is_palindrome(n, base=10):\n", " \"\"\"True if n reads the same forwards and backwards in the given base.\"\"\"\n", " ds = digits(n, base)\n", " return ds == ds[::-1]\n", "\n", "\n", "def is_pandigital(n, digit_set=None):\n", " \"\"\"True if the digits of n are exactly digit_set (default '1'..'9').\n", "\n", " With no digit_set, checks for a 1-9 pandigital (each of 1-9 once).\n", " \"\"\"\n", " s = str(n)\n", " if digit_set is None:\n", " digit_set = set(\"123456789\")\n", " return len(s) == len(digit_set) and set(s) == digit_set\n", "\n", "\n", "def is_permutation(a, b):\n", " \"\"\"True if a and b are digit-permutations of each other.\"\"\"\n", " return sorted(str(a)) == sorted(str(b))\n", "\n", "\n", "def triangular(n):\n", " return n * (n + 1) // 2\n", "\n", "\n", "def pentagonal(n):\n", " return n * (3 * n - 1) // 2\n", "\n", "\n", "def hexagonal(n):\n", " return n * (2 * n - 1)\n", "\n", "\n", "def is_triangular(t):\n", " n = (isqrt(8 * t + 1) - 1) // 2\n", " return n * (n + 1) // 2 == t\n", "\n", "\n", "def is_pentagonal(p):\n", " \"\"\"True if p is a (generalized-positive) pentagonal number.\"\"\"\n", " n = (1 + isqrt(1 + 24 * p))\n", " return n % 6 == 0 and pentagonal(n // 6) == p\n", "\n", "\n", "def is_hexagonal(h):\n", " n = (1 + isqrt(1 + 8 * h))\n", " return n % 4 == 0 and hexagonal(n // 4) == h\n", "\n", "\n", "def fib():\n", " \"\"\"Infinite generator of Fibonacci numbers: 1, 2, 3, 5, 8, ... (1-indexed F1=1, F2=2 style).\n", "\n", " Actually yields F1=1, F2=1, F3=2, ... the standard sequence.\n", " \"\"\"\n", " a, b = 1, 1\n", " while True:\n", " yield a\n", " a, b = b, a + b\n", "\n", "\n", "def fib_n(n):\n", " \"\"\"Return the n-th Fibonacci number (F1 = F2 = 1) via fast doubling.\"\"\"\n", " if n == 0:\n", " return 0\n", " def _fd(k):\n", " if k == 0:\n", " return (0, 1)\n", " a, b = _fd(k >> 1)\n", " c = a * (2 * b - a)\n", " d = a * a + b * b\n", " if k & 1:\n", " return (d, c + d)\n", " return (c, d)\n", " return _fd(n)[0]\n", "\n", "\n", "def continued_fraction_sqrt(n):\n", " \"\"\"Return (a0, [period]) of the continued fraction expansion of sqrt(n).\n", "\n", " Returns (a0, []) when n is a perfect square. Useful for problems 64-66.\n", " \"\"\"\n", " a0 = isqrt(n)\n", " if a0 * a0 == n:\n", " return a0, []\n", " period = []\n", " m, d, a = 0, 1, a0\n", " while a != 2 * a0:\n", " m = d * a - m\n", " d = (n - m * m) // d\n", " a = (a0 + m) // d\n", " period.append(a)\n", " return a0, period\n", "\n", "\n", "def convergents(a0, period, count_terms):\n", " \"\"\"Yield (numerator, denominator) convergents of a continued fraction.\n", "\n", " period is repeated cyclically. Useful for Pell equations (problem 66)\n", " and sqrt(2) convergents (problem 57).\n", " \"\"\"\n", " h_prev, h = 1, a0\n", " k_prev, k = 0, 1\n", " yield h, k\n", " i = 0\n", " for _ in range(count_terms - 1):\n", " a = period[i % len(period)] if period else 0\n", " i += 1\n", " h_prev, h = h, a * h + h_prev\n", " k_prev, k = k, a * k + k_prev\n", " yield h, k\n", "\n", "\n", "def modpow(base, exp, mod):\n", " \"\"\"Modular exponentiation (thin wrapper over built-in pow).\"\"\"\n", " return pow(base, exp, mod)\n", "\n", "\n", "_ONES = [\"\", \"one\", \"two\", \"three\", \"four\", \"five\", \"six\", \"seven\", \"eight\",\n", " \"nine\", \"ten\", \"eleven\", \"twelve\", \"thirteen\", \"fourteen\", \"fifteen\",\n", " \"sixteen\", \"seventeen\", \"eighteen\", \"nineteen\"]\n", "\n", "\n", "_TENS = [\"\", \"\", \"twenty\", \"thirty\", \"forty\", \"fifty\", \"sixty\", \"seventy\",\n", " \"eighty\", \"ninety\"]\n", "\n", "\n", "def number_to_words(n):\n", " \"\"\"Spell out an integer 0..999999 in (British-style) English words.\"\"\"\n", " if n == 0:\n", " return \"zero\"\n", "\n", " def under_1000(x):\n", " words = []\n", " if x >= 100:\n", " words.append(_ONES[x // 100] + \" hundred\")\n", " x %= 100\n", " if x:\n", " words.append(\"and\")\n", " if x >= 20:\n", " words.append(_TENS[x // 10])\n", " x %= 10\n", " if x:\n", " words.append(_ONES[x])\n", " elif x:\n", " words.append(_ONES[x])\n", " return \" \".join(words)\n", "\n", " parts = []\n", " if n >= 1000:\n", " parts.append(under_1000(n // 1000) + \" thousand\")\n", " n %= 1000\n", " if n:\n", " parts.append(under_1000(n))\n", " return \" \".join(parts)\n", "\n", "\n", "def chunked(iterable, size):\n", " \"\"\"Yield successive lists of length `size` from iterable.\"\"\"\n", " it = iter(iterable)\n", " while True:\n", " block = []\n", " for _ in range(size):\n", " try:\n", " block.append(next(it))\n", " except StopIteration:\n", " if block:\n", " yield block\n", " return\n", " yield block\n", "\n", "\n", "def read_grid(text, sep=None, cast=int):\n", " \"\"\"Parse a whitespace/line-delimited grid of numbers into a 2-D list.\n", "\n", " Handy for the bundled-data problems (e.g. 11, 18, 67, 81-83).\n", " \"\"\"\n", " return [[cast(x) for x in line.split(sep)] for line in text.strip().splitlines()]" ] }, { "cell_type": "code", "execution_count": 3, "id": "cell-004", "metadata": {}, "outputs": [], "source": [ "import operator\n", "\n", "\n", "def _max_triangle_path(rows):\n", " \"\"\"Maximum top-to-bottom path sum through a triangle (list of rows).\"\"\"\n", " dp = rows[-1][:]\n", " for r in range(len(rows) - 2, -1, -1):\n", " for c in range(len(rows[r])):\n", " dp[c] = rows[r][c] + max(dp[c], dp[c + 1])\n", " return dp[0]\n", "\n", "\n", "def _read_matrix(text):\n", " return [[int(x) for x in line.split(\",\")]\n", " for line in text.splitlines() if line.strip()]\n" ] }, { "cell_type": "markdown", "id": "cell-006", "metadata": {}, "source": [ "## [Problem 1](https://projecteuler.net/problem=1)\n", "\n", "*Sum the integers below 1000 that are divisible by 3 or 5 (direct filter).*" ] }, { "cell_type": "code", "execution_count": 4, "id": "cell-007", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 1: Multiples of 3 or 5 0 msec ⇒ 233168 ✅ " ] }, "execution_count": 4, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_1():\n", " \"\"\"Multiples of 3 or 5\"\"\"\n", " return sum(n for n in range(1000) if n % 3 == 0 or n % 5 == 0)\n", "\n", "\n", "run(euler_1)" ] }, { "cell_type": "markdown", "id": "cell-008", "metadata": {}, "source": [ "## [Problem 2](https://projecteuler.net/problem=2)\n", "\n", "*Iterate the Fibonacci sequence below 4,000,000 and sum the even terms.*" ] }, { "cell_type": "code", "execution_count": 5, "id": "cell-009", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 2: Even Fibonacci Numbers 0 msec ⇒ 4613732 ✅ " ] }, "execution_count": 5, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_2():\n", " \"\"\"Even Fibonacci Numbers\"\"\"\n", " total = 0\n", " for f in fib():\n", " if f >= 4_000_000:\n", " break\n", " if f % 2 == 0:\n", " total += f\n", " return total\n", "\n", "\n", "run(euler_2)" ] }, { "cell_type": "markdown", "id": "cell-010", "metadata": {}, "source": [ "## [Problem 3](https://projecteuler.net/problem=3)\n", "\n", "*Factorize 600851475143 by trial division and take the largest prime factor.*" ] }, { "cell_type": "code", "execution_count": 6, "id": "cell-011", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 3: Largest Prime Factor 0 msec ⇒ 6857 ✅ " ] }, "execution_count": 6, "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-012", "metadata": {}, "source": [ "## [Problem 4](https://projecteuler.net/problem=4)\n", "\n", "*Brute-force all 3-digit × 3-digit products, keeping the largest palindrome.*" ] }, { "cell_type": "code", "execution_count": 7, "id": "cell-013", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 4: Largest Palindrome Product 25 msec ⇒ 906609 ✅ " ] }, "execution_count": 7, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_4():\n", " \"\"\"Largest Palindrome Product\"\"\"\n", " best = 0\n", " for a in range(100, 1000):\n", " for b in range(a, 1000):\n", " p = a * b\n", " if p > best and is_palindrome(p):\n", " best = p\n", " return best\n", "\n", "\n", "run(euler_4)" ] }, { "cell_type": "markdown", "id": "cell-014", "metadata": {}, "source": [ "## [Problem 5](https://projecteuler.net/problem=5)\n", "\n", "*Fold the whole range 1..20 under lcm.*" ] }, { "cell_type": "code", "execution_count": 8, "id": "cell-015", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 5: Smallest Multiple 0 msec ⇒ 232792560 ✅ " ] }, "execution_count": 8, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_5():\n", " \"\"\"Smallest Multiple\"\"\"\n", " return reduce(lcm, range(1, 21))\n", "\n", "\n", "run(euler_5)" ] }, { "cell_type": "markdown", "id": "cell-016", "metadata": {}, "source": [ "## [Problem 6](https://projecteuler.net/problem=6)\n", "\n", "*Closed-form square-of-sum minus sum-of-squares for the first 100 naturals.*" ] }, { "cell_type": "code", "execution_count": 9, "id": "cell-017", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 6: Sum Square Difference 0 msec ⇒ 25164150 ✅ " ] }, "execution_count": 9, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_6():\n", " \"\"\"Sum Square Difference\"\"\"\n", " n = 100\n", " return (n * (n + 1) // 2) ** 2 - sum(i * i for i in range(1, n + 1))\n", "\n", "\n", "run(euler_6)" ] }, { "cell_type": "markdown", "id": "cell-018", "metadata": {}, "source": [ "## [Problem 7](https://projecteuler.net/problem=7)\n", "\n", "*Ask SymPy for the 10001st prime directly.*" ] }, { "cell_type": "code", "execution_count": 10, "id": "cell-019", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 7: 10001st Prime 6 msec ⇒ 104743 ✅ " ] }, "execution_count": 10, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_7():\n", " \"\"\"10001st Prime\"\"\"\n", " return nth_prime(10001)\n", "\n", "\n", "run(euler_7)" ] }, { "cell_type": "markdown", "id": "cell-020", "metadata": {}, "source": [ "## [Problem 8](https://projecteuler.net/problem=8)\n", "\n", "*Slide a 13-digit window across the number and maximize the digit product.*" ] }, { "cell_type": "code", "execution_count": 11, "id": "cell-021", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 8: Largest Product in a Series 0 msec ⇒ 23514624000 ✅ " ] }, "execution_count": 11, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_8():\n", " \"\"\"Largest Product in a Series\"\"\"\n", " ds = [int(c) for line in DATA[8].split() for c in line]\n", " return max(prod(ds[i:i + 13]) for i in range(len(ds) - 12))\n", "\n", "\n", "run(euler_8)" ] }, { "cell_type": "markdown", "id": "cell-022", "metadata": {}, "source": [ "## [Problem 9](https://projecteuler.net/problem=9)\n", "\n", "*Brute-force a and b with c = 1000 − a − b, testing a² + b² = c².*" ] }, { "cell_type": "code", "execution_count": 12, "id": "cell-023", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 9: Special Pythagorean Triplet 7 msec ⇒ 31875000 ✅ " ] }, "execution_count": 12, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_9():\n", " \"\"\"Special Pythagorean Triplet\"\"\"\n", " for a in range(1, 1000):\n", " for b in range(a, 1000 - a):\n", " c = 1000 - a - b\n", " if c > b and a * a + b * b == c * c:\n", " return a * b * c\n", "\n", "\n", "run(euler_9)" ] }, { "cell_type": "markdown", "id": "cell-024", "metadata": {}, "source": [ "## [Problem 10](https://projecteuler.net/problem=10)\n", "\n", "*Sieve all primes below two million and sum them.*" ] }, { "cell_type": "code", "execution_count": 13, "id": "cell-025", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 10: Summation of Primes 37 msec ⇒ 142913828922 ✅ " ] }, "execution_count": 13, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_10():\n", " \"\"\"Summation of Primes\"\"\"\n", " return sum(primes_up_to(1_999_999))\n", "\n", "\n", "run(euler_10)" ] }, { "cell_type": "markdown", "id": "cell-026", "metadata": {}, "source": [ "## [Problem 11](https://projecteuler.net/problem=11)\n", "\n", "*Check every 4-in-a-row product horizontally, vertically, and on both diagonals.*" ] }, { "cell_type": "code", "execution_count": 14, "id": "cell-027", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 11: Largest Product in a Grid 0 msec ⇒ 70600674 ✅ " ] }, "execution_count": 14, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_11():\n", " \"\"\"Largest Product in a Grid\"\"\"\n", " grid = read_grid(DATA[11])\n", " n = 20\n", " best = 0\n", " for r in range(n):\n", " for c in range(n):\n", " if c <= n - 4:\n", " best = max(best, prod(grid[r][c + i] for i in range(4)))\n", " if r <= n - 4:\n", " best = max(best, prod(grid[r + i][c] for i in range(4)))\n", " if r <= n - 4 and c <= n - 4:\n", " best = max(best, prod(grid[r + i][c + i] for i in range(4)))\n", " if r <= n - 4 and c >= 3:\n", " best = max(best, prod(grid[r + i][c - i] for i in range(4)))\n", " return best\n", "\n", "\n", "run(euler_11)" ] }, { "cell_type": "markdown", "id": "cell-028", "metadata": {}, "source": [ "## [Problem 12](https://projecteuler.net/problem=12)\n", "\n", "*Generate triangular numbers, counting divisors via factorization until d(t) > 500.*" ] }, { "cell_type": "code", "execution_count": 15, "id": "cell-029", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 12: Highly Divisible Triangular Number 83 msec ⇒ 76576500 ✅ " ] }, "execution_count": 15, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_12():\n", " \"\"\"Highly Divisible Triangular Number\"\"\"\n", " n = t = 0\n", " while True:\n", " n += 1\n", " t += n\n", " if num_divisors(t) > 500:\n", " return t\n", "\n", "\n", "run(euler_12)" ] }, { "cell_type": "markdown", "id": "cell-030", "metadata": {}, "source": [ "## [Problem 13](https://projecteuler.net/problem=13)\n", "\n", "*Sum the hundred 50-digit numbers and take the first ten digits.*" ] }, { "cell_type": "code", "execution_count": 16, "id": "cell-031", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 13: Large Sum 0 msec ⇒ 5537376230 ✅ " ] }, "execution_count": 16, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_13():\n", " \"\"\"Large Sum\"\"\"\n", " nums = [int(line) for line in DATA[13].split()]\n", " return int(str(sum(nums))[:10])\n", "\n", "\n", "run(euler_13)" ] }, { "cell_type": "markdown", "id": "cell-032", "metadata": {}, "source": [ "## [Problem 14](https://projecteuler.net/problem=14)\n", "\n", "*Walk Collatz chains with a memo cache, tracking the longest start below one million.*" ] }, { "cell_type": "code", "execution_count": 17, "id": "cell-033", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 14: Longest Collatz Sequence 625 msec ⇒ 837799 ✅ " ] }, "execution_count": 17, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_14():\n", " \"\"\"Longest Collatz Sequence\"\"\"\n", " limit = 1_000_000\n", " cache = {1: 1}\n", " best_len = best_n = 0\n", " for start in range(2, limit):\n", " path = []\n", " m = start\n", " while m not in cache:\n", " path.append(m)\n", " m = m // 2 if m % 2 == 0 else 3 * m + 1\n", " base = cache[m]\n", " for i, v in enumerate(reversed(path)):\n", " cache[v] = base + i + 1\n", " if cache[start] > best_len:\n", " best_len, best_n = cache[start], start\n", " return best_n\n", "\n", "\n", "run(euler_14)" ] }, { "cell_type": "markdown", "id": "cell-034", "metadata": {}, "source": [ "## [Problem 15](https://projecteuler.net/problem=15)\n", "\n", "*The number of lattice paths is the central binomial coefficient C(40, 20).*" ] }, { "cell_type": "code", "execution_count": 18, "id": "cell-035", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 15: Lattice Paths 0 msec ⇒ 137846528820 ✅ " ] }, "execution_count": 18, "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-036", "metadata": {}, "source": [ "## [Problem 16](https://projecteuler.net/problem=16)\n", "\n", "*Digit sum of the big integer 2¹⁰⁰⁰.*" ] }, { "cell_type": "code", "execution_count": 19, "id": "cell-037", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 16: Power Digit Sum 0 msec ⇒ 1366 ✅ " ] }, "execution_count": 19, "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-038", "metadata": {}, "source": [ "## [Problem 17](https://projecteuler.net/problem=17)\n", "\n", "*Spell each number 1..1000 into words and count the letters (no spaces).*" ] }, { "cell_type": "code", "execution_count": 20, "id": "cell-039", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 17: Number Letter Counts 0 msec ⇒ 21124 ✅ " ] }, "execution_count": 20, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_17():\n", " \"\"\"Number Letter Counts\"\"\"\n", " return sum(len(number_to_words(i).replace(\" \", \"\")) for i in range(1, 1001))\n", "\n", "\n", "run(euler_17)" ] }, { "cell_type": "markdown", "id": "cell-040", "metadata": {}, "source": [ "## [Problem 18](https://projecteuler.net/problem=18)\n", "\n", "*Bottom-up DP: collapse the triangle row by row taking the better child.*" ] }, { "cell_type": "code", "execution_count": 21, "id": "cell-041", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 18: Maximum Path Sum I 0 msec ⇒ 1074 ✅ " ] }, "execution_count": 21, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_18():\n", " \"\"\"Maximum Path Sum I\"\"\"\n", " return _max_triangle_path(read_grid(DATA[18]))\n", "\n", "\n", "run(euler_18)" ] }, { "cell_type": "markdown", "id": "cell-042", "metadata": {}, "source": [ "## [Problem 19](https://projecteuler.net/problem=19)\n", "\n", "*Iterate months of 1901–2000 with datetime and count those starting on Sunday.*" ] }, { "cell_type": "code", "execution_count": 22, "id": "cell-043", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 19: Counting Sundays 0 msec ⇒ 171 ✅ " ] }, "execution_count": 22, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_19():\n", " \"\"\"Counting Sundays\"\"\"\n", " import datetime\n", " return sum(\n", " 1\n", " for y in range(1901, 2001)\n", " for m in range(1, 13)\n", " if datetime.date(y, m, 1).weekday() == 6\n", " )\n", "\n", "\n", "run(euler_19)" ] }, { "cell_type": "markdown", "id": "cell-044", "metadata": {}, "source": [ "## [Problem 20](https://projecteuler.net/problem=20)\n", "\n", "*Digit sum of 100! computed with big integers.*" ] }, { "cell_type": "code", "execution_count": 23, "id": "cell-045", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 20: Factorial Digit Sum 0 msec ⇒ 648 ✅ " ] }, "execution_count": 23, "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-046", "metadata": {}, "source": [ "## [Problem 21](https://projecteuler.net/problem=21)\n", "\n", "*Sieve proper-divisor sums, then sum members of amicable pairs below 10000.*" ] }, { "cell_type": "code", "execution_count": 24, "id": "cell-047", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 21: Amicable Numbers 3 msec ⇒ 31626 ✅ " ] }, "execution_count": 24, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_21():\n", " \"\"\"Amicable Numbers\"\"\"\n", " s = divisor_sum_sieve(10000)\n", " total = 0\n", " for a in range(2, 10000):\n", " b = s[a]\n", " if b != a and b < 10000 and s[b] == a:\n", " total += a\n", " return total\n", "\n", "\n", "run(euler_21)" ] }, { "cell_type": "markdown", "id": "cell-048", "metadata": {}, "source": [ "## [Problem 22](https://projecteuler.net/problem=22)\n", "\n", "*Sort the names, then sum position × alphabetical letter value.*" ] }, { "cell_type": "code", "execution_count": 25, "id": "cell-049", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 22: Names Scores 2 msec ⇒ 871198282 ✅ " ] }, "execution_count": 25, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_22():\n", " \"\"\"Names Scores\"\"\"\n", " names = sorted(DATA[22].replace('\"', \"\").split(\",\"))\n", " return sum(\n", " i * sum(ord(c) - 64 for c in name)\n", " for i, name in enumerate(names, 1)\n", " )\n", "\n", "\n", "run(euler_22)" ] }, { "cell_type": "markdown", "id": "cell-050", "metadata": {}, "source": [ "## [Problem 23](https://projecteuler.net/problem=23)\n", "\n", "*Sieve abundant numbers, mark every pairwise sum, and add up what can't be formed.*" ] }, { "cell_type": "code", "execution_count": 26, "id": "cell-051", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 23: Non-Abundant Sums 384 msec ⇒ 4179871 ✅ " ] }, "execution_count": 26, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_23():\n", " \"\"\"Non-Abundant Sums\"\"\"\n", " LIMIT = 28123\n", " s = divisor_sum_sieve(LIMIT)\n", " abundant = [i for i in range(12, LIMIT + 1) if s[i] > i]\n", " can = bytearray(LIMIT + 1)\n", " for i, a in enumerate(abundant):\n", " for b in abundant[i:]:\n", " if a + b > LIMIT:\n", " break\n", " can[a + b] = 1\n", " return sum(i for i in range(LIMIT + 1) if not can[i])\n", "\n", "\n", "run(euler_23)" ] }, { "cell_type": "markdown", "id": "cell-052", "metadata": {}, "source": [ "## [Problem 24](https://projecteuler.net/problem=24)\n", "\n", "*Take the millionth entry from itertools.permutations of the digits 0–9.*" ] }, { "cell_type": "code", "execution_count": 27, "id": "cell-053", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 24: Lexicographic Permutations 6 msec ⇒ 2783915460 ✅ " ] }, "execution_count": 27, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_24():\n", " \"\"\"Lexicographic Permutations\"\"\"\n", " from itertools import islice\n", " return int(\"\".join(next(islice(permutations(\"0123456789\"), 999999, None))))\n", "\n", "\n", "run(euler_24)" ] }, { "cell_type": "markdown", "id": "cell-054", "metadata": {}, "source": [ "## [Problem 25](https://projecteuler.net/problem=25)\n", "\n", "*Advance the Fibonacci sequence until a term reaches 10⁹⁹⁹; return its index.*" ] }, { "cell_type": "code", "execution_count": 28, "id": "cell-055", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 25: 1000-digit Fibonacci Number 15 msec ⇒ 4782 ✅ " ] }, "execution_count": 28, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_25():\n", " \"\"\"1000-digit Fibonacci Number\"\"\"\n", " for i, f in enumerate(fib(), 1):\n", " if f >= 10 ** 999:\n", " return i\n", "\n", "\n", "run(euler_25)" ] }, { "cell_type": "markdown", "id": "cell-056", "metadata": {}, "source": [ "## [Problem 26](https://projecteuler.net/problem=26)\n", "\n", "*Simulate long division, detecting the repeating-remainder cycle length for each d < 1000.*" ] }, { "cell_type": "code", "execution_count": 29, "id": "cell-057", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 26: Reciprocal Cycles 7 msec ⇒ 983 ✅ " ] }, "execution_count": 29, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_26():\n", " \"\"\"Reciprocal Cycles\"\"\"\n", " def cycle_len(d):\n", " seen = {}\n", " r, pos = 1, 0\n", " while r != 0 and r not in seen:\n", " seen[r] = pos\n", " r = (r * 10) % d\n", " pos += 1\n", " return 0 if r == 0 else pos - seen[r]\n", " return max(range(2, 1000), key=cycle_len)\n", "\n", "\n", "run(euler_26)" ] }, { "cell_type": "markdown", "id": "cell-058", "metadata": {}, "source": [ "## [Problem 27](https://projecteuler.net/problem=27)\n", "\n", "*Brute-force coefficients a, b, counting consecutive primes produced by n² + an + b.*" ] }, { "cell_type": "code", "execution_count": 30, "id": "cell-059", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 27: Quadratic Primes 1,300 msec ⇒ -59231 ✅ 🐌" ] }, "execution_count": 30, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_27():\n", " \"\"\"Quadratic Primes\"\"\"\n", " best_len, best_prod = 0, 0\n", " bs = primes_up_to(1000)\n", " for a in range(-999, 1000):\n", " for b in bs:\n", " n = 0\n", " while is_prime(n * n + a * n + b):\n", " n += 1\n", " if n > best_len:\n", " best_len, best_prod = n, a * b\n", " return best_prod\n", "\n", "\n", "run(euler_27)" ] }, { "cell_type": "markdown", "id": "cell-060", "metadata": {}, "source": [ "## [Problem 28](https://projecteuler.net/problem=28)\n", "\n", "*Sum the ring corners of the number spiral using a closed-form per ring.*" ] }, { "cell_type": "code", "execution_count": 31, "id": "cell-061", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 28: Number Spiral Diagonals 0 msec ⇒ 669171001 ✅ " ] }, "execution_count": 31, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_28():\n", " \"\"\"Number Spiral Diagonals\"\"\"\n", " total = 1\n", " for n in range(3, 1002, 2):\n", " total += 4 * n * n - 6 * (n - 1)\n", " return total\n", "\n", "\n", "run(euler_28)" ] }, { "cell_type": "markdown", "id": "cell-062", "metadata": {}, "source": [ "## [Problem 29](https://projecteuler.net/problem=29)\n", "\n", "*Collect a^b into a set for 2 ≤ a, b ≤ 100 and count distinct values.*" ] }, { "cell_type": "code", "execution_count": 32, "id": "cell-063", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 29: Distinct Powers 2 msec ⇒ 9183 ✅ " ] }, "execution_count": 32, "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-064", "metadata": {}, "source": [ "## [Problem 30](https://projecteuler.net/problem=30)\n", "\n", "*Search for numbers equal to the sum of the fifth powers of their digits.*" ] }, { "cell_type": "code", "execution_count": 33, "id": "cell-065", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 30: Digit Fifth Powers 135 msec ⇒ 443839 ✅ " ] }, "execution_count": 33, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_30():\n", " \"\"\"Digit Fifth Powers\"\"\"\n", " p5 = [i ** 5 for i in range(10)]\n", " return sum(\n", " n for n in range(10, 354295)\n", " if n == sum(p5[int(c)] for c in str(n))\n", " )\n", "\n", "\n", "run(euler_30)" ] }, { "cell_type": "markdown", "id": "cell-066", "metadata": {}, "source": [ "## [Problem 31](https://projecteuler.net/problem=31)\n", "\n", "*Classic coin-change DP counting the ways to make £2 from the coin set.*" ] }, { "cell_type": "code", "execution_count": 34, "id": "cell-067", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 31: Coin Sums 0 msec ⇒ 73682 ✅ " ] }, "execution_count": 34, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_31():\n", " \"\"\"Coin Sums\"\"\"\n", " coins = [1, 2, 5, 10, 20, 50, 100, 200]\n", " ways = [1] + [0] * 200\n", " for c in coins:\n", " for i in range(c, 201):\n", " ways[i] += ways[i - c]\n", " return ways[200]\n", "\n", "\n", "run(euler_31)" ] }, { "cell_type": "markdown", "id": "cell-068", "metadata": {}, "source": [ "## [Problem 32](https://projecteuler.net/problem=32)\n", "\n", "*Search a × b whose concatenation with the product is a 1–9 pandigital; sum distinct products.*" ] }, { "cell_type": "code", "execution_count": 35, "id": "cell-069", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 32: Pandigital Products 15 msec ⇒ 45228 ✅ " ] }, "execution_count": 35, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_32():\n", " \"\"\"Pandigital Products\"\"\"\n", " products = set()\n", " for a in range(1, 100):\n", " for b in range(a, 10000):\n", " s = str(a) + str(b) + str(a * b)\n", " if len(s) > 9:\n", " break\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-070", "metadata": {}, "source": [ "## [Problem 33](https://projecteuler.net/problem=33)\n", "\n", "*Find the four nontrivial digit-cancelling fractions; return the reduced product's denominator.*" ] }, { "cell_type": "code", "execution_count": 36, "id": "cell-071", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 33: Digit Cancelling Fractions 1 msec ⇒ 100 ✅ " ] }, "execution_count": 36, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_33():\n", " \"\"\"Digit Cancelling Fractions\"\"\"\n", " p = Fraction(1, 1)\n", " for d in range(11, 100):\n", " for n in range(10, d):\n", " ns, ds = str(n), str(d)\n", " if ns[1] == ds[0] and ds[1] != \"0\":\n", " if Fraction(n, d) == Fraction(int(ns[0]), int(ds[1])):\n", " p *= Fraction(n, d)\n", " return p.denominator\n", "\n", "\n", "run(euler_33)" ] }, { "cell_type": "markdown", "id": "cell-072", "metadata": {}, "source": [ "## [Problem 34](https://projecteuler.net/problem=34)\n", "\n", "*Search for numbers equal to the sum of the factorials of their digits.*" ] }, { "cell_type": "code", "execution_count": 37, "id": "cell-073", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 34: Digit Factorials 1,040 msec ⇒ 40730 ✅ 🐌" ] }, "execution_count": 37, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_34():\n", " \"\"\"Digit Factorials\"\"\"\n", " fact = [factorial(i) for i in range(10)]\n", " return sum(\n", " n for n in range(10, 2540161)\n", " if n == sum(fact[int(c)] for c in str(n))\n", " )\n", "\n", "\n", "run(euler_34)" ] }, { "cell_type": "markdown", "id": "cell-074", "metadata": {}, "source": [ "## [Problem 35](https://projecteuler.net/problem=35)\n", "\n", "*Sieve to a million, keeping primes all of whose digit rotations are also prime.*" ] }, { "cell_type": "code", "execution_count": 38, "id": "cell-075", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 35: Circular Primes 42 msec ⇒ 55 ✅ " ] }, "execution_count": 38, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_35():\n", " \"\"\"Circular Primes\"\"\"\n", " sieve = prime_sieve(1_000_000)\n", " count = 0\n", " for n in range(2, 1_000_000):\n", " if sieve[n]:\n", " s = str(n)\n", " if all(sieve[int(s[i:] + s[:i])] for i in range(len(s))):\n", " count += 1\n", " return count\n", "\n", "\n", "run(euler_35)" ] }, { "cell_type": "markdown", "id": "cell-076", "metadata": {}, "source": [ "## [Problem 36](https://projecteuler.net/problem=36)\n", "\n", "*Collect numbers palindromic in both base 10 and base 2.*" ] }, { "cell_type": "code", "execution_count": 39, "id": "cell-077", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 36: Double-base Palindromes 280 msec ⇒ 872187 ✅ " ] }, "execution_count": 39, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_36():\n", " \"\"\"Double-base Palindromes\"\"\"\n", " return sum(\n", " n for n in range(1_000_000)\n", " if is_palindrome(n) and is_palindrome(n, 2)\n", " )\n", "\n", "\n", "run(euler_36)" ] }, { "cell_type": "markdown", "id": "cell-078", "metadata": {}, "source": [ "## [Problem 37](https://projecteuler.net/problem=37)\n", "\n", "*Search for the eleven primes that stay prime when truncated from either end.*" ] }, { "cell_type": "code", "execution_count": 40, "id": "cell-079", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 37: Truncatable Primes 968 msec ⇒ 748317 ✅ " ] }, "execution_count": 40, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_37():\n", " \"\"\"Truncatable Primes\"\"\"\n", " found = []\n", " n = 10\n", " while len(found) < 11:\n", " n += 1\n", " if is_prime(n):\n", " s = str(n)\n", " if (all(is_prime(int(s[i:])) for i in range(len(s)))\n", " and all(is_prime(int(s[:i])) for i in range(1, len(s)))):\n", " found.append(n)\n", " return sum(found)\n", "\n", "\n", "run(euler_37)" ] }, { "cell_type": "markdown", "id": "cell-080", "metadata": {}, "source": [ "## [Problem 38](https://projecteuler.net/problem=38)\n", "\n", "*Concatenate n, 2n, 3n, … into a 1–9 pandigital and keep the maximum.*" ] }, { "cell_type": "code", "execution_count": 41, "id": "cell-081", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 38: Pandigital Multiples 3 msec ⇒ 932718654 ✅ " ] }, "execution_count": 41, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_38():\n", " \"\"\"Pandigital Multiples\"\"\"\n", " best = 0\n", " for n in range(1, 10000):\n", " s = str(n)\n", " k = 2\n", " while len(s) < 9:\n", " s += str(n * k)\n", " k += 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-082", "metadata": {}, "source": [ "## [Problem 39](https://projecteuler.net/problem=39)\n", "\n", "*Count right triangles by perimeter (p ≤ 1000) and return the most frequent perimeter.*" ] }, { "cell_type": "code", "execution_count": 42, "id": "cell-083", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 39: Integer Right Triangles 7 msec ⇒ 840 ✅ " ] }, "execution_count": 42, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_39():\n", " \"\"\"Integer Right Triangles\"\"\"\n", " counts = Counter()\n", " for a in range(1, 500):\n", " for b in range(a, 500):\n", " c2 = a * a + b * b\n", " c = isqrt(c2)\n", " if c * c == c2:\n", " p = a + b + c\n", " if p <= 1000:\n", " counts[p] += 1\n", " return counts.most_common(1)[0][0]\n", "\n", "\n", "run(euler_39)" ] }, { "cell_type": "markdown", "id": "cell-084", "metadata": {}, "source": [ "## [Problem 40](https://projecteuler.net/problem=40)\n", "\n", "*Build Champernowne's string and multiply the digits at positions 1, 10, …, 10⁶.*" ] }, { "cell_type": "code", "execution_count": 43, "id": "cell-085", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 40: Champernowne's Constant 53 msec ⇒ 210 ✅ " ] }, "execution_count": 43, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_40():\n", " \"\"\"Champernowne's Constant\"\"\"\n", " s = \"\".join(str(i) for i in range(1, 1_000_000))\n", " p = 1\n", " for k in range(7):\n", " p *= int(s[10 ** k - 1])\n", " return p\n", "\n", "\n", "run(euler_40)" ] }, { "cell_type": "markdown", "id": "cell-086", "metadata": {}, "source": [ "## [Problem 41](https://projecteuler.net/problem=41)\n", "\n", "*Scan pandigital permutations (7-, then 4-digit) top-down for the first prime.*" ] }, { "cell_type": "code", "execution_count": 44, "id": "cell-087", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 41: Pandigital Prime 0 msec ⇒ 7652413 ✅ " ] }, "execution_count": 44, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_41():\n", " \"\"\"Pandigital Prime\"\"\"\n", " for n in (7, 4):\n", " digs = \"\".join(str(i) for i in range(1, n + 1))\n", " for p in sorted(permutations(digs), reverse=True):\n", " num = int(\"\".join(p))\n", " if is_prime(num):\n", " return num\n", "\n", "\n", "run(euler_41)" ] }, { "cell_type": "markdown", "id": "cell-088", "metadata": {}, "source": [ "## [Problem 42](https://projecteuler.net/problem=42)\n", "\n", "*Count words whose alphabetical value is a triangular number.*" ] }, { "cell_type": "code", "execution_count": 45, "id": "cell-089", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 42: Coded Triangle Numbers 1 msec ⇒ 162 ✅ " ] }, "execution_count": 45, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_42():\n", " \"\"\"Coded Triangle Numbers\"\"\"\n", " words = DATA[42].replace('\"', \"\").split(\",\")\n", " tri = {triangular(n) for n in range(1, 100)}\n", " return sum(\n", " 1 for w in words\n", " if sum(ord(c) - 64 for c in w) in tri\n", " )\n", "\n", "\n", "run(euler_42)" ] }, { "cell_type": "markdown", "id": "cell-090", "metadata": {}, "source": [ "## [Problem 43](https://projecteuler.net/problem=43)\n", "\n", "*Test permutations of 0–9 for the substring-divisibility property and sum them.*" ] }, { "cell_type": "code", "execution_count": 46, "id": "cell-091", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 43: Sub-string Divisibility 1,098 msec ⇒ 16695334890 ✅ 🐌" ] }, "execution_count": 46, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_43():\n", " \"\"\"Sub-string Divisibility\"\"\"\n", " primes7 = [2, 3, 5, 7, 11, 13, 17]\n", " total = 0\n", " for p in permutations(\"0123456789\"):\n", " if all(int(\"\".join(p[i + 1:i + 4])) % primes7[i] == 0 for i in range(7)):\n", " total += int(\"\".join(p))\n", " return total\n", "\n", "\n", "run(euler_43)" ] }, { "cell_type": "markdown", "id": "cell-092", "metadata": {}, "source": [ "## [Problem 44](https://projecteuler.net/problem=44)\n", "\n", "*Find the pentagonal pair whose sum and difference are both pentagonal; return the difference.*" ] }, { "cell_type": "code", "execution_count": 47, "id": "cell-093", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 44: Pentagon Numbers 166 msec ⇒ 5482660 ✅ " ] }, "execution_count": 47, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_44():\n", " \"\"\"Pentagon Numbers\"\"\"\n", " pents = [pentagonal(n) for n in range(1, 3000)]\n", " pset = set(pents)\n", " best = None\n", " for i in range(len(pents)):\n", " for j in range(i):\n", " a, b = pents[j], pents[i]\n", " d = b - a\n", " if d in pset and (a + b) in pset:\n", " if best is None or d < best:\n", " best = d\n", " return best\n", "\n", "\n", "run(euler_44)" ] }, { "cell_type": "markdown", "id": "cell-094", "metadata": {}, "source": [ "## [Problem 45](https://projecteuler.net/problem=45)\n", "\n", "*Iterate hexagonals (each is triangular) and test each for being pentagonal.*" ] }, { "cell_type": "code", "execution_count": 48, "id": "cell-095", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 45: Triangular, Pentagonal, and Hexagonal 4 msec ⇒ 1533776805 ✅ " ] }, "execution_count": 48, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_45():\n", " \"\"\"Triangular, Pentagonal, and Hexagonal\"\"\"\n", " n = 144\n", " while True:\n", " n += 1\n", " h = hexagonal(n)\n", " if is_pentagonal(h):\n", " return h\n", "\n", "\n", "run(euler_45)" ] }, { "cell_type": "markdown", "id": "cell-096", "metadata": {}, "source": [ "## [Problem 46](https://projecteuler.net/problem=46)\n", "\n", "*Find the smallest odd composite not expressible as prime + 2×square.*" ] }, { "cell_type": "code", "execution_count": 49, "id": "cell-097", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 46: Goldbach's Other Conjecture 13 msec ⇒ 5777 ✅ " ] }, "execution_count": 49, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_46():\n", " \"\"\"Goldbach's Other Conjecture\"\"\"\n", " def can(n):\n", " for i in range(1, isqrt(n // 2) + 1):\n", " if is_prime(n - 2 * i * i):\n", " return True\n", " return False\n", " n = 9\n", " while True:\n", " n += 2\n", " if not is_prime(n) and not can(n):\n", " return n\n", "\n", "\n", "run(euler_46)" ] }, { "cell_type": "markdown", "id": "cell-098", "metadata": {}, "source": [ "## [Problem 47](https://projecteuler.net/problem=47)\n", "\n", "*Scan for the first run of four consecutive integers each with four distinct prime factors.*" ] }, { "cell_type": "code", "execution_count": 50, "id": "cell-099", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 47: Distinct Primes Factors 253 msec ⇒ 134043 ✅ " ] }, "execution_count": 50, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_47():\n", " \"\"\"Distinct Primes Factors\"\"\"\n", " n = 1\n", " consec = 0\n", " while True:\n", " n += 1\n", " if len(factorize(n)) == 4:\n", " consec += 1\n", " if consec == 4:\n", " return n - 3\n", " else:\n", " consec = 0\n", "\n", "\n", "run(euler_47)" ] }, { "cell_type": "markdown", "id": "cell-100", "metadata": {}, "source": [ "## [Problem 48](https://projecteuler.net/problem=48)\n", "\n", "*Sum k^k mod 10¹⁰ using fast modular exponentiation.*" ] }, { "cell_type": "code", "execution_count": 51, "id": "cell-101", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 48: Self Powers 1 msec ⇒ 9110846700 ✅ " ] }, "execution_count": 51, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_48():\n", " \"\"\"Self Powers\"\"\"\n", " mod = 10 ** 10\n", " return sum(pow(k, k, mod) for k in range(1, 1001)) % mod\n", "\n", "\n", "run(euler_48)" ] }, { "cell_type": "markdown", "id": "cell-102", "metadata": {}, "source": [ "## [Problem 49](https://projecteuler.net/problem=49)\n", "\n", "*Find 4-digit prime arithmetic triples that are digit permutations (skipping the given one).*" ] }, { "cell_type": "code", "execution_count": 52, "id": "cell-103", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 49: Prime Permutations 753 msec ⇒ 296962999629 ✅ " ] }, "execution_count": 52, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_49():\n", " \"\"\"Prime Permutations\"\"\"\n", " for a in range(1000, 10000):\n", " if is_prime(a):\n", " for d in range(1, 5000):\n", " b, c = a + d, a + 2 * d\n", " if c < 10000 and is_prime(b) and is_prime(c) \\\n", " and is_permutation(a, b) and is_permutation(a, c):\n", " if a != 1487:\n", " return int(f\"{a}{b}{c}\")\n", "\n", "\n", "run(euler_49)" ] }, { "cell_type": "markdown", "id": "cell-104", "metadata": {}, "source": [ "## [Problem 50](https://projecteuler.net/problem=50)\n", "\n", "*Use prefix sums of primes to find the longest consecutive run summing to a prime below a million.*" ] }, { "cell_type": "code", "execution_count": 53, "id": "cell-105", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 50: Consecutive Prime Sum 35 msec ⇒ 997651 ✅ " ] }, "execution_count": 53, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_50():\n", " \"\"\"Consecutive Prime Sum\"\"\"\n", " primes = primes_up_to(1_000_000)\n", " pset = set(primes)\n", " pre = [0]\n", " for p in primes:\n", " pre.append(pre[-1] + p)\n", " best_len, best_prime = 0, 0\n", " n = len(primes)\n", " for i in range(n):\n", " for j in range(i + best_len, n):\n", " s = pre[j + 1] - pre[i]\n", " if s >= 1_000_000:\n", " break\n", " if s in pset and (j + 1 - i) > best_len:\n", " best_len, best_prime = j + 1 - i, s\n", " return best_prime\n", "\n", "\n", "run(euler_50)" ] }, { "cell_type": "markdown", "id": "cell-106", "metadata": {}, "source": [ "## [Problem 51](https://projecteuler.net/problem=51)\n", "\n", "*Group primes by wildcard digit patterns and find a pattern with an eight-prime family.*" ] }, { "cell_type": "code", "execution_count": 54, "id": "cell-107", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 51: Prime Digit Replacements 1,167 msec ⇒ 121313 ✅ 🐌" ] }, "execution_count": 54, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_51():\n", " \"\"\"Prime Digit Replacements\"\"\"\n", " for length in range(2, 8):\n", " families = defaultdict(list)\n", " for p in primes_in_range(10 ** (length - 1), 10 ** length - 1):\n", " s = str(p)\n", " for r in range(1, length):\n", " for combo in combinations(range(length), r):\n", " if len({s[i] for i in combo}) == 1:\n", " pat = \"\".join(\n", " \"*\" if i in combo else s[i] for i in range(length)\n", " )\n", " families[pat].append(p)\n", " best = None\n", " for members in families.values():\n", " if len(members) >= 8:\n", " cand = min(members)\n", " if best is None or cand < best:\n", " best = cand\n", " if best is not None:\n", " return best\n", "\n", "\n", "run(euler_51)" ] }, { "cell_type": "markdown", "id": "cell-108", "metadata": {}, "source": [ "## [Problem 52](https://projecteuler.net/problem=52)\n", "\n", "*Search for the smallest x whose multiples 2x..6x are all digit permutations of x.*" ] }, { "cell_type": "code", "execution_count": 55, "id": "cell-109", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 52: Permuted Multiples 69 msec ⇒ 142857 ✅ " ] }, "execution_count": 55, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_52():\n", " \"\"\"Permuted Multiples\"\"\"\n", " x = 1\n", " while True:\n", " x += 1\n", " if all(is_permutation(x, k * x) for k in range(2, 7)):\n", " return x\n", "\n", "\n", "run(euler_52)" ] }, { "cell_type": "markdown", "id": "cell-110", "metadata": {}, "source": [ "## [Problem 53](https://projecteuler.net/problem=53)\n", "\n", "*Count the binomial coefficients C(n, r) exceeding one million for n ≤ 100.*" ] }, { "cell_type": "code", "execution_count": 56, "id": "cell-111", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 53: Combinatoric Selections 0 msec ⇒ 4075 ✅ " ] }, "execution_count": 56, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_53():\n", " \"\"\"Combinatoric Selections\"\"\"\n", " return sum(\n", " 1\n", " for n in range(1, 101)\n", " for r in range(n + 1)\n", " if comb(n, r) > 1_000_000\n", " )\n", "\n", "\n", "run(euler_53)" ] }, { "cell_type": "markdown", "id": "cell-112", "metadata": {}, "source": [ "## [Problem 54](https://projecteuler.net/problem=54)\n", "\n", "*Score each poker hand by category and tiebreakers; count player one's wins.*" ] }, { "cell_type": "code", "execution_count": 57, "id": "cell-113", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 54: Poker Hands 4 msec ⇒ 376 ✅ " ] }, "execution_count": 57, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_54():\n", " \"\"\"Poker Hands\"\"\"\n", " ORDER = \"23456789TJQKA\"\n", "\n", " def rank(hand):\n", " vals = sorted((ORDER.index(c[0]) for c in hand), reverse=True)\n", " suits = [c[1] for c in hand]\n", " cnt = Counter(vals)\n", " order = sorted(vals, key=lambda v: (cnt[v], v), reverse=True)\n", " counts = sorted(cnt.values(), reverse=True)\n", " flush = len(set(suits)) == 1\n", " straight = len(cnt) == 5 and max(vals) - min(vals) == 4\n", " if straight and flush:\n", " cat = 8\n", " elif counts == [4, 1]:\n", " cat = 7\n", " elif counts == [3, 2]:\n", " cat = 6\n", " elif flush:\n", " cat = 5\n", " elif straight:\n", " cat = 4\n", " elif counts == [3, 1, 1]:\n", " cat = 3\n", " elif counts == [2, 2, 1]:\n", " cat = 2\n", " elif counts == [2, 1, 1, 1]:\n", " cat = 1\n", " else:\n", " cat = 0\n", " return (cat, order)\n", "\n", " count = 0\n", " for line in DATA[54].splitlines():\n", " cards = line.split()\n", " if rank(cards[:5]) > rank(cards[5:]):\n", " count += 1\n", " return count\n", "\n", "\n", "run(euler_54)" ] }, { "cell_type": "markdown", "id": "cell-114", "metadata": {}, "source": [ "## [Problem 55](https://projecteuler.net/problem=55)\n", "\n", "*Count Lychrel numbers below 10000 (no palindrome within 50 reverse-and-add steps).*" ] }, { "cell_type": "code", "execution_count": 58, "id": "cell-115", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 55: Lychrel Numbers 22 msec ⇒ 249 ✅ " ] }, "execution_count": 58, "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(1 for n in range(1, 10000) if is_lychrel(n))\n", "\n", "\n", "run(euler_55)" ] }, { "cell_type": "markdown", "id": "cell-116", "metadata": {}, "source": [ "## [Problem 56](https://projecteuler.net/problem=56)\n", "\n", "*Maximize the digit sum of a^b for a, b < 100.*" ] }, { "cell_type": "code", "execution_count": 59, "id": "cell-117", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 56: Powerful Digit Sum 48 msec ⇒ 972 ✅ " ] }, "execution_count": 59, "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-118", "metadata": {}, "source": [ "## [Problem 57](https://projecteuler.net/problem=57)\n", "\n", "*Iterate √2 continued-fraction convergents and count those with a longer numerator than denominator.*" ] }, { "cell_type": "code", "execution_count": 60, "id": "cell-119", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 57: Square Root Convergents 1 msec ⇒ 153 ✅ " ] }, "execution_count": 60, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_57():\n", " \"\"\"Square Root Convergents\"\"\"\n", " n, d = 3, 2\n", " count = 0\n", " for _ in range(1000):\n", " if len(str(n)) > len(str(d)):\n", " count += 1\n", " n, d = n + 2 * d, n + d\n", " return count\n", "\n", "\n", "run(euler_57)" ] }, { "cell_type": "markdown", "id": "cell-120", "metadata": {}, "source": [ "## [Problem 58](https://projecteuler.net/problem=58)\n", "\n", "*Grow the spiral, tracking the prime ratio along the diagonals until it drops below 10%.*" ] }, { "cell_type": "code", "execution_count": 61, "id": "cell-121", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 58: Spiral Primes 74 msec ⇒ 26241 ✅ " ] }, "execution_count": 61, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_58():\n", " \"\"\"Spiral Primes\"\"\"\n", " total, primes, side = 1, 0, 1\n", " while True:\n", " side += 2\n", " corners = [side * side - k * (side - 1) for k in range(4)]\n", " primes += sum(1 for c in corners if is_prime(c))\n", " total += 4\n", " if primes * 10 < total:\n", " return side\n", "\n", "\n", "run(euler_58)" ] }, { "cell_type": "markdown", "id": "cell-122", "metadata": {}, "source": [ "## [Problem 59](https://projecteuler.net/problem=59)\n", "\n", "*Recover the 3-character XOR key by frequency analysis (space is most common) and sum the plaintext.*" ] }, { "cell_type": "code", "execution_count": 62, "id": "cell-123", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 59: XOR Decryption 0 msec ⇒ 107359 ✅ " ] }, "execution_count": 62, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_59():\n", " \"\"\"XOR Decryption\"\"\"\n", " data = [int(x) for x in DATA[59].split(\",\")]\n", " key = []\n", " for i in range(3):\n", " col = data[i::3]\n", " common = Counter(col).most_common(1)[0][0]\n", " key.append(common ^ 32)\n", " return sum(c ^ key[i % 3] for i, c in enumerate(data))\n", "\n", "\n", "run(euler_59)" ] }, { "cell_type": "markdown", "id": "cell-124", "metadata": {}, "source": [ "## [Problem 60](https://projecteuler.net/problem=60)\n", "\n", "*DFS for five primes whose every pairwise concatenation is prime; minimize the sum.*" ] }, { "cell_type": "code", "execution_count": 63, "id": "cell-125", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 60: Prime Pair Sets 1,548 msec ⇒ 26033 ✅ 🐌" ] }, "execution_count": 63, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_60():\n", " \"\"\"Prime Pair Sets\"\"\"\n", " @lru_cache(maxsize=None)\n", " def good(a, b):\n", " return is_prime(int(f\"{a}{b}\")) and is_prime(int(f\"{b}{a}\"))\n", "\n", " primes = [p for p in primes_up_to(10000) if p not in (2, 5)]\n", " best = [float(\"inf\")]\n", "\n", " def search(chain, chain_sum, candidates):\n", " if len(chain) == 5:\n", " best[0] = min(best[0], chain_sum)\n", " return\n", " for i, p in enumerate(candidates):\n", " if chain_sum + p >= best[0]:\n", " break\n", " if all(good(p, c) for c in chain):\n", " newc = [q for q in candidates[i + 1:] if good(p, q)]\n", " search(chain + [p], chain_sum + p, newc)\n", "\n", " search([], 0, primes)\n", " return best[0]\n", "\n", "\n", "run(euler_60)" ] }, { "cell_type": "markdown", "id": "cell-126", "metadata": {}, "source": [ "## [Problem 61](https://projecteuler.net/problem=61)\n", "\n", "*DFS chaining 4-digit polygonal numbers (triangle..octagonal) into a cyclic set of six.*" ] }, { "cell_type": "code", "execution_count": 64, "id": "cell-127", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 61: Cyclical Figurate Numbers 1 msec ⇒ 28684 ✅ " ] }, "execution_count": 64, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_61():\n", " \"\"\"Cyclical Figurate Numbers\"\"\"\n", " def poly(s, n):\n", " return n * ((s - 2) * n - (s - 4)) // 2\n", "\n", " polys = {}\n", " for s in range(3, 9):\n", " nums = []\n", " n = 1\n", " while True:\n", " v = poly(s, n)\n", " if v >= 10000:\n", " break\n", " if v >= 1000:\n", " nums.append(v)\n", " n += 1\n", " polys[s] = nums\n", "\n", " def search(chain, used):\n", " if len(chain) == 6:\n", " if str(chain[-1])[2:] == str(chain[0])[:2]:\n", " return chain\n", " return None\n", " last = str(chain[-1])[2:]\n", " for s in range(3, 9):\n", " if s in used:\n", " continue\n", " for num in polys[s]:\n", " if str(num)[:2] == last:\n", " res = search(chain + [num], used | {s})\n", " if res:\n", " return res\n", " return None\n", "\n", " for start in polys[8]:\n", " res = search([start], {8})\n", " if res:\n", " return sum(res)\n", "\n", "\n", "run(euler_61)" ] }, { "cell_type": "markdown", "id": "cell-128", "metadata": {}, "source": [ "## [Problem 62](https://projecteuler.net/problem=62)\n", "\n", "*Group cubes by their sorted digits and return the smallest of the first five-member group.*" ] }, { "cell_type": "code", "execution_count": 65, "id": "cell-129", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 62: Cubic Permutations 4 msec ⇒ 127035954683 ✅ " ] }, "execution_count": 65, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_62():\n", " \"\"\"Cubic Permutations\"\"\"\n", " groups = defaultdict(list)\n", " n = 0\n", " while True:\n", " n += 1\n", " c = n ** 3\n", " key = \"\".join(sorted(str(c)))\n", " groups[key].append(c)\n", " if len(groups[key]) == 5:\n", " return min(groups[key])\n", "\n", "\n", "run(euler_62)" ] }, { "cell_type": "markdown", "id": "cell-130", "metadata": {}, "source": [ "## [Problem 63](https://projecteuler.net/problem=63)\n", "\n", "*Count n-digit numbers that are perfect nth powers.*" ] }, { "cell_type": "code", "execution_count": 66, "id": "cell-131", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 63: Powerful Digit Counts 0 msec ⇒ 49 ✅ " ] }, "execution_count": 66, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_63():\n", " \"\"\"Powerful Digit Counts\"\"\"\n", " return sum(\n", " 1\n", " for n in range(1, 30)\n", " for b in range(1, 10)\n", " if len(str(b ** n)) == n\n", " )\n", "\n", "\n", "run(euler_63)" ] }, { "cell_type": "markdown", "id": "cell-132", "metadata": {}, "source": [ "## [Problem 64](https://projecteuler.net/problem=64)\n", "\n", "*Count square roots (n ≤ 10000) whose continued-fraction period is odd.*" ] }, { "cell_type": "code", "execution_count": 67, "id": "cell-133", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 64: Odd Period Square Roots 20 msec ⇒ 1322 ✅ " ] }, "execution_count": 67, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_64():\n", " \"\"\"Odd Period Square Roots\"\"\"\n", " count = 0\n", " for n in range(2, 10001):\n", " _, period = continued_fraction_sqrt(n)\n", " if period and len(period) % 2 == 1:\n", " count += 1\n", " return count\n", "\n", "\n", "run(euler_64)" ] }, { "cell_type": "markdown", "id": "cell-134", "metadata": {}, "source": [ "## [Problem 65](https://projecteuler.net/problem=65)\n", "\n", "*Build the 100th convergent of e via its continued fraction; return the numerator's digit sum.*" ] }, { "cell_type": "code", "execution_count": 68, "id": "cell-135", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 65: Convergents of e 0 msec ⇒ 272 ✅ " ] }, "execution_count": 68, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_65():\n", " \"\"\"Convergents of e\"\"\"\n", " terms = [2]\n", " k = 1\n", " while len(terms) < 100:\n", " terms += [1, 2 * k, 1]\n", " k += 1\n", " terms = terms[:100]\n", " val = Fraction(terms[-1])\n", " for a in reversed(terms[:-1]):\n", " val = a + 1 / val\n", " return digit_sum(val.numerator)\n", "\n", "\n", "run(euler_65)" ] }, { "cell_type": "markdown", "id": "cell-136", "metadata": {}, "source": [ "## [Problem 66](https://projecteuler.net/problem=66)\n", "\n", "*Solve each Pell equation via continued fractions; return the D with the largest minimal solution.*" ] }, { "cell_type": "code", "execution_count": 69, "id": "cell-137", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 66: Diophantine Equation 2 msec ⇒ 661 ✅ " ] }, "execution_count": 69, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_66():\n", " \"\"\"Diophantine Equation\"\"\"\n", " best_x, best_D = 0, 0\n", " for D in range(2, 1001):\n", " a0, period = continued_fraction_sqrt(D)\n", " if not period:\n", " continue\n", " h_prev, h = 1, a0\n", " k_prev, k = 0, 1\n", " i = 0\n", " while h * h - D * k * k != 1:\n", " a = period[i % len(period)]\n", " i += 1\n", " h_prev, h = h, a * h + h_prev\n", " k_prev, k = k, a * k + k_prev\n", " if h > best_x:\n", " best_x, best_D = h, D\n", " return best_D\n", "\n", "\n", "run(euler_66)" ] }, { "cell_type": "markdown", "id": "cell-138", "metadata": {}, "source": [ "## [Problem 67](https://projecteuler.net/problem=67)\n", "\n", "*Same bottom-up triangle DP as Problem 18, on the large bundled triangle.*" ] }, { "cell_type": "code", "execution_count": 70, "id": "cell-139", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 67: Maximum Path Sum II 0 msec ⇒ 7273 ✅ " ] }, "execution_count": 70, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_67():\n", " \"\"\"Maximum Path Sum II\"\"\"\n", " rows = read_grid(DATA[67])\n", " return _max_triangle_path(rows)\n", "\n", "\n", "run(euler_67)" ] }, { "cell_type": "markdown", "id": "cell-140", "metadata": {}, "source": [ "## [Problem 68](https://projecteuler.net/problem=68)\n", "\n", "*Search permutations of 1–10 for the maximum 16-digit magic 5-gon ring string.*" ] }, { "cell_type": "code", "execution_count": 71, "id": "cell-141", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 68: Magic 5-gon Ring 5 msec ⇒ 6531031914842725 ✅ " ] }, "execution_count": 71, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_68():\n", " \"\"\"Magic 5-gon Ring\"\"\"\n", " best = 0\n", " universe = set(range(1, 11))\n", " for inner in permutations(range(1, 11), 5):\n", " if 10 in inner:\n", " continue\n", " outer_set = universe - set(inner)\n", " s = sum(inner)\n", " if (55 + s) % 5 != 0:\n", " continue\n", " L = (55 + s) // 5\n", " outer = []\n", " ok = True\n", " for i in range(5):\n", " o = L - inner[i] - inner[(i + 1) % 5]\n", " if o not in outer_set or o in outer:\n", " ok = False\n", " break\n", " outer.append(o)\n", " if not ok or set(outer) != outer_set:\n", " continue\n", " start = outer.index(min(outer))\n", " groups = [\n", " (outer[(start + i) % 5], inner[(start + i) % 5],\n", " inner[(start + i + 1) % 5])\n", " for i in range(5)\n", " ]\n", " text = \"\".join(str(x) for g in groups for x in g)\n", " if len(text) == 16:\n", " best = max(best, int(text))\n", " return best\n", "\n", "\n", "run(euler_68)" ] }, { "cell_type": "markdown", "id": "cell-142", "metadata": {}, "source": [ "## [Problem 69](https://projecteuler.net/problem=69)\n", "\n", "*Maximize n/φ(n) by multiplying successive primes (primorial) while staying under a million.*" ] }, { "cell_type": "code", "execution_count": 72, "id": "cell-143", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 69: Totient Maximum 0 msec ⇒ 510510 ✅ " ] }, "execution_count": 72, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_69():\n", " \"\"\"Totient Maximum\"\"\"\n", " result, i = 1, 1\n", " while True:\n", " p = nth_prime(i)\n", " if result * p > 1_000_000:\n", " return result\n", " result *= p\n", " i += 1\n", "\n", "\n", "run(euler_69)" ] }, { "cell_type": "markdown", "id": "cell-144", "metadata": {}, "source": [ "## [Problem 70](https://projecteuler.net/problem=70)\n", "\n", "*Search n = p·q with φ(n) a permutation of n, minimizing the ratio n/φ(n).*" ] }, { "cell_type": "code", "execution_count": 73, "id": "cell-145", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 70: Totient Permutation 12 msec ⇒ 8319823 ✅ " ] }, "execution_count": 73, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_70():\n", " \"\"\"Totient Permutation\"\"\"\n", " LIMIT = 10 ** 7\n", " primes = primes_in_range(2000, 5000)\n", " best_ratio, best_n = 10.0, 0\n", " for i, p in enumerate(primes):\n", " for q in primes[i:]:\n", " n = p * q\n", " if n >= LIMIT:\n", " break\n", " phi = (p - 1) * (q - 1)\n", " if is_permutation(n, phi):\n", " ratio = n / phi\n", " if ratio < best_ratio:\n", " best_ratio, best_n = ratio, n\n", " return best_n\n", "\n", "\n", "run(euler_70)" ] }, { "cell_type": "markdown", "id": "cell-146", "metadata": {}, "source": [ "## [Problem 71](https://projecteuler.net/problem=71)\n", "\n", "*Scan denominators for the fraction just below 3/7 (mediant / Farey neighbour).*" ] }, { "cell_type": "code", "execution_count": 74, "id": "cell-147", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 71: Ordered Fractions 62 msec ⇒ 428570 ✅ " ] }, "execution_count": 74, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_71():\n", " \"\"\"Ordered Fractions\"\"\"\n", " n, d = 0, 1\n", " for b in range(1, 1_000_001):\n", " a = (3 * b - 1) // 7\n", " if a * d > n * b:\n", " n, d = a, b\n", " return n\n", "\n", "\n", "run(euler_71)" ] }, { "cell_type": "markdown", "id": "cell-148", "metadata": {}, "source": [ "## [Problem 72](https://projecteuler.net/problem=72)\n", "\n", "*The count of reduced proper fractions is the sum of Euler's totient up to a million.*" ] }, { "cell_type": "code", "execution_count": 75, "id": "cell-149", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 72: Counting Fractions 382 msec ⇒ 303963552391 ✅ " ] }, "execution_count": 75, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_72():\n", " \"\"\"Counting Fractions\"\"\"\n", " phi = totient_sieve(1_000_000)\n", " return sum(phi[2:])\n", "\n", "\n", "run(euler_72)" ] }, { "cell_type": "markdown", "id": "cell-150", "metadata": {}, "source": [ "## [Problem 73](https://projecteuler.net/problem=73)\n", "\n", "*Count reduced fractions strictly between 1/3 and 1/2 for denominators up to 12000.*" ] }, { "cell_type": "code", "execution_count": 76, "id": "cell-151", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 73: Counting Fractions in a Range 730 msec ⇒ 7295372 ✅ " ] }, "execution_count": 76, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_73():\n", " \"\"\"Counting Fractions in a Range\"\"\"\n", " count = 0\n", " for d in range(2, 12001):\n", " for n in range(d // 3 + 1, (d - 1) // 2 + 1):\n", " if gcd(n, d) == 1:\n", " count += 1\n", " return count\n", "\n", "\n", "run(euler_73)" ] }, { "cell_type": "markdown", "id": "cell-152", "metadata": {}, "source": [ "## [Problem 74](https://projecteuler.net/problem=74)\n", "\n", "*Memoize digit-factorial chain lengths and count starts with a chain of exactly 60.*" ] }, { "cell_type": "code", "execution_count": 77, "id": "cell-153", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 74: Digit Factorial Chains 630 msec ⇒ 402 ✅ " ] }, "execution_count": 77, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_74():\n", " \"\"\"Digit Factorial Chains\"\"\"\n", " fact = [factorial(i) for i in range(10)]\n", "\n", " def nxt(n):\n", " return sum(fact[int(c)] for c in str(n))\n", "\n", " cache = {}\n", "\n", " def chain_len(n):\n", " seen = {}\n", " cur, steps = n, 0\n", " while cur not in seen:\n", " if cur in cache:\n", " total = steps + cache[cur]\n", " for k, v in seen.items():\n", " cache[k] = total - v\n", " return total\n", " seen[cur] = steps\n", " cur = nxt(cur)\n", " steps += 1\n", " total = steps\n", " for k, v in seen.items():\n", " cache[k] = total - v\n", " return total\n", "\n", " return sum(1 for n in range(1, 1_000_000) if chain_len(n) == 60)\n", "\n", "\n", "run(euler_74)" ] }, { "cell_type": "markdown", "id": "cell-154", "metadata": {}, "source": [ "## [Problem 75](https://projecteuler.net/problem=75)\n", "\n", "*Generate primitive Pythagorean triples (Euclid's formula) and count perimeters formed exactly once.*" ] }, { "cell_type": "code", "execution_count": 78, "id": "cell-155", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 75: Singular Integer Right Triangles 100 msec ⇒ 161667 ✅ " ] }, "execution_count": 78, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_75():\n", " \"\"\"Singular Integer Right Triangles\"\"\"\n", " LIMIT = 1_500_000\n", " counts = bytearray(LIMIT + 1)\n", " m = 2\n", " while 2 * m * m <= LIMIT:\n", " for n in range(1, m):\n", " if (m - n) % 2 == 1 and gcd(m, n) == 1:\n", " p = 2 * m * (m + n)\n", " if p <= LIMIT:\n", " for k in range(p, LIMIT + 1, p):\n", " if counts[k] < 255:\n", " counts[k] += 1\n", " m += 1\n", " return sum(1 for c in counts if c == 1)\n", "\n", "\n", "run(euler_75)" ] }, { "cell_type": "markdown", "id": "cell-156", "metadata": {}, "source": [ "## [Problem 76](https://projecteuler.net/problem=76)\n", "\n", "*Partition-count DP using parts 1..99 (summations of at least two positives).*" ] }, { "cell_type": "code", "execution_count": 79, "id": "cell-157", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 76: Counting Summations 0 msec ⇒ 190569291 ✅ " ] }, "execution_count": 79, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_76():\n", " \"\"\"Counting Summations\"\"\"\n", " target = 100\n", " ways = [1] + [0] * target\n", " for i in range(1, target):\n", " for j in range(i, target + 1):\n", " ways[j] += ways[j - i]\n", " return ways[target]\n", "\n", "\n", "run(euler_76)" ] }, { "cell_type": "markdown", "id": "cell-158", "metadata": {}, "source": [ "## [Problem 77](https://projecteuler.net/problem=77)\n", "\n", "*Prime-partition DP, increasing n until the number of prime summations exceeds 5000.*" ] }, { "cell_type": "code", "execution_count": 80, "id": "cell-159", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 77: Prime Summations 1 msec ⇒ 71 ✅ " ] }, "execution_count": 80, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_77():\n", " \"\"\"Prime Summations\"\"\"\n", " primes = primes_up_to(100)\n", " n = 1\n", " while True:\n", " n += 1\n", " ways = [1] + [0] * n\n", " for p in primes:\n", " if p > n:\n", " break\n", " for j in range(p, n + 1):\n", " ways[j] += ways[j - p]\n", " if ways[n] > 5000:\n", " return n\n", "\n", "\n", "run(euler_77)" ] }, { "cell_type": "markdown", "id": "cell-160", "metadata": {}, "source": [ "## [Problem 78](https://projecteuler.net/problem=78)\n", "\n", "*Compute the partition function via the pentagonal-number recurrence mod 10⁶ until a value is 0.*" ] }, { "cell_type": "code", "execution_count": 81, "id": "cell-161", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 78: Coin Partitions 1,209 msec ⇒ 55374 ✅ 🐌" ] }, "execution_count": 81, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_78():\n", " \"\"\"Coin Partitions\"\"\"\n", " mod = 10 ** 6\n", " p = [1]\n", " n = 0\n", " while True:\n", " n += 1\n", " total = 0\n", " k = 1\n", " while True:\n", " g1 = k * (3 * k - 1) // 2\n", " g2 = k * (3 * k + 1) // 2\n", " if g1 > n:\n", " break\n", " sign = 1 if k % 2 == 1 else -1\n", " total += sign * p[n - g1]\n", " if g2 <= n:\n", " total += sign * p[n - g2]\n", " k += 1\n", " total %= mod\n", " p.append(total)\n", " if total == 0:\n", " return n\n", "\n", "\n", "run(euler_78)" ] }, { "cell_type": "markdown", "id": "cell-162", "metadata": {}, "source": [ "## [Problem 79](https://projecteuler.net/problem=79)\n", "\n", "*Topologically sort the digit successor constraints from the keylog into the passcode.*" ] }, { "cell_type": "code", "execution_count": 82, "id": "cell-163", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 79: Passcode Derivation 0 msec ⇒ 73162890 ✅ " ] }, "execution_count": 82, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_79():\n", " \"\"\"Passcode Derivation\"\"\"\n", " succ = defaultdict(set)\n", " chars = set()\n", " for tok in DATA[79].split():\n", " a, b, c = tok[0], tok[1], tok[2]\n", " chars |= {a, b, c}\n", " succ[a].add(b)\n", " succ[b].add(c)\n", " result = \"\"\n", " remaining = set(chars)\n", " while remaining:\n", " for ch in sorted(remaining):\n", " if not any(ch in succ[o] for o in remaining):\n", " result += ch\n", " remaining.discard(ch)\n", " break\n", " else:\n", " break\n", " return int(result)\n", "\n", "\n", "run(euler_79)" ] }, { "cell_type": "markdown", "id": "cell-164", "metadata": {}, "source": [ "## [Problem 80](https://projecteuler.net/problem=80)\n", "\n", "*Take integer square roots at high precision and sum the first 100 digits of each non-square.*" ] }, { "cell_type": "code", "execution_count": 83, "id": "cell-165", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 80: Square Root Digital Expansion 0 msec ⇒ 40886 ✅ " ] }, "execution_count": 83, "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", " r = isqrt(n)\n", " if r * r == n:\n", " continue\n", " val = isqrt(n * 10 ** (2 * 110))\n", " total += sum(int(c) for c in str(val)[:100])\n", " return total\n", "\n", "\n", "run(euler_80)" ] }, { "cell_type": "markdown", "id": "cell-166", "metadata": {}, "source": [ "## [Problem 81](https://projecteuler.net/problem=81)\n", "\n", "*DP moving only right/down through the matrix, minimizing the path sum.*" ] }, { "cell_type": "code", "execution_count": 84, "id": "cell-167", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 81: Path Sum 1 msec ⇒ 427337 ✅ " ] }, "execution_count": 84, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_81():\n", " \"\"\"Path Sum: Two Ways\"\"\"\n", " g = _read_matrix(DATA[81])\n", " n = len(g)\n", " dp = [[0] * n for _ in range(n)]\n", " for r in range(n - 1, -1, -1):\n", " for c in range(n - 1, -1, -1):\n", " if r == n - 1 and c == n - 1:\n", " dp[r][c] = g[r][c]\n", " elif r == n - 1:\n", " dp[r][c] = g[r][c] + dp[r][c + 1]\n", " elif c == n - 1:\n", " dp[r][c] = g[r][c] + dp[r + 1][c]\n", " else:\n", " dp[r][c] = g[r][c] + min(dp[r + 1][c], dp[r][c + 1])\n", " return dp[0][0]\n", "\n", "\n", "run(euler_81)" ] }, { "cell_type": "markdown", "id": "cell-168", "metadata": {}, "source": [ "## [Problem 82](https://projecteuler.net/problem=82)\n", "\n", "*Column-by-column DP allowing up, down, and right moves across the matrix.*" ] }, { "cell_type": "code", "execution_count": 85, "id": "cell-169", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 82: Path Sum 1 msec ⇒ 260324 ✅ " ] }, "execution_count": 85, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_82():\n", " \"\"\"Path Sum: Three Ways\"\"\"\n", " g = _read_matrix(DATA[82])\n", " n = len(g)\n", " cost = [g[r][n - 1] for r in range(n)]\n", " for c in range(n - 2, -1, -1):\n", " new = [0] * n\n", " new[0] = g[0][c] + cost[0]\n", " for r in range(1, n):\n", " new[r] = g[r][c] + min(new[r - 1], cost[r])\n", " for r in range(n - 2, -1, -1):\n", " new[r] = min(new[r], g[r][c] + new[r + 1])\n", " cost = new\n", " return min(cost)\n", "\n", "\n", "run(euler_82)" ] }, { "cell_type": "markdown", "id": "cell-170", "metadata": {}, "source": [ "## [Problem 83](https://projecteuler.net/problem=83)\n", "\n", "*Dijkstra over the grid with movement in all four directions.*" ] }, { "cell_type": "code", "execution_count": 86, "id": "cell-171", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 83: Path Sum 4 msec ⇒ 425185 ✅ " ] }, "execution_count": 86, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_83():\n", " \"\"\"Path Sum: Four Ways\"\"\"\n", " g = _read_matrix(DATA[83])\n", " n = len(g)\n", " INF = float(\"inf\")\n", " dist = [[INF] * n for _ in range(n)]\n", " dist[0][0] = g[0][0]\n", " pq = [(g[0][0], 0, 0)]\n", " while pq:\n", " d, r, c = heappop(pq)\n", " if d > dist[r][c]:\n", " continue\n", " for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):\n", " nr, nc = r + dr, c + dc\n", " if 0 <= nr < n and 0 <= nc < n:\n", " nd = d + g[nr][nc]\n", " if nd < dist[nr][nc]:\n", " dist[nr][nc] = nd\n", " heappush(pq, (nd, nr, nc))\n", " return dist[n - 1][n - 1]\n", "\n", "\n", "run(euler_83)" ] }, { "cell_type": "markdown", "id": "cell-172", "metadata": {}, "source": [ "## [Problem 84](https://projecteuler.net/problem=84)\n", "\n", "*Build the Monopoly Markov transition matrix (cards, jail, doubles) and find the stationary distribution.*" ] }, { "cell_type": "code", "execution_count": 87, "id": "cell-173", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 84: Monopoly Odds 2 msec ⇒ 101524 ✅ " ] }, "execution_count": 87, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_84():\n", " \"\"\"Monopoly Odds\"\"\"\n", " railways = [5, 15, 25, 35]\n", " utilities = [12, 28]\n", "\n", " def next_in(pos, lst):\n", " for x in lst:\n", " if x > pos:\n", " return x\n", " return lst[0]\n", "\n", " def resolve(land):\n", " if land == 30:\n", " return {10: 1.0}\n", " if land in (7, 22, 36):\n", " res = defaultdict(float)\n", " per = 1 / 16\n", " for d in (0, 10, 11, 24, 39, 5):\n", " res[d] += per\n", " res[next_in(land, railways)] += 2 * per\n", " res[next_in(land, utilities)] += per\n", " for d, pr in resolve((land - 3) % 40).items():\n", " res[d] += per * pr\n", " res[land] += 6 * per\n", " return res\n", " if land in (2, 17, 33):\n", " res = defaultdict(float)\n", " per = 1 / 16\n", " res[0] += per\n", " res[10] += per\n", " res[land] += 14 * per\n", " return res\n", " return {land: 1.0}\n", "\n", " dist = defaultdict(int)\n", " for a in range(1, 5):\n", " for b in range(1, 5):\n", " dist[a + b] += 1\n", " T = np.zeros((40, 40))\n", " for s in range(40):\n", " for roll, cnt in dist.items():\n", " p = cnt / 16\n", " for dest, pp in resolve((s + roll) % 40).items():\n", " T[s][dest] += p * pp\n", " v = np.ones(40) / 40\n", " for _ in range(3000):\n", " v = v @ T\n", " top = sorted(range(40), key=lambda i: v[i], reverse=True)[:3]\n", " return int(\"\".join(f\"{i:02d}\" for i in top))\n", "\n", "\n", "run(euler_84)" ] }, { "cell_type": "markdown", "id": "cell-174", "metadata": {}, "source": [ "## [Problem 85](https://projecteuler.net/problem=85)\n", "\n", "*Closed-form rectangle count over grid sizes, minimizing the distance to two million.*" ] }, { "cell_type": "code", "execution_count": 88, "id": "cell-175", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 85: Counting Rectangles 1 msec ⇒ 2772 ✅ " ] }, "execution_count": 88, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_85():\n", " \"\"\"Counting Rectangles\"\"\"\n", " target = 2_000_000\n", " best = None\n", " for m in range(1, 100):\n", " for n in range(1, 100):\n", " cnt = (m * (m + 1) // 2) * (n * (n + 1) // 2)\n", " diff = abs(cnt - target)\n", " if best is None or diff < best[0]:\n", " best = (diff, m * n)\n", " return best[1]\n", "\n", "\n", "run(euler_85)" ] }, { "cell_type": "markdown", "id": "cell-176", "metadata": {}, "source": [ "## [Problem 86](https://projecteuler.net/problem=86)\n", "\n", "*Count cuboids with an integer shortest surface path, growing M until the running total passes a million.*" ] }, { "cell_type": "code", "execution_count": 89, "id": "cell-177", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 86: Cuboid Route 190 msec ⇒ 1818 ✅ " ] }, "execution_count": 89, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_86():\n", " \"\"\"Cuboid Route\"\"\"\n", " LIMIT = 1_000_000\n", " M, total = 0, 0\n", " while total <= LIMIT:\n", " M += 1\n", " c = M\n", " for ab in range(2, 2 * c + 1):\n", " d2 = ab * ab + c * c\n", " d = isqrt(d2)\n", " if d * d == d2:\n", " if ab <= c:\n", " total += ab // 2\n", " else:\n", " total += ab // 2 - (ab - c - 1)\n", " return M\n", "\n", "\n", "run(euler_86)" ] }, { "cell_type": "markdown", "id": "cell-178", "metadata": {}, "source": [ "## [Problem 87](https://projecteuler.net/problem=87)\n", "\n", "*Sum the distinct values a² + b³ + c⁴ below fifty million over prime a, b, c.*" ] }, { "cell_type": "code", "execution_count": 90, "id": "cell-179", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 87: Prime Power Triples 159 msec ⇒ 1097343 ✅ " ] }, "execution_count": 90, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_87():\n", " \"\"\"Prime Power Triples\"\"\"\n", " LIMIT = 50_000_000\n", " primes = primes_up_to(isqrt(LIMIT) + 1)\n", " found = set()\n", " for c in primes:\n", " c4 = c ** 4\n", " if c4 >= LIMIT:\n", " break\n", " for b in primes:\n", " b3 = b ** 3\n", " if c4 + b3 >= LIMIT:\n", " break\n", " for a in primes:\n", " v = c4 + b3 + a * a\n", " if v >= LIMIT:\n", " break\n", " found.add(v)\n", " return len(found)\n", "\n", "\n", "run(euler_87)" ] }, { "cell_type": "markdown", "id": "cell-180", "metadata": {}, "source": [ "## [Problem 88](https://projecteuler.net/problem=88)\n", "\n", "*DFS over factorizations to find the minimal product-sum number for each k, then sum the distinct ones.*" ] }, { "cell_type": "code", "execution_count": 91, "id": "cell-181", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 88: Product-sum Numbers 58 msec ⇒ 7587457 ✅ " ] }, "execution_count": 91, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_88():\n", " \"\"\"Product-sum Numbers\"\"\"\n", " LIMIT = 12000\n", " min_ps = [2 * LIMIT] * (LIMIT + 1)\n", "\n", " def search(prod_, summ, cnt, start):\n", " if cnt >= 2:\n", " k = prod_ - summ + cnt\n", " if k <= LIMIT and prod_ < min_ps[k]:\n", " min_ps[k] = prod_\n", " for f in range(start, (2 * LIMIT) // prod_ + 1):\n", " search(prod_ * f, summ + f, cnt + 1, f)\n", "\n", " search(1, 0, 0, 2)\n", " return sum(set(min_ps[2:]))\n", "\n", "\n", "run(euler_88)" ] }, { "cell_type": "markdown", "id": "cell-182", "metadata": {}, "source": [ "## [Problem 89](https://projecteuler.net/problem=89)\n", "\n", "*Parse each Roman numeral and re-encode it minimally, summing the characters saved.*" ] }, { "cell_type": "code", "execution_count": 92, "id": "cell-183", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 89: Roman Numerals 1 msec ⇒ 743 ✅ " ] }, "execution_count": 92, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_89():\n", " \"\"\"Roman Numerals\"\"\"\n", " vals = {\"I\": 1, \"V\": 5, \"X\": 10, \"L\": 50, \"C\": 100, \"D\": 500, \"M\": 1000}\n", "\n", " def to_int(s):\n", " total = 0\n", " for i, ch in enumerate(s):\n", " if i + 1 < len(s) and vals[ch] < vals[s[i + 1]]:\n", " total -= vals[ch]\n", " else:\n", " total += vals[ch]\n", " return total\n", "\n", " table = [(1000, \"M\"), (900, \"CM\"), (500, \"D\"), (400, \"CD\"), (100, \"C\"),\n", " (90, \"XC\"), (50, \"L\"), (40, \"XL\"), (10, \"X\"), (9, \"IX\"),\n", " (5, \"V\"), (4, \"IV\"), (1, \"I\")]\n", "\n", " def to_roman(n):\n", " res = \"\"\n", " for v, sym in table:\n", " while n >= v:\n", " res += sym\n", " n -= v\n", " return res\n", "\n", " return sum(\n", " len(line) - len(to_roman(to_int(line)))\n", " for line in DATA[89].split()\n", " )\n", "\n", "\n", "run(euler_89)" ] }, { "cell_type": "markdown", "id": "cell-184", "metadata": {}, "source": [ "## [Problem 90](https://projecteuler.net/problem=90)\n", "\n", "*Search pairs of dice faces that can display every two-digit square (with the 6/9 swap).*" ] }, { "cell_type": "code", "execution_count": 93, "id": "cell-185", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 90: Cube Digit Pairs 12 msec ⇒ 1217 ✅ " ] }, "execution_count": 93, "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),\n", " (6, 4), (8, 1)]\n", "\n", " def has(cube, d):\n", " if d in (6, 9):\n", " return 6 in cube or 9 in cube\n", " return d in cube\n", "\n", " def works(c1, c2):\n", " return all(\n", " (has(c1, a) and has(c2, b)) or (has(c1, b) and has(c2, a))\n", " for a, b in squares\n", " )\n", "\n", " cubes = list(combinations(range(10), 6))\n", " count = 0\n", " for i in range(len(cubes)):\n", " for j in range(i, len(cubes)):\n", " if works(cubes[i], cubes[j]):\n", " count += 1\n", " return count\n", "\n", "\n", "run(euler_90)" ] }, { "cell_type": "markdown", "id": "cell-186", "metadata": {}, "source": [ "## [Problem 91](https://projecteuler.net/problem=91)\n", "\n", "*Count right triangles with one vertex at the origin and the others on the grid.*" ] }, { "cell_type": "code", "execution_count": 94, "id": "cell-187", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 91: Right Triangles with Integer Coordinates 1,273 msec ⇒ 14234 ✅ 🐌" ] }, "execution_count": 94, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_91():\n", " \"\"\"Right Triangles with Integer Coordinates\"\"\"\n", " N = 50\n", " pts = [(x, y) for x in range(N + 1) for y in range(N + 1)\n", " if (x, y) != (0, 0)]\n", "\n", " def right(p, q):\n", " o = (0, 0)\n", " for a, b, c in ((o, p, q), (p, o, q), (q, o, p)):\n", " v1 = (b[0] - a[0], b[1] - a[1])\n", " v2 = (c[0] - a[0], c[1] - a[1])\n", " if v1[0] * v2[0] + v1[1] * v2[1] == 0:\n", " return True\n", " return False\n", "\n", " count = 0\n", " for i in range(len(pts)):\n", " for j in range(i + 1, len(pts)):\n", " if right(pts[i], pts[j]):\n", " count += 1\n", " return count\n", "\n", "\n", "run(euler_91)" ] }, { "cell_type": "markdown", "id": "cell-188", "metadata": {}, "source": [ "## [Problem 92](https://projecteuler.net/problem=92)\n", "\n", "*Precompute square-digit-chain outcomes for 1..567 and count starts reaching 89.*" ] }, { "cell_type": "code", "execution_count": 95, "id": "cell-189", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 92: Square Digit Chains 4,565 msec ⇒ 8581146 ✅ 🐌" ] }, "execution_count": 95, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_92():\n", " \"\"\"Square Digit Chains\"\"\"\n", " def sds(n):\n", " return sum(int(c) ** 2 for c in str(n))\n", " outcome = [0] * 568\n", " for n in range(1, 568):\n", " m = n\n", " while m != 1 and m != 89:\n", " m = sds(m)\n", " outcome[n] = m\n", " return sum(1 for n in range(1, 10_000_000) if outcome[sds(n)] == 89)\n", "\n", "\n", "run(euler_92)" ] }, { "cell_type": "markdown", "id": "cell-190", "metadata": {}, "source": [ "## [Problem 93](https://projecteuler.net/problem=93)\n", "\n", "*Try all operator and parenthesization combinations on each digit set for the longest run 1..n.*" ] }, { "cell_type": "code", "execution_count": 96, "id": "cell-191", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 93: Arithmetic Expressions 1,035 msec ⇒ 1258 ✅ 🐌" ] }, "execution_count": 96, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_93():\n", " \"\"\"Arithmetic Expressions\"\"\"\n", " OPS = {\"+\": operator.add, \"-\": operator.sub, \"*\": operator.mul}\n", "\n", " def ap(o, x, y):\n", " if x is None or y is None:\n", " return None\n", " if o == \"/\":\n", " return x / y if y != 0 else None\n", " return OPS[o](x, y)\n", "\n", " def values(nums):\n", " vals = set()\n", " for p in permutations(nums):\n", " a, b, c, d = map(Fraction, p)\n", " for o1, o2, o3 in product(\"+-*/\", repeat=3):\n", " for v in (\n", " ap(o3, ap(o2, ap(o1, a, b), c), d),\n", " ap(o3, ap(o1, a, b), ap(o2, c, d)),\n", " ap(o1, a, ap(o3, ap(o2, b, c), d)),\n", " ap(o1, a, ap(o2, b, ap(o3, c, d))),\n", " ap(o2, ap(o1, a, b), ap(o3, c, d)),\n", " ):\n", " if v is not None and v.denominator == 1 and v > 0:\n", " vals.add(int(v))\n", " return vals\n", "\n", " best_len, best_digits = 0, \"\"\n", " for combo in combinations(range(1, 10), 4):\n", " vals = values(combo)\n", " n = 1\n", " while n in vals:\n", " n += 1\n", " if n - 1 > best_len:\n", " best_len = n - 1\n", " best_digits = \"\".join(map(str, combo))\n", " return int(best_digits)\n", "\n", "\n", "run(euler_93)" ] }, { "cell_type": "markdown", "id": "cell-192", "metadata": {}, "source": [ "## [Problem 94](https://projecteuler.net/problem=94)\n", "\n", "*Use two Pell-like recurrences to sum perimeters of near-equilateral integer-area triangles.*" ] }, { "cell_type": "code", "execution_count": 97, "id": "cell-193", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 94: Almost Equilateral Triangles 0 msec ⇒ 518408346 ✅ " ] }, "execution_count": 97, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_94():\n", " \"\"\"Almost Equilateral Triangles\"\"\"\n", " LIMIT = 10 ** 9\n", " total = 0\n", " prev, cur = 1, 5 # family: base = side + 1\n", " while 3 * cur + 1 <= LIMIT:\n", " total += 3 * cur + 1\n", " prev, cur = cur, 14 * cur - prev - 4\n", " prev, cur = 1, 17 # family: base = side - 1\n", " while 3 * cur - 1 <= LIMIT:\n", " total += 3 * cur - 1\n", " prev, cur = cur, 14 * cur - prev + 4\n", " return total\n", "\n", "\n", "run(euler_94)" ] }, { "cell_type": "markdown", "id": "cell-194", "metadata": {}, "source": [ "## [Problem 95](https://projecteuler.net/problem=95)\n", "\n", "*Follow proper-divisor-sum chains to find the longest amicable cycle; return its smallest member.*" ] }, { "cell_type": "code", "execution_count": 98, "id": "cell-195", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 95: Amicable Chains 1,813 msec ⇒ 14316 ✅ 🐌" ] }, "execution_count": 98, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_95():\n", " \"\"\"Amicable Chains\"\"\"\n", " LIMIT = 10 ** 6\n", " s = divisor_sum_sieve(LIMIT)\n", " best_len, best_min = 0, 0\n", " for start in range(2, LIMIT + 1):\n", " seen = {}\n", " n, step = start, 0\n", " while n <= LIMIT and n > 1 and n not in seen:\n", " seen[n] = step\n", " n = s[n]\n", " step += 1\n", " if n in seen:\n", " cycle = [k for k, v in seen.items() if v >= seen[n]]\n", " if len(cycle) > best_len:\n", " best_len, best_min = len(cycle), min(cycle)\n", " return best_min\n", "\n", "\n", "run(euler_95)" ] }, { "cell_type": "markdown", "id": "cell-196", "metadata": {}, "source": [ "## [Problem 96](https://projecteuler.net/problem=96)\n", "\n", "*Bitmask backtracking with a minimum-remaining-values heuristic; sum each grid's top-left three digits.*" ] }, { "cell_type": "code", "execution_count": 99, "id": "cell-197", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 96: Su Doku 57 msec ⇒ 24702 ✅ " ] }, "execution_count": 99, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_96():\n", " \"\"\"Su Doku\"\"\"\n", " def solve(board):\n", " rows = [0] * 9\n", " cols = [0] * 9\n", " boxes = [0] * 9\n", " for i in range(81):\n", " v = board[i]\n", " if v:\n", " r, c = divmod(i, 9)\n", " b = (r // 3) * 3 + c // 3\n", " bit = 1 << v\n", " rows[r] |= bit\n", " cols[c] |= bit\n", " boxes[b] |= bit\n", "\n", " def bt():\n", " best = -1\n", " best_mask = 0\n", " best_count = 10\n", " for i in range(81):\n", " if board[i] == 0:\n", " r, c = divmod(i, 9)\n", " b = (r // 3) * 3 + c // 3\n", " cand = (~(rows[r] | cols[c] | boxes[b])) & 0x3FE\n", " cnt = bin(cand).count(\"1\")\n", " if cnt < best_count:\n", " best_count, best, best_mask = cnt, i, cand\n", " if cnt == 0:\n", " break\n", " if best == -1:\n", " return True\n", " if best_count == 0:\n", " return False\n", " i = best\n", " r, c = divmod(i, 9)\n", " b = (r // 3) * 3 + c // 3\n", " mask = best_mask\n", " while mask:\n", " bit = mask & (-mask)\n", " mask -= bit\n", " v = bit.bit_length() - 1\n", " board[i] = v\n", " rows[r] |= bit\n", " cols[c] |= bit\n", " boxes[b] |= bit\n", " if bt():\n", " return True\n", " board[i] = 0\n", " rows[r] &= ~bit\n", " cols[c] &= ~bit\n", " boxes[b] &= ~bit\n", " return False\n", "\n", " bt()\n", " return board\n", "\n", " lines = [l.strip() for l in DATA[96].splitlines()\n", " if l.strip()]\n", " total = 0\n", " i = 0\n", " while i < len(lines):\n", " if lines[i].startswith(\"Grid\"):\n", " i += 1\n", " board = [int(ch) for row in lines[i:i + 9] for ch in row]\n", " i += 9\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-198", "metadata": {}, "source": [ "## [Problem 97](https://projecteuler.net/problem=97)\n", "\n", "*Modular exponentiation to get the last ten digits of 28433·2⁷⁸³⁰⁴⁵⁷ + 1.*" ] }, { "cell_type": "code", "execution_count": 100, "id": "cell-199", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 97: Large Non-Mersenne Prime 0 msec ⇒ 8739992577 ✅ " ] }, "execution_count": 100, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_97():\n", " \"\"\"Large Non-Mersenne Prime\"\"\"\n", " mod = 10 ** 10\n", " return (28433 * pow(2, 7830457, mod) + 1) % mod\n", "\n", "\n", "run(euler_97)" ] }, { "cell_type": "markdown", "id": "cell-200", "metadata": {}, "source": [ "## [Problem 98](https://projecteuler.net/problem=98)\n", "\n", "*Match anagram word pairs against square numbers via digit-to-letter mappings.*" ] }, { "cell_type": "code", "execution_count": 101, "id": "cell-201", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 98: Anagramic Squares 49 msec ⇒ 18769 ✅ " ] }, "execution_count": 101, "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", " anagram_sets = [g for g in groups.values() if len(g) >= 2]\n", " maxlen = max(len(g[0]) for g in anagram_sets)\n", " sq_by_len = defaultdict(list)\n", " n = 1\n", " while len(str(n * n)) <= maxlen:\n", " sq_by_len[len(str(n * n))].append(n * n)\n", " n += 1\n", " best = 0\n", " for group in anagram_sets:\n", " L = len(group[0])\n", " for w1, w2 in permutations(group, 2):\n", " for sq in sq_by_len[L]:\n", " s = str(sq)\n", " m = {}\n", " ok = True\n", " for ch, dg in zip(w1, s):\n", " if ch in m:\n", " if m[ch] != dg:\n", " ok = False\n", " break\n", " else:\n", " m[ch] = dg\n", " if not ok or len(set(m.values())) != len(m):\n", " continue\n", " t = \"\".join(m[ch] for ch in w2)\n", " if t[0] == \"0\":\n", " continue\n", " ti = int(t)\n", " r = isqrt(ti)\n", " if r * r == ti:\n", " best = max(best, sq, ti)\n", " return best\n", "\n", "\n", "run(euler_98)" ] }, { "cell_type": "markdown", "id": "cell-202", "metadata": {}, "source": [ "## [Problem 99](https://projecteuler.net/problem=99)\n", "\n", "*Compare e·log(b) across the base/exponent pairs to find the largest value.*" ] }, { "cell_type": "code", "execution_count": 102, "id": "cell-203", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " 99: Largest Exponential 0 msec ⇒ 709 ✅ " ] }, "execution_count": 102, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_99():\n", " \"\"\"Largest Exponential\"\"\"\n", " import math\n", " best, best_line = 0.0, 0\n", " for i, line in enumerate(DATA[99].split(), 1):\n", " b, e = map(int, line.split(\",\"))\n", " val = e * math.log(b)\n", " if val > best:\n", " best, best_line = val, i\n", " return best_line\n", "\n", "\n", "run(euler_99)" ] }, { "cell_type": "markdown", "id": "cell-204", "metadata": {}, "source": [ "## [Problem 100](https://projecteuler.net/problem=100)\n", "\n", "*Pell-like recurrence generating the blue-disc arrangements past 10¹² discs.*" ] }, { "cell_type": "code", "execution_count": 103, "id": "cell-205", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "100: Arranged Probability 0 msec ⇒ 756872327473 ✅ " ] }, "execution_count": 103, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def euler_100():\n", " \"\"\"Arranged Probability\"\"\"\n", " LIMIT = 10 ** 12\n", " b, t = 15, 21\n", " while t <= LIMIT:\n", " b, t = 3 * b + 2 * t - 2, 4 * b + 3 * t - 3\n", " return b\n", "\n", "\n", "run(euler_100)" ] }, { "cell_type": "markdown", "id": "eec07911-f132-42a5-b23d-d3198c684db4", "metadata": {}, "source": [ "# Summary of Runs" ] }, { "cell_type": "code", "execution_count": 104, "id": "db1230a4-3134-426d-8768-d056167ba357", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Problems: 100\n", "Run time in seconds: total: 22.7, max: 4.6, mean: 0.227, median: 0.005\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 25 msec ⇒ 906609 ✅ \n", " 5: Smallest Multiple 0 msec ⇒ 232792560 ✅ \n", " 6: Sum Square Difference 0 msec ⇒ 25164150 ✅ \n", " 7: 10001st Prime 6 msec ⇒ 104743 ✅ \n", " 8: Largest Product in a Series 0 msec ⇒ 23514624000 ✅ \n", " 9: Special Pythagorean Triplet 7 msec ⇒ 31875000 ✅ \n", " 10: Summation of Primes 37 msec ⇒ 142913828922 ✅ \n", " 11: Largest Product in a Grid 0 msec ⇒ 70600674 ✅ \n", " 12: Highly Divisible Triangular Number 83 msec ⇒ 76576500 ✅ \n", " 13: Large Sum 0 msec ⇒ 5537376230 ✅ \n", " 14: Longest Collatz Sequence 625 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 3 msec ⇒ 31626 ✅ \n", " 22: Names Scores 2 msec ⇒ 871198282 ✅ \n", " 23: Non-Abundant Sums 384 msec ⇒ 4179871 ✅ \n", " 24: Lexicographic Permutations 6 msec ⇒ 2783915460 ✅ \n", " 25: 1000-digit Fibonacci Number 15 msec ⇒ 4782 ✅ \n", " 26: Reciprocal Cycles 7 msec ⇒ 983 ✅ \n", " 27: Quadratic Primes 1,300 msec ⇒ -59231 ✅ 🐌\n", " 28: Number Spiral Diagonals 0 msec ⇒ 669171001 ✅ \n", " 29: Distinct Powers 2 msec ⇒ 9183 ✅ \n", " 30: Digit Fifth Powers 135 msec ⇒ 443839 ✅ \n", " 31: Coin Sums 0 msec ⇒ 73682 ✅ \n", " 32: Pandigital Products 15 msec ⇒ 45228 ✅ \n", " 33: Digit Cancelling Fractions 1 msec ⇒ 100 ✅ \n", " 34: Digit Factorials 1,040 msec ⇒ 40730 ✅ 🐌\n", " 35: Circular Primes 42 msec ⇒ 55 ✅ \n", " 36: Double-base Palindromes 280 msec ⇒ 872187 ✅ \n", " 37: Truncatable Primes 968 msec ⇒ 748317 ✅ \n", " 38: Pandigital Multiples 3 msec ⇒ 932718654 ✅ \n", " 39: Integer Right Triangles 7 msec ⇒ 840 ✅ \n", " 40: Champernowne's Constant 53 msec ⇒ 210 ✅ \n", " 41: Pandigital Prime 0 msec ⇒ 7652413 ✅ \n", " 42: Coded Triangle Numbers 1 msec ⇒ 162 ✅ \n", " 43: Sub-string Divisibility 1,098 msec ⇒ 16695334890 ✅ 🐌\n", " 44: Pentagon Numbers 166 msec ⇒ 5482660 ✅ \n", " 45: Triangular, Pentagonal, and Hexagonal 4 msec ⇒ 1533776805 ✅ \n", " 46: Goldbach's Other Conjecture 13 msec ⇒ 5777 ✅ \n", " 47: Distinct Primes Factors 253 msec ⇒ 134043 ✅ \n", " 48: Self Powers 1 msec ⇒ 9110846700 ✅ \n", " 49: Prime Permutations 753 msec ⇒ 296962999629 ✅ \n", " 50: Consecutive Prime Sum 35 msec ⇒ 997651 ✅ \n", " 51: Prime Digit Replacements 1,167 msec ⇒ 121313 ✅ 🐌\n", " 52: Permuted Multiples 69 msec ⇒ 142857 ✅ \n", " 53: Combinatoric Selections 0 msec ⇒ 4075 ✅ \n", " 54: Poker Hands 4 msec ⇒ 376 ✅ \n", " 55: Lychrel Numbers 22 msec ⇒ 249 ✅ \n", " 56: Powerful Digit Sum 48 msec ⇒ 972 ✅ \n", " 57: Square Root Convergents 1 msec ⇒ 153 ✅ \n", " 58: Spiral Primes 74 msec ⇒ 26241 ✅ \n", " 59: XOR Decryption 0 msec ⇒ 107359 ✅ \n", " 60: Prime Pair Sets 1,548 msec ⇒ 26033 ✅ 🐌\n", " 61: Cyclical Figurate Numbers 1 msec ⇒ 28684 ✅ \n", " 62: Cubic Permutations 4 msec ⇒ 127035954683 ✅ \n", " 63: Powerful Digit Counts 0 msec ⇒ 49 ✅ \n", " 64: Odd Period Square Roots 20 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 5 msec ⇒ 6531031914842725 ✅ \n", " 69: Totient Maximum 0 msec ⇒ 510510 ✅ \n", " 70: Totient Permutation 12 msec ⇒ 8319823 ✅ \n", " 71: Ordered Fractions 62 msec ⇒ 428570 ✅ \n", " 72: Counting Fractions 382 msec ⇒ 303963552391 ✅ \n", " 73: Counting Fractions in a Range 730 msec ⇒ 7295372 ✅ \n", " 74: Digit Factorial Chains 630 msec ⇒ 402 ✅ \n", " 75: Singular Integer Right Triangles 100 msec ⇒ 161667 ✅ \n", " 76: Counting Summations 0 msec ⇒ 190569291 ✅ \n", " 77: Prime Summations 1 msec ⇒ 71 ✅ \n", " 78: Coin Partitions 1,209 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 4 msec ⇒ 425185 ✅ \n", " 84: Monopoly Odds 2 msec ⇒ 101524 ✅ \n", " 85: Counting Rectangles 1 msec ⇒ 2772 ✅ \n", " 86: Cuboid Route 190 msec ⇒ 1818 ✅ \n", " 87: Prime Power Triples 159 msec ⇒ 1097343 ✅ \n", " 88: Product-sum Numbers 58 msec ⇒ 7587457 ✅ \n", " 89: Roman Numerals 1 msec ⇒ 743 ✅ \n", " 90: Cube Digit Pairs 12 msec ⇒ 1217 ✅ \n", " 91: Right Triangles with Integer Coordinates 1,273 msec ⇒ 14234 ✅ 🐌\n", " 92: Square Digit Chains 4,565 msec ⇒ 8581146 ✅ 🐌\n", " 93: Arithmetic Expressions 1,035 msec ⇒ 1258 ✅ 🐌\n", " 94: Almost Equilateral Triangles 0 msec ⇒ 518408346 ✅ \n", " 95: Amicable Chains 1,813 msec ⇒ 14316 ✅ 🐌\n", " 96: Su Doku 57 msec ⇒ 24702 ✅ \n", " 97: Large Non-Mersenne Prime 0 msec ⇒ 8739992577 ✅ \n", " 98: Anagramic Squares 49 msec ⇒ 18769 ✅ \n", " 99: Largest Exponential 0 msec ⇒ 709 ✅ \n", "100: Arranged Probability 0 msec ⇒ 756872327473 ✅ \n" ] } ], "source": [ "runs()" ] }, { "cell_type": "code", "execution_count": null, "id": "34b04f7b-9249-4518-84dc-ad32247d7acd", "metadata": {}, "outputs": [], "source": [] } ], "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 }