{
"cells": [
{
"cell_type": "markdown",
"id": "3363e134",
"metadata": {},
"source": [
"notebook by Kimi K3
July 2026
\n",
"\n",
"# Project Euler\n",
"\n",
"[Project Euler](https://projecteuler.net) is a collection of math/programming [problems](https://projecteuler.net/archives). Here are solutions for all of the first 100 problems, written in the notebook format used by Peter Norvig in his [Euler.ipynb](https://github.com/norvig/pytudes/blob/main/ipynb/Euler.ipynb): one markdown cell and one code cell per problem, with every answer checked against the expected value and timed.\n",
"\n",
"The `DATA` dict (input data for the problems that need it) and the `EXPECTED` dict (the known answers) and the `run` command are taken from Norvig's [`euler_data.py`]\n",
"\n",
"Project Euler suggests that solutions should run in a minute or less; almost all of these run in well under a second."
]
},
{
"cell_type": "markdown",
"id": "234e10d9",
"metadata": {},
"source": [
"## Imports\n",
"\n",
"I import the following modules (standard library only)."
]
},
{
"cell_type": "code",
"execution_count": 1,
"id": "13af6ab8",
"metadata": {},
"outputs": [],
"source": [
"from euler_data import DATA, run, runs\n",
"\n",
"from ast import literal_eval\n",
"from collections import Counter, defaultdict, deque\n",
"from fractions import Fraction\n",
"from functools import cache, reduce\n",
"from itertools import (permutations, combinations, combinations_with_replacement, count,\n",
" islice, takewhile, dropwhile, product, groupby, accumulate, pairwise,\n",
" chain, repeat, cycle, zip_longest, starmap, filterfalse)\n",
"from math import gcd, lcm, factorial, comb, sqrt, isqrt, prod, log, log10, exp, ceil, floor, inf, pi\n",
"from statistics import mean, median\n",
"\n",
"import decimal\n",
"import heapq\n",
"import random\n",
"import re\n",
"import time"
]
},
{
"cell_type": "markdown",
"id": "b7044fab",
"metadata": {},
"source": [
"## Utilities\n",
"\n",
"The following utilities are used in multiple problems."
]
},
{
"cell_type": "code",
"execution_count": 2,
"id": "9e691dc6",
"metadata": {},
"outputs": [],
"source": [
"#### Constant\n",
"\n",
"million = 1_000_000\n",
"\n",
"#### Functions on iterables\n",
"\n",
"def quantify(iterable, predicate=bool) -> int:\n",
" \"\"\"Count how many items in the iterable are true-ish, by themselves, or according to predicate.\"\"\"\n",
" return sum(map(predicate, iterable))\n",
"\n",
"def first(iterable, default=False) -> object:\n",
" \"\"\"Return the first element of the iterable, or the default if it is empty.\"\"\"\n",
" return next(iter(iterable), default)\n",
"\n",
"def first_true(iterable, default=False, predicate=None):\n",
" \"\"\"Returns the first true value (according to predicate) or the default if there is no true value.\"\"\"\n",
" return next(filter(predicate, iterable), default)\n",
"\n",
"def integers(start, end=10**18, step=1) -> range:\n",
" \"\"\"The integers from start to end, inclusive, with a very big default for end.\n",
" Equal to range(start, end + 1, step).\"\"\"\n",
" return range(start, end + 1, step)"
]
},
{
"cell_type": "markdown",
"id": "0fec0d87",
"metadata": {},
"source": [
"# Project Euler Problems 1–10"
]
},
{
"cell_type": "markdown",
"id": "598d3cfe",
"metadata": {},
"source": [
"## [Problem 1](https://projecteuler.net/problem=1)"
]
},
{
"cell_type": "code",
"execution_count": 3,
"id": "4fb884e4",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
" 1: Multiples of 3 or 5 0 msec ⇒ 233168 ✅ "
]
},
"execution_count": 3,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def euler_1(limit=1000):\n",
" \"\"\"Multiples of 3 or 5: Sum all the natural numbers below 1000 that are multiples of 3 or 5.\"\"\"\n",
" return sum(n for n in range(limit) if n % 3 == 0 or n % 5 == 0)\n",
"run(euler_1)\n"
]
},
{
"cell_type": "markdown",
"id": "5fc61e84",
"metadata": {},
"source": [
"## [Problem 2](https://projecteuler.net/problem=2)"
]
},
{
"cell_type": "code",
"execution_count": 4,
"id": "b75d412c",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
" 2: Even Fibonacci Numbers 0 msec ⇒ 4613732 ✅ "
]
},
"execution_count": 4,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def euler_2(limit=4_000_000):\n",
" \"\"\"Even Fibonacci Numbers: Sum the even-valued Fibonacci terms whose values do not exceed four million.\"\"\"\n",
" total, a, b = 0, 1, 2\n",
" while b <= limit:\n",
" if b % 2 == 0:\n",
" total += b\n",
" a, b = b, a + b\n",
" return total\n",
"run(euler_2)\n"
]
},
{
"cell_type": "markdown",
"id": "ae580c0d",
"metadata": {},
"source": [
"## [Problem 3](https://projecteuler.net/problem=3)"
]
},
{
"cell_type": "code",
"execution_count": 5,
"id": "b2c3a919",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
" 3: Largest Prime Factor 0 msec ⇒ 6857 ✅ "
]
},
"execution_count": 5,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def euler_3(n=600851475143):\n",
" \"\"\"Largest Prime Factor: Find the largest prime factor of 600851475143.\"\"\"\n",
" factor = 2\n",
" while factor * factor <= n:\n",
" if n % factor == 0:\n",
" n //= factor\n",
" else:\n",
" factor += 1 if factor == 2 else 2 # test 2, then odd candidates\n",
" return n\n",
"run(euler_3)\n"
]
},
{
"cell_type": "markdown",
"id": "bf0ff075",
"metadata": {},
"source": [
"## [Problem 4](https://projecteuler.net/problem=4)"
]
},
{
"cell_type": "code",
"execution_count": 6,
"id": "7c5a7500",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
" 4: Largest Palindrome Product 33 msec ⇒ 906609 ✅ "
]
},
"execution_count": 6,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def euler_4(digits=3):\n",
" \"\"\"Largest Palindrome Product: Find the largest palindrome made from the product of two 3-digit numbers.\"\"\"\n",
" lo, hi = 10 ** (digits - 1), 10 ** digits\n",
" def is_palindrome(n):\n",
" s = str(n)\n",
" return s == s[::-1]\n",
" return max(a * b for a in range(lo, hi) for b in range(a, hi) if is_palindrome(a * b))\n",
"run(euler_4)\n"
]
},
{
"cell_type": "markdown",
"id": "37f08738",
"metadata": {},
"source": [
"## [Problem 5](https://projecteuler.net/problem=5)"
]
},
{
"cell_type": "code",
"execution_count": 7,
"id": "147c71c1",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
" 5: Smallest Multiple 0 msec ⇒ 232792560 ✅ "
]
},
"execution_count": 7,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def euler_5(n=20):\n",
" \"\"\"Smallest Multiple: Find the smallest positive number evenly divisible by all of the numbers from 1 to 20.\"\"\"\n",
" return reduce(lcm, range(1, n + 1))\n",
"run(euler_5)\n"
]
},
{
"cell_type": "markdown",
"id": "b1bb349e",
"metadata": {},
"source": [
"## [Problem 6](https://projecteuler.net/problem=6)"
]
},
{
"cell_type": "code",
"execution_count": 8,
"id": "441b1577",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
" 6: Sum Square Difference 0 msec ⇒ 25164150 ✅ "
]
},
"execution_count": 8,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def euler_6(n=100):\n",
" \"\"\"Sum Square Difference: Find the difference between the square of the sum and the sum of the squares of the first 100 natural numbers.\"\"\"\n",
" return sum(range(n + 1)) ** 2 - sum(k * k for k in range(n + 1))\n",
"run(euler_6)\n"
]
},
{
"cell_type": "markdown",
"id": "18882657",
"metadata": {},
"source": [
"## [Problem 7](https://projecteuler.net/problem=7)"
]
},
{
"cell_type": "code",
"execution_count": 9,
"id": "c353be7f",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
" 7: 10001st Prime 2 msec ⇒ 104743 ✅ "
]
},
"execution_count": 9,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def euler_7(which=10001):\n",
" \"\"\"10001st Prime: Find the 10001st prime number.\"\"\"\n",
" # Rosser's theorem: the nth prime is below n * (ln n + ln ln n), a safe sieve bound.\n",
" bound = int(which * (log(which) + log(log(which)))) + 10\n",
" sieve = bytearray(b'\\x01') * (bound + 1)\n",
" sieve[0:2] = b'\\x00\\x00'\n",
" for p in range(2, isqrt(bound) + 1):\n",
" if sieve[p]:\n",
" sieve[p * p::p] = bytes(len(sieve[p * p::p]))\n",
" return [p for p, prime in enumerate(sieve) if prime][which - 1]\n",
"run(euler_7)\n"
]
},
{
"cell_type": "markdown",
"id": "d5fe39ad",
"metadata": {},
"source": [
"## [Problem 8](https://projecteuler.net/problem=8)"
]
},
{
"cell_type": "code",
"execution_count": 10,
"id": "e7644c9b",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
" 8: Largest Product in a Series 0 msec ⇒ 23514624000 ✅ "
]
},
"execution_count": 10,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def euler_8(data=DATA[8]):\n",
" \"\"\"Largest Product in a Series: Find the greatest product of thirteen adjacent digits in the 1000-digit number.\"\"\"\n",
" digits = [int(d) for d in data if d.isdigit()]\n",
" window = 13\n",
" return max(prod(digits[i:i + window]) for i in range(len(digits) - window + 1))\n",
"run(euler_8)\n"
]
},
{
"cell_type": "markdown",
"id": "ba7572aa",
"metadata": {},
"source": [
"## [Problem 9](https://projecteuler.net/problem=9)"
]
},
{
"cell_type": "code",
"execution_count": 11,
"id": "046483c0",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
" 9: Special Pythagorean Triplet 0 msec ⇒ 31875000 ✅ "
]
},
"execution_count": 11,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def euler_9(total=1000):\n",
" \"\"\"Special Pythagorean Triplet: Find the product abc of the Pythagorean triplet for which a + b + c = 1000.\"\"\"\n",
" for a in range(1, total // 3):\n",
" # From a^2 + b^2 = (total - a - b)^2, solve for b given a.\n",
" b, remainder = divmod(total * total - 2 * total * a, 2 * (total - a))\n",
" if remainder == 0 and a < b:\n",
" return a * b * (total - a - b)\n",
"run(euler_9)\n"
]
},
{
"cell_type": "markdown",
"id": "62df4bbf",
"metadata": {},
"source": [
"## [Problem 10](https://projecteuler.net/problem=10)"
]
},
{
"cell_type": "code",
"execution_count": 12,
"id": "dfb62f3a",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
" 10: Summation of Primes 31 msec ⇒ 142913828922 ✅ "
]
},
"execution_count": 12,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def euler_10(limit=2_000_000):\n",
" \"\"\"Summation of Primes: Find the sum of all the primes below two million.\"\"\"\n",
" sieve = bytearray(b'\\x01') * limit\n",
" sieve[0:2] = b'\\x00\\x00'\n",
" for p in range(2, isqrt(limit) + 1):\n",
" if sieve[p]:\n",
" sieve[p * p::p] = bytes(len(sieve[p * p::p]))\n",
" return sum(p for p, prime in enumerate(sieve) if prime)\n",
"run(euler_10)\n"
]
},
{
"cell_type": "markdown",
"id": "35d170b9",
"metadata": {},
"source": [
"# Project Euler Problems 11–20"
]
},
{
"cell_type": "markdown",
"id": "44eaa909",
"metadata": {},
"source": [
"## [Problem 11](https://projecteuler.net/problem=11)"
]
},
{
"cell_type": "code",
"execution_count": 13,
"id": "75c90452",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
" 11: Largest Product in a Grid 1 msec ⇒ 70600674 ✅ "
]
},
"execution_count": 13,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def euler_11(data=DATA[11]):\n",
" \"\"\"Largest Product in a Grid: Find the greatest product of four adjacent numbers in the same direction (up, down, left, right, or diagonally) in the grid.\"\"\"\n",
" grid = [[int(cell) for cell in line.split()] for line in data.strip().splitlines()]\n",
" rows, cols, span = len(grid), len(grid[0]), 4\n",
" best = 0\n",
" for r in range(rows):\n",
" for c in range(cols):\n",
" for dr, dc in ((0, 1), (1, 0), (1, 1), (1, -1)):\n",
" cells = [(r + i * dr, c + i * dc) for i in range(span)]\n",
" if all(0 <= rr < rows and 0 <= cc < cols for rr, cc in cells):\n",
" best = max(best, prod(grid[rr][cc] for rr, cc in cells))\n",
" return best\n",
"run(euler_11)\n"
]
},
{
"cell_type": "markdown",
"id": "bc076431",
"metadata": {},
"source": [
"## [Problem 12](https://projecteuler.net/problem=12)"
]
},
{
"cell_type": "code",
"execution_count": 14,
"id": "9eae8164",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
" 12: Highly Divisible Triangular Number 30 msec ⇒ 76576500 ✅ "
]
},
"execution_count": 14,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def euler_12(target=500):\n",
" \"\"\"Highly Divisible Triangular Number: Find the value of the first triangle number to have over 500 divisors.\"\"\"\n",
" # Primes up to 10000 suffice: every triangle number tested is below 10^8.\n",
" bound = 10_000\n",
" sieve = bytearray(b'\\x01') * (bound + 1)\n",
" sieve[0:2] = b'\\x00\\x00'\n",
" for p in range(2, isqrt(bound) + 1):\n",
" if sieve[p]:\n",
" sieve[p * p::p] = bytes(len(sieve[p * p::p]))\n",
" primes = [p for p, prime in enumerate(sieve) if prime]\n",
"\n",
" def divisor_count(n):\n",
" count = 1\n",
" for p in primes:\n",
" if p * p > n:\n",
" break\n",
" if n % p == 0:\n",
" exponent = 1\n",
" while n % p == 0:\n",
" n //= p\n",
" exponent += 1\n",
" count *= exponent\n",
" return count * (2 if n > 1 else 1) # leftover n is prime\n",
"\n",
" triangle = 0\n",
" for i in count(1):\n",
" triangle += i\n",
" if divisor_count(triangle) > target:\n",
" return triangle\n",
"run(euler_12)\n"
]
},
{
"cell_type": "markdown",
"id": "e076ffac",
"metadata": {},
"source": [
"## [Problem 13](https://projecteuler.net/problem=13)"
]
},
{
"cell_type": "code",
"execution_count": 15,
"id": "367ef9d3",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
" 13: Large Sum 0 msec ⇒ 5537376230 ✅ "
]
},
"execution_count": 15,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def euler_13(data=DATA[13]):\n",
" \"\"\"Large Sum: Find the first ten digits of the sum of one hundred 50-digit numbers.\"\"\"\n",
" return int(str(sum(int(line) for line in data.split()))[:10])\n",
"run(euler_13)\n"
]
},
{
"cell_type": "markdown",
"id": "46562933",
"metadata": {},
"source": [
"## [Problem 14](https://projecteuler.net/problem=14)"
]
},
{
"cell_type": "code",
"execution_count": 16,
"id": "3e490f7b",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
" 14: Longest Collatz Sequence 255 msec ⇒ 837799 ✅ "
]
},
"execution_count": 16,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def euler_14(limit=1_000_000):\n",
" \"\"\"Longest Collatz Sequence: Find the starting number under one million that produces the longest Collatz chain.\"\"\"\n",
" lengths = [0] * limit # chain length cache, for values below limit only\n",
" lengths[1] = 1\n",
" best_number, best_length = 1, 1\n",
" # Any start n <= limit/2 is dominated by 2n (one step longer), so search the top half.\n",
" for start in range(limit // 2, limit):\n",
" n, path = start, []\n",
" while n >= limit or lengths[n] == 0:\n",
" path.append(n)\n",
" n = n // 2 if n % 2 == 0 else 3 * n + 1\n",
" length = lengths[n]\n",
" for m in reversed(path):\n",
" length += 1\n",
" if m < limit:\n",
" lengths[m] = length\n",
" if length > best_length:\n",
" best_number, best_length = start, length\n",
" return best_number\n",
"run(euler_14)\n"
]
},
{
"cell_type": "markdown",
"id": "56b4515c",
"metadata": {},
"source": [
"## [Problem 15](https://projecteuler.net/problem=15)"
]
},
{
"cell_type": "code",
"execution_count": 17,
"id": "83ec6a1e",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
" 15: Lattice Paths 0 msec ⇒ 137846528820 ✅ "
]
},
"execution_count": 17,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def euler_15(n=20):\n",
" \"\"\"Lattice Paths: Count the routes, moving only right and down, through a 20 by 20 grid.\"\"\"\n",
" return comb(2 * n, n)\n",
"run(euler_15)\n"
]
},
{
"cell_type": "markdown",
"id": "c189038b",
"metadata": {},
"source": [
"## [Problem 16](https://projecteuler.net/problem=16)"
]
},
{
"cell_type": "code",
"execution_count": 18,
"id": "a771f984",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
" 16: Power Digit Sum 0 msec ⇒ 1366 ✅ "
]
},
"execution_count": 18,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def euler_16(power=1000):\n",
" \"\"\"Power Digit Sum: Find the sum of the digits of 2^1000.\"\"\"\n",
" return sum(int(d) for d in str(2 ** power))\n",
"run(euler_16)\n"
]
},
{
"cell_type": "markdown",
"id": "8cf131a8",
"metadata": {},
"source": [
"## [Problem 17](https://projecteuler.net/problem=17)"
]
},
{
"cell_type": "code",
"execution_count": 19,
"id": "df4d5778",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
" 17: Number Letter Counts 0 msec ⇒ 21124 ✅ "
]
},
"execution_count": 19,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def euler_17(limit=1000):\n",
" \"\"\"Number Letter Counts: Count the letters used when writing out the numbers from 1 to 1000 in words, excluding spaces and hyphens.\"\"\"\n",
" ones = ['', 'one', 'two', 'three', 'four', 'five', 'six', 'seven', 'eight', 'nine',\n",
" 'ten', 'eleven', 'twelve', 'thirteen', 'fourteen', 'fifteen', 'sixteen',\n",
" 'seventeen', 'eighteen', 'nineteen']\n",
" tens = ['', '', 'twenty', 'thirty', 'forty', 'fifty', 'sixty', 'seventy', 'eighty', 'ninety']\n",
"\n",
" def in_words(n):\n",
" if n < 20:\n",
" return ones[n]\n",
" if n < 100:\n",
" return tens[n // 10] + ones[n % 10]\n",
" if n < 1000:\n",
" tail = 'and' + in_words(n % 100) if n % 100 else ''\n",
" return ones[n // 100] + 'hundred' + tail\n",
" return 'onethousand'\n",
"\n",
" return sum(len(in_words(n)) for n in range(1, limit + 1))\n",
"run(euler_17)\n"
]
},
{
"cell_type": "markdown",
"id": "1d264075",
"metadata": {},
"source": [
"## [Problem 18](https://projecteuler.net/problem=18)"
]
},
{
"cell_type": "code",
"execution_count": 20,
"id": "b82b6e65",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
" 18: Maximum Path Sum I 0 msec ⇒ 1074 ✅ "
]
},
"execution_count": 20,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def euler_18(data=DATA[18]):\n",
" \"\"\"Maximum Path Sum I: Find the maximum total from top to bottom of the triangle, moving to adjacent numbers on the row below.\"\"\"\n",
" triangle = [[int(cell) for cell in line.split()] for line in data.strip().splitlines()]\n",
" best = triangle[-1] # fold rows upward, tracking the best subtotal at each position\n",
" for row in reversed(triangle[:-1]):\n",
" best = [row[i] + max(best[i], best[i + 1]) for i in range(len(row))]\n",
" return best[0]\n",
"run(euler_18)\n"
]
},
{
"cell_type": "markdown",
"id": "6676fe0e",
"metadata": {},
"source": [
"## [Problem 19](https://projecteuler.net/problem=19)"
]
},
{
"cell_type": "code",
"execution_count": 21,
"id": "72379354",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
" 19: Counting Sundays 0 msec ⇒ 171 ✅ "
]
},
"execution_count": 21,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def euler_19():\n",
" \"\"\"Counting Sundays: Count the months of the twentieth century (1 Jan 1901 to 31 Dec 2000) that began on a Sunday.\"\"\"\n",
" month_days = [31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]\n",
" def is_leap(year):\n",
" return year % 4 == 0 and (year % 100 != 0 or year % 400 == 0)\n",
" weekday = 1 # 0 = Sunday; 1 Jan 1900 was a Monday\n",
" sunday_months = 0\n",
" for year in range(1900, 2001):\n",
" for month in range(12):\n",
" if weekday == 0 and year >= 1901:\n",
" sunday_months += 1\n",
" weekday = (weekday + month_days[month] + (month == 1 and is_leap(year))) % 7\n",
" return sunday_months\n",
"run(euler_19)\n"
]
},
{
"cell_type": "markdown",
"id": "ae31689a",
"metadata": {},
"source": [
"## [Problem 20](https://projecteuler.net/problem=20)"
]
},
{
"cell_type": "code",
"execution_count": 22,
"id": "997f2c25",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
" 20: Factorial Digit Sum 0 msec ⇒ 648 ✅ "
]
},
"execution_count": 22,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def euler_20(n=100):\n",
" \"\"\"Factorial Digit Sum: Find the sum of the digits in the number 100!.\"\"\"\n",
" return sum(int(d) for d in str(factorial(n)))\n",
"run(euler_20)\n"
]
},
{
"cell_type": "markdown",
"id": "b49c3bf9",
"metadata": {},
"source": [
"# Project Euler Problems 21–30"
]
},
{
"cell_type": "markdown",
"id": "c989c902",
"metadata": {},
"source": [
"## [Problem 21](https://projecteuler.net/problem=21)"
]
},
{
"cell_type": "code",
"execution_count": 23,
"id": "cf6f667b",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
" 21: Amicable Numbers 3 msec ⇒ 31626 ✅ "
]
},
"execution_count": 23,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def euler_21(limit=10_000):\n",
" \"\"\"Amicable Numbers: Sum all the amicable numbers under 10000, where d(n) denotes the\n",
" sum of proper divisors of n and an amicable pair (a, b) satisfies d(a) = b, d(b) = a, a != b.\"\"\"\n",
" d = [1] * limit # d[n] accumulates the proper divisors of n; 1 divides every n >= 2\n",
" for i in range(2, limit // 2 + 1):\n",
" for j in range(2 * i, limit, i):\n",
" d[j] += i\n",
" return sum(a for a in range(2, limit)\n",
" if d[a] != a and d[a] < limit and d[d[a]] == a)\n",
"run(euler_21)\n"
]
},
{
"cell_type": "markdown",
"id": "c2a46e5e",
"metadata": {},
"source": [
"## [Problem 22](https://projecteuler.net/problem=22)"
]
},
{
"cell_type": "code",
"execution_count": 24,
"id": "201f6479",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
" 22: Names Scores 8 msec ⇒ 871198282 ✅ "
]
},
"execution_count": 24,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def euler_22(data=DATA[22]):\n",
" \"\"\"Names Scores: Sort the 5000+ names and total (alphabetical position times\n",
" alphabetical value) over all names, where the value sums letters as A=1 .. Z=26.\"\"\"\n",
" names = sorted(literal_eval('[' + data + ']'))\n",
" def value(name): return sum(ord(c) - ord('A') + 1 for c in name)\n",
" return sum(pos * value(name) for pos, name in enumerate(names, 1))\n",
"run(euler_22)\n"
]
},
{
"cell_type": "markdown",
"id": "441c3258",
"metadata": {},
"source": [
"## [Problem 23](https://projecteuler.net/problem=23)"
]
},
{
"cell_type": "code",
"execution_count": 25,
"id": "d32847d8",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
" 23: Non-Abundant Sums 17 msec ⇒ 4179871 ✅ "
]
},
"execution_count": 25,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def euler_23(limit=28_123):\n",
" \"\"\"Non-Abundant Sums: Find the sum of all positive integers that cannot be written as\n",
" the sum of two abundant numbers (every integer above 28123 can be so written).\"\"\"\n",
" divsum = [1] * (limit + 1)\n",
" for i in range(2, limit // 2 + 1):\n",
" for j in range(2 * i, limit + 1, i):\n",
" divsum[j] += i\n",
" is_abundant = bytearray(limit + 1)\n",
" for n in range(12, limit + 1):\n",
" is_abundant[n] = divsum[n] > n\n",
" evens = [n for n in range(12, limit + 1) if is_abundant[n] and n % 2 == 0]\n",
" odds = [n for n in range(12, limit + 1) if is_abundant[n] and n % 2 == 1]\n",
" expressible = bytearray(limit + 1)\n",
" # Even sums: for even n >= 48, one of n-12, n-20, n-40 is a multiple of 6 >= 12,\n",
" # hence abundant; only the few smaller evens need a direct check.\n",
" for n in range(24, 48, 2):\n",
" expressible[n] = any(is_abundant[n - a] for a in evens if a < n)\n",
" for n in range(48, limit + 1, 2):\n",
" expressible[n] = 1\n",
" # Odd sums: an odd abundant plus an even abundant.\n",
" for o in odds:\n",
" for e in evens:\n",
" if o + e > limit:\n",
" break\n",
" expressible[o + e] = 1\n",
" return sum(n for n in range(1, limit + 1) if not expressible[n])\n",
"run(euler_23)\n"
]
},
{
"cell_type": "markdown",
"id": "b42ca901",
"metadata": {},
"source": [
"## [Problem 24](https://projecteuler.net/problem=24)"
]
},
{
"cell_type": "code",
"execution_count": 26,
"id": "dd8a31fc",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
" 24: Lexicographic Permutations 0 msec ⇒ 2783915460 ✅ "
]
},
"execution_count": 26,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def euler_24(index=999_999, symbols='0123456789'):\n",
" \"\"\"Lexicographic Permutations: The millionth lexicographic permutation of the digits\n",
" 0 through 9, read as an integer (found via the factorial number system).\"\"\"\n",
" digits = sorted(symbols)\n",
" chosen = []\n",
" for remaining in range(len(digits), 0, -1):\n",
" block = factorial(remaining - 1) # permutations sharing each choice of next digit\n",
" q, index = divmod(index, block)\n",
" chosen.append(digits.pop(q))\n",
" return int(''.join(chosen))\n",
"run(euler_24)\n"
]
},
{
"cell_type": "markdown",
"id": "25f182d8",
"metadata": {},
"source": [
"## [Problem 25](https://projecteuler.net/problem=25)"
]
},
{
"cell_type": "code",
"execution_count": 27,
"id": "b5b0e09b",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
" 25: 1000-digit Fibonacci Number 0 msec ⇒ 4782 ✅ "
]
},
"execution_count": 27,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def euler_25(ndigits=1000):\n",
" \"\"\"1000-digit Fibonacci Number: The index of the first term of the Fibonacci sequence\n",
" (starting 1, 1, ...) to contain 1000 digits.\"\"\"\n",
" threshold = 10 ** (ndigits - 1)\n",
" a, b, index = 0, 1, 1\n",
" while b < threshold:\n",
" a, b, index = b, a + b, index + 1\n",
" return index\n",
"run(euler_25)\n"
]
},
{
"cell_type": "markdown",
"id": "82dc2ce8",
"metadata": {},
"source": [
"## [Problem 26](https://projecteuler.net/problem=26)"
]
},
{
"cell_type": "code",
"execution_count": 28,
"id": "83ad65ea",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
" 26: Reciprocal Cycles 7 msec ⇒ 983 ✅ "
]
},
"execution_count": 28,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def euler_26(limit=1000):\n",
" \"\"\"Reciprocal Cycles: The value d < 1000 for which the decimal expansion of 1/d\n",
" contains the longest recurring cycle.\"\"\"\n",
" def cycle_length(d):\n",
" seen = {} # remainder -> position where it first appeared\n",
" pos, remainder = 0, 1\n",
" while remainder and remainder not in seen:\n",
" seen[remainder] = pos\n",
" pos, remainder = pos + 1, (10 * remainder) % d\n",
" return 0 if remainder == 0 else pos - seen[remainder]\n",
" return max(range(2, limit), key=cycle_length)\n",
"run(euler_26)\n"
]
},
{
"cell_type": "markdown",
"id": "e48652d2",
"metadata": {},
"source": [
"## [Problem 27](https://projecteuler.net/problem=27)"
]
},
{
"cell_type": "code",
"execution_count": 29,
"id": "89fab555",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
" 27: Quadratic Primes 67 msec ⇒ -59231 ✅ "
]
},
"execution_count": 29,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def euler_27(bound=1000):\n",
" \"\"\"Quadratic Primes: The product a*b of the coefficients of the quadratic formula\n",
" n^2 + a*n + b (|a| < 1000, |b| <= 1000) that produces the most consecutive primes from n = 0.\"\"\"\n",
" size = 2 * bound * bound + bound + 1 # every reachable n^2 + a*n + b is below this\n",
" prime = bytearray([1]) * size\n",
" prime[0:2] = b'\\0\\0'\n",
" for p in range(2, isqrt(size) + 1):\n",
" if prime[p]:\n",
" prime[p*p::p] = bytes(len(prime[p*p::p]))\n",
" def streak(a, b):\n",
" n = 0\n",
" while 0 <= n*n + a*n + b < size and prime[n*n + a*n + b]:\n",
" n += 1\n",
" return n\n",
" best = (0, 0) # (longest streak, a*b)\n",
" for b in range(2, bound + 1):\n",
" if not prime[b]:\n",
" continue # n = 0 yields b itself, which must be prime\n",
" for a in range(-bound + 1, bound):\n",
" s = streak(a, b)\n",
" if s > best[0]:\n",
" best = (s, a * b)\n",
" return best[1]\n",
"run(euler_27)\n"
]
},
{
"cell_type": "markdown",
"id": "221f581b",
"metadata": {},
"source": [
"## [Problem 28](https://projecteuler.net/problem=28)"
]
},
{
"cell_type": "code",
"execution_count": 30,
"id": "6ca36e88",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
" 28: Number Spiral Diagonals 0 msec ⇒ 669171001 ✅ "
]
},
"execution_count": 30,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def euler_28(size=1001):\n",
" \"\"\"Number Spiral Diagonals: The sum of the numbers on both diagonals of a 1001 by 1001\n",
" clockwise spiral that starts with 1 in the centre.\"\"\"\n",
" # Ring k has side 2k+1; its corners are (2k+1)^2 minus 0, 2k, 4k, 6k.\n",
" return 1 + sum(4 * (2 * k + 1) ** 2 - 12 * k for k in range(1, size // 2 + 1))\n",
"run(euler_28)\n"
]
},
{
"cell_type": "markdown",
"id": "8e68d32b",
"metadata": {},
"source": [
"## [Problem 29](https://projecteuler.net/problem=29)"
]
},
{
"cell_type": "code",
"execution_count": 31,
"id": "71caced9",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
" 29: Distinct Powers 2 msec ⇒ 9183 ✅ "
]
},
"execution_count": 31,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def euler_29(lo=2, hi=100):\n",
" \"\"\"Distinct Powers: How many distinct terms are generated by a**b\n",
" for 2 <= a <= 100 and 2 <= b <= 100?\"\"\"\n",
" return len({a ** b for a in range(lo, hi + 1) for b in range(lo, hi + 1)})\n",
"run(euler_29)\n"
]
},
{
"cell_type": "markdown",
"id": "4bbf50d3",
"metadata": {},
"source": [
"## [Problem 30](https://projecteuler.net/problem=30)"
]
},
{
"cell_type": "code",
"execution_count": 32,
"id": "9e7cb0a7",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
" 30: Digit Fifth Powers 131 msec ⇒ 443839 ✅ "
]
},
"execution_count": 32,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def euler_30(power=5):\n",
" \"\"\"Digit Fifth Powers: The sum of all numbers that can be written as the sum of\n",
" fifth powers of their digits.\"\"\"\n",
" raised = [d ** power for d in range(10)]\n",
" limit = (power + 1) * raised[9] # beyond this the digit-power sum is always too small\n",
" return sum(n for n in range(2, limit + 1)\n",
" if n == sum(raised[int(d)] for d in str(n)))\n",
"run(euler_30)\n"
]
},
{
"cell_type": "markdown",
"id": "fd3e421e",
"metadata": {},
"source": [
"# Project Euler Problems 31–40"
]
},
{
"cell_type": "markdown",
"id": "e3c0f57d",
"metadata": {},
"source": [
"## [Problem 31](https://projecteuler.net/problem=31)"
]
},
{
"cell_type": "code",
"execution_count": 33,
"id": "d1378237",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
" 31: Coin Sums 0 msec ⇒ 73682 ✅ "
]
},
"execution_count": 33,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def euler_31(total=200, coins=(1, 2, 5, 10, 20, 50, 100, 200)):\n",
" \"\"\"Coin Sums: How many different ways can two pounds be made using any number\n",
" of the eight standard British coins?\"\"\"\n",
" ways = [1] + [0] * total # ways[t] = number of ways to make t pence so far\n",
" for coin in coins:\n",
" for t in range(coin, total + 1):\n",
" ways[t] += ways[t - coin]\n",
" return ways[total]\n",
"run(euler_31)\n"
]
},
{
"cell_type": "markdown",
"id": "e7221bb6",
"metadata": {},
"source": [
"## [Problem 32](https://projecteuler.net/problem=32)"
]
},
{
"cell_type": "code",
"execution_count": 34,
"id": "acf30fa4",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
" 32: Pandigital Products 15 msec ⇒ 45228 ✅ "
]
},
"execution_count": 34,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def euler_32():\n",
" \"\"\"Pandigital Products: The sum of all products whose multiplicand/multiplier/product\n",
" identity, written as one string, is 1 through 9 pandigital.\"\"\"\n",
" products = set()\n",
" for a in range(1, 100):\n",
" for b in range(a, 10_000):\n",
" digits = str(a) + str(b) + str(a * b)\n",
" if len(digits) > 9:\n",
" break # only grows longer as b increases\n",
" if len(digits) == 9 and set(digits) == set('123456789'):\n",
" products.add(a * b)\n",
" return sum(products)\n",
"run(euler_32)\n"
]
},
{
"cell_type": "markdown",
"id": "15a4fbfb",
"metadata": {},
"source": [
"## [Problem 33](https://projecteuler.net/problem=33)"
]
},
{
"cell_type": "code",
"execution_count": 35,
"id": "4d6bc34a",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
" 33: Digit Cancelling Fractions 2 msec ⇒ 100 ✅ "
]
},
"execution_count": 35,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def euler_33():\n",
" \"\"\"Digit Cancelling Fractions: The denominator, in lowest terms, of the product of the\n",
" four non-trivial two-digit fractions that stay equal after 'cancelling' a shared digit.\"\"\"\n",
" def curious(num, den):\n",
" a, b = divmod(num, 10) # num digits\n",
" c, d = divmod(den, 10) # den digits\n",
" if b == 0 and d == 0:\n",
" return False # trivial trailing-zero example\n",
" f = Fraction(num, den)\n",
" return ((a == c and d and Fraction(b, d) == f) or\n",
" (a == d and c and Fraction(b, c) == f) or\n",
" (b == c and d and Fraction(a, d) == f) or\n",
" (b == d and c and Fraction(a, c) == f))\n",
" result = Fraction(1)\n",
" for num in range(10, 100):\n",
" for den in range(num + 1, 100):\n",
" if curious(num, den):\n",
" result *= Fraction(num, den)\n",
" return result.denominator\n",
"run(euler_33)\n"
]
},
{
"cell_type": "markdown",
"id": "ee2369ce",
"metadata": {},
"source": [
"## [Problem 34](https://projecteuler.net/problem=34)"
]
},
{
"cell_type": "code",
"execution_count": 36,
"id": "0d18dea5",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
" 34: Digit Factorials 33 msec ⇒ 40730 ✅ "
]
},
"execution_count": 36,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def euler_34():\n",
" \"\"\"Digit Factorials: The sum of all numbers equal to the sum of the factorial of\n",
" their digits (excluding the trivial 1 and 2).\"\"\"\n",
" fact = [factorial(d) for d in range(10)]\n",
" total = 0\n",
" # A number is fixed by its digit multiset; 8 digits give at most 8*9! (7 digits),\n",
" # so only multisets of 2..7 digits can possibly work.\n",
" for length in range(2, 8):\n",
" for digits in combinations_with_replacement(range(10), length):\n",
" s = sum(fact[d] for d in digits)\n",
" if Counter(str(s)) == Counter(map(str, digits)):\n",
" total += s\n",
" return total\n",
"run(euler_34)\n"
]
},
{
"cell_type": "markdown",
"id": "33824862",
"metadata": {},
"source": [
"## [Problem 35](https://projecteuler.net/problem=35)"
]
},
{
"cell_type": "code",
"execution_count": 37,
"id": "00fdb7ba",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
" 35: Circular Primes 37 msec ⇒ 55 ✅ "
]
},
"execution_count": 37,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def euler_35(limit=million):\n",
" \"\"\"Circular Primes: How many primes below one million have the property that every\n",
" rotation of their decimal digits is also prime?\"\"\"\n",
" prime = bytearray([1]) * limit\n",
" prime[0:2] = b'\\0\\0'\n",
" for p in range(2, isqrt(limit) + 1):\n",
" if prime[p]:\n",
" prime[p*p::p] = bytes(len(prime[p*p::p]))\n",
" forbidden = set('024568') # a multi-digit circular prime can only use 1, 3, 7, 9\n",
" def is_circular(p):\n",
" s = str(p)\n",
" return all(prime[int(s[i:] + s[:i])] for i in range(len(s)))\n",
" return quantify((p for p in range(limit) if prime[p]),\n",
" lambda p: p < 10 or (not forbidden & set(str(p)) and is_circular(p)))\n",
"run(euler_35)\n"
]
},
{
"cell_type": "markdown",
"id": "572c5f6d",
"metadata": {},
"source": [
"## [Problem 36](https://projecteuler.net/problem=36)"
]
},
{
"cell_type": "code",
"execution_count": 38,
"id": "ca2c36d1",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
" 36: Double-base Palindromes 0 msec ⇒ 872187 ✅ "
]
},
"execution_count": 38,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def euler_36(limit=million):\n",
" \"\"\"Double-base Palindromes: The sum of all numbers below one million that are\n",
" palindromic in both base 10 and base 2.\"\"\"\n",
" def is_binary_palindrome(p):\n",
" b = bin(p)[2:]\n",
" return b == b[::-1]\n",
" total = 0\n",
" for half in range(1, 1000): # mirroring each half builds every palindrome under 10^6\n",
" s = str(half)\n",
" for p in (int(s + s[::-1]), int(s + s[-2::-1])):\n",
" if p < limit and is_binary_palindrome(p):\n",
" total += p\n",
" return total\n",
"run(euler_36)\n"
]
},
{
"cell_type": "markdown",
"id": "46b9884e",
"metadata": {},
"source": [
"## [Problem 37](https://projecteuler.net/problem=37)"
]
},
{
"cell_type": "code",
"execution_count": 39,
"id": "45f2d251",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
" 37: Truncatable Primes 1 msec ⇒ 748317 ✅ "
]
},
"execution_count": 39,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def euler_37(limit=million):\n",
" \"\"\"Truncatable Primes: The sum of the only eleven primes that remain prime when\n",
" digits are continually removed from left to right and from right to left.\"\"\"\n",
" prime = bytearray([1]) * limit\n",
" prime[0:2] = b'\\0\\0'\n",
" for p in range(2, isqrt(limit) + 1):\n",
" if prime[p]:\n",
" prime[p*p::p] = bytes(len(prime[p*p::p]))\n",
" # Grow primes that survive right truncation by appending a final digit.\n",
" level = [2, 3, 5, 7]\n",
" right_truncatable = []\n",
" while level:\n",
" level = [10 * p + d for p in level for d in (1, 3, 7, 9)\n",
" if 10 * p + d < limit and prime[10 * p + d]]\n",
" right_truncatable += level\n",
" def is_left_truncatable(p):\n",
" s = str(p)\n",
" return all(prime[int(s[i:])] for i in range(1, len(s)))\n",
" return sum(p for p in right_truncatable if is_left_truncatable(p))\n",
"run(euler_37)\n"
]
},
{
"cell_type": "markdown",
"id": "47f29316",
"metadata": {},
"source": [
"## [Problem 38](https://projecteuler.net/problem=38)"
]
},
{
"cell_type": "code",
"execution_count": 40,
"id": "4f7c53fb",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
" 38: Pandigital Multiples 4 msec ⇒ 932718654 ✅ "
]
},
"execution_count": 40,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def euler_38():\n",
" \"\"\"Pandigital Multiples: The largest 1-to-9 pandigital number that can be formed as the\n",
" concatenated product n*1, n*2, ... of some integer n with the integers 1, 2, ...\"\"\"\n",
" def concatenated_product(n):\n",
" s = ''\n",
" for k in count(1):\n",
" s += str(n * k)\n",
" if len(s) >= 9:\n",
" return s\n",
" best = 0\n",
" for n in range(1, 10_000): # more digits can never yield exactly nine\n",
" s = concatenated_product(n)\n",
" if len(s) == 9 and set(s) == set('123456789'):\n",
" best = max(best, int(s))\n",
" return best\n",
"run(euler_38)\n"
]
},
{
"cell_type": "markdown",
"id": "a4106112",
"metadata": {},
"source": [
"## [Problem 39](https://projecteuler.net/problem=39)"
]
},
{
"cell_type": "code",
"execution_count": 41,
"id": "85199ae1",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
" 39: Integer Right Triangles 5 msec ⇒ 840 ✅ "
]
},
"execution_count": 41,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def euler_39(limit=1000):\n",
" \"\"\"Integer Right Triangles: The perimeter p <= 1000 for which the number of\n",
" integer-sided right-angle triangles with a + b + c = p is maximised.\"\"\"\n",
" solutions = Counter()\n",
" for a in range(1, limit // 3):\n",
" for b in range(a, (limit - a) // 2 + 1):\n",
" c2 = a * a + b * b\n",
" c = isqrt(c2)\n",
" if c * c == c2 and a + b + c <= limit:\n",
" solutions[a + b + c] += 1\n",
" return solutions.most_common(1)[0][0]\n",
"run(euler_39)\n"
]
},
{
"cell_type": "markdown",
"id": "c45f2949",
"metadata": {},
"source": [
"## [Problem 40](https://projecteuler.net/problem=40)"
]
},
{
"cell_type": "code",
"execution_count": 42,
"id": "24ba3f4b",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
" 40: Champernowne's Constant 8 msec ⇒ 210 ✅ "
]
},
"execution_count": 42,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def euler_40(positions=(1, 10, 100, 1_000, 10_000, 100_000, million)):\n",
" \"\"\"Champernowne's Constant: The product of the digits at positions 1, 10, 100, ...,\n",
" 10^6 of the irrational 0.1234567891011121314... formed by concatenating the integers.\"\"\"\n",
" digits = ''.join(map(str, range(1, 200_000))) # 1,088,889 digits: enough for 10^6\n",
" return prod(int(digits[p - 1]) for p in positions)\n",
"run(euler_40)\n"
]
},
{
"cell_type": "markdown",
"id": "7a4e117d",
"metadata": {},
"source": [
"# Project Euler Problems 41–50"
]
},
{
"cell_type": "markdown",
"id": "c8d4ab03",
"metadata": {},
"source": [
"## [Problem 41](https://projecteuler.net/problem=41)"
]
},
{
"cell_type": "code",
"execution_count": 43,
"id": "ae6fe715",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
" 41: Pandigital Prime 0 msec ⇒ 7652413 ✅ "
]
},
"execution_count": 43,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def euler_41():\n",
" \"\"\"Pandigital Prime: What is the largest n-digit pandigital prime?\"\"\"\n",
" def is_prime(n):\n",
" # Deterministic Miller-Rabin for n < 2.15e12.\n",
" if n < 2:\n",
" return False\n",
" for p in (2, 3, 5, 7, 11):\n",
" if n % p == 0:\n",
" return n == p\n",
" d, s = n - 1, 0\n",
" while d % 2 == 0:\n",
" d, s = d // 2, s + 1\n",
" for a in (2, 3, 5, 7, 11):\n",
" x = pow(a, d, n)\n",
" if x == 1 or x == n - 1:\n",
" continue\n",
" for _ in range(s - 1):\n",
" x = x * x % n\n",
" if x == n - 1:\n",
" break\n",
" else:\n",
" return False\n",
" return True\n",
" # 8- and 9-digit pandigitals have digit sums 36 and 45, so all are divisible by 3;\n",
" # likewise 6-, 5-, 3- and 2-digit ones (sums 21, 15, 6, 3). Only 7 or 4 digits remain.\n",
" for digits in ('7654321', '4321'):\n",
" for perm in permutations(digits): # descending input -> descending numbers\n",
" n = int(''.join(perm))\n",
" if is_prime(n):\n",
" return n\n",
"run(euler_41)\n"
]
},
{
"cell_type": "markdown",
"id": "2fb879c6",
"metadata": {},
"source": [
"## [Problem 42](https://projecteuler.net/problem=42)"
]
},
{
"cell_type": "code",
"execution_count": 44,
"id": "09947416",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
" 42: Coded Triangle Numbers 1 msec ⇒ 162 ✅ "
]
},
"execution_count": 44,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def euler_42(data=DATA[42]):\n",
" \"\"\"Coded Triangle Numbers: How many of the words are triangle words, i.e. their\n",
" converted letter-sum is itself a triangle number?\"\"\"\n",
" def is_triangle(v):\n",
" r = isqrt(8 * v + 1) # v = t(t+1)/2 iff 8v+1 is a perfect square\n",
" return r * r == 8 * v + 1\n",
" def value(word):\n",
" return sum(ord(c) - 64 for c in word)\n",
" return quantify(re.findall(r'\"(\\w+)\"', data), lambda w: is_triangle(value(w)))\n",
"run(euler_42)\n"
]
},
{
"cell_type": "markdown",
"id": "435eabf9",
"metadata": {},
"source": [
"## [Problem 43](https://projecteuler.net/problem=43)"
]
},
{
"cell_type": "code",
"execution_count": 45,
"id": "bbbd72c3",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
" 43: Sub-string Divisibility 0 msec ⇒ 16695334890 ✅ "
]
},
"execution_count": 45,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def euler_43():\n",
" \"\"\"Sub-string Divisibility: Find the sum of all 0-9 pandigital numbers where each\n",
" 3-digit substring d2d3d4 ... d8d9d10 is divisible by 2, 3, 5, 7, 11, 13, 17 in turn.\"\"\"\n",
" # Build right-to-left: start with the substring divisible by 17, then keep\n",
" # prepending a fresh digit whose new 3-digit window meets the next divisor.\n",
" chains = [s for s in (f'{n:03d}' for n in range(0, 1000, 17)) if len(set(s)) == 3]\n",
" for div in (13, 11, 7, 5, 3, 2):\n",
" chains = [d + s for s in chains for d in '0123456789'\n",
" if d not in s and int(d + s[:2]) % div == 0]\n",
" # One digit is still missing at the front; it may not be zero.\n",
" return sum(int(d + s) for s in chains for d in '123456789' if d not in s)\n",
"run(euler_43)\n"
]
},
{
"cell_type": "markdown",
"id": "486cb58f",
"metadata": {},
"source": [
"## [Problem 44](https://projecteuler.net/problem=44)"
]
},
{
"cell_type": "code",
"execution_count": 46,
"id": "11f43a9d",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
" 44: Pentagon Numbers 82 msec ⇒ 5482660 ✅ "
]
},
"execution_count": 46,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def euler_44():\n",
" \"\"\"Pentagon Numbers: Find the pair of pentagonal numbers Pj, Pk whose sum and\n",
" difference are both pentagonal and D = |Pk - Pj| is minimised; what is D?\"\"\"\n",
" pents = [n * (3 * n - 1) // 2 for n in range(1, 10_000)]\n",
" contains = set(pents).__contains__\n",
" # Scan k upwards; the first hit is the minimising pair (known answer at k = 2167).\n",
" for k in range(2, 10_000):\n",
" Pk = pents[k - 1]\n",
" for j in range(k - 2, -1, -1):\n",
" Pj = pents[j]\n",
" if contains(Pk - Pj) and contains(Pk + Pj):\n",
" return Pk - Pj\n",
"run(euler_44)\n"
]
},
{
"cell_type": "markdown",
"id": "3ec3696d",
"metadata": {},
"source": [
"## [Problem 45](https://projecteuler.net/problem=45)"
]
},
{
"cell_type": "code",
"execution_count": 47,
"id": "4dd37319",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
" 45: Triangular, Pentagonal, and Hexagonal 4 msec ⇒ 1533776805 ✅ "
]
},
"execution_count": 47,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def euler_45():\n",
" \"\"\"Triangular, Pentagonal, and Hexagonal: Find the next number after 40755 that is\n",
" triangular, pentagonal and hexagonal.\"\"\"\n",
" def is_pent(m):\n",
" r = isqrt(24 * m + 1) # m = p(3p-1)/2 iff 24m+1 is a square with r == 5 (mod 6)\n",
" return r * r == 24 * m + 1 and r % 6 == 5\n",
" # Every hexagonal number H(n) = n(2n-1) is automatically the triangle T(2n-1).\n",
" for n in count(144): # 40755 is H(143)\n",
" H = n * (2 * n - 1)\n",
" if is_pent(H):\n",
" return H\n",
"run(euler_45)\n"
]
},
{
"cell_type": "markdown",
"id": "9943edf8",
"metadata": {},
"source": [
"## [Problem 46](https://projecteuler.net/problem=46)"
]
},
{
"cell_type": "code",
"execution_count": 48,
"id": "c3455753",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
" 46: Goldbach's Other Conjecture 1 msec ⇒ 5777 ✅ "
]
},
"execution_count": 48,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def euler_46():\n",
" \"\"\"Goldbach's Other Conjecture: What is the smallest odd composite that cannot be\n",
" written as the sum of a prime and twice a square?\"\"\"\n",
" limit = 10_000\n",
" is_p = bytearray(b'\\x01') * limit\n",
" is_p[0:2] = b'\\x00\\x00'\n",
" for n in range(2, isqrt(limit) + 1):\n",
" if is_p[n]:\n",
" is_p[n*n::n] = b'\\x00' * len(range(n*n, limit, n))\n",
" n = 9\n",
" while True:\n",
" if not is_p[n] and not any(is_p[n - 2*k*k] for k in range(1, isqrt(n // 2) + 1)):\n",
" return n\n",
" n += 2\n",
"run(euler_46)\n"
]
},
{
"cell_type": "markdown",
"id": "20709d40",
"metadata": {},
"source": [
"## [Problem 47](https://projecteuler.net/problem=47)"
]
},
{
"cell_type": "code",
"execution_count": 49,
"id": "1eb02989",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
" 47: Distinct Primes Factors 26 msec ⇒ 134043 ✅ "
]
},
"execution_count": 49,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def euler_47():\n",
" \"\"\"Distinct Primes Factors: Find the first four consecutive integers each having\n",
" exactly four distinct prime factors, and give the first of them.\"\"\"\n",
" limit = 200_000\n",
" nfactors = bytearray(limit) # number of distinct prime factors of each n\n",
" for p in range(2, limit):\n",
" if nfactors[p] == 0: # p is prime: it contributes one factor to each multiple\n",
" for m in range(p, limit, p):\n",
" nfactors[m] += 1\n",
" for n in range(2, limit - 3):\n",
" if nfactors[n] == nfactors[n+1] == nfactors[n+2] == nfactors[n+3] == 4:\n",
" return n\n",
"run(euler_47)\n"
]
},
{
"cell_type": "markdown",
"id": "26ffad3a",
"metadata": {},
"source": [
"## [Problem 48](https://projecteuler.net/problem=48)"
]
},
{
"cell_type": "code",
"execution_count": 50,
"id": "64ffb2dd",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
" 48: Self Powers 1 msec ⇒ 9110846700 ✅ "
]
},
"execution_count": 50,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def euler_48():\n",
" \"\"\"Self Powers: Find the last ten digits of the series 1^1 + 2^2 + ... + 1000^1000.\"\"\"\n",
" return sum(pow(i, i, 10**10) for i in range(1, 1001)) % 10**10\n",
"run(euler_48)\n"
]
},
{
"cell_type": "markdown",
"id": "22aadb0d",
"metadata": {},
"source": [
"## [Problem 49](https://projecteuler.net/problem=49)"
]
},
{
"cell_type": "code",
"execution_count": 51,
"id": "a1461995",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
" 49: Prime Permutations 0 msec ⇒ 296962999629 ✅ "
]
},
"execution_count": 51,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def euler_49():\n",
" \"\"\"Prime Permutations: Given the arithmetic sequence 1487, 4817, 8147 of 4-digit\n",
" primes (step 3330) whose terms are permutations of each other, find the one other\n",
" such sequence and concatenate its three terms into a 12-digit number.\"\"\"\n",
" limit = 10_000\n",
" is_p = bytearray(b'\\x01') * limit\n",
" is_p[0:2] = b'\\x00\\x00'\n",
" for n in range(2, isqrt(limit) + 1):\n",
" if is_p[n]:\n",
" is_p[n*n::n] = b'\\x00' * len(range(n*n, limit, n))\n",
" for p in range(1489, limit - 6660, 2): # start just past the known first sequence\n",
" q, r = p + 3330, p + 6660\n",
" if (is_p[p] and is_p[q] and is_p[r]\n",
" and sorted(str(p)) == sorted(str(q)) == sorted(str(r))):\n",
" return int(str(p) + str(q) + str(r))\n",
"run(euler_49)\n"
]
},
{
"cell_type": "markdown",
"id": "65ef8349",
"metadata": {},
"source": [
"## [Problem 50](https://projecteuler.net/problem=50)"
]
},
{
"cell_type": "code",
"execution_count": 52,
"id": "cbbc43d4",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
" 50: Consecutive Prime Sum 26 msec ⇒ 997651 ✅ "
]
},
"execution_count": 52,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def euler_50():\n",
" \"\"\"Consecutive Prime Sum: Which prime below one million can be written as the sum\n",
" of the most consecutive primes?\"\"\"\n",
" limit = million\n",
" is_p = bytearray(b'\\x01') * limit\n",
" is_p[0:2] = b'\\x00\\x00'\n",
" for n in range(2, isqrt(limit) + 1):\n",
" if is_p[n]:\n",
" is_p[n*n::n] = b'\\x00' * len(range(n*n, limit, n))\n",
" primes = [n for n in range(limit) if is_p[n]]\n",
" prefix = list(accumulate(primes, initial=0))\n",
" best_len = best_sum = 0\n",
" for i in range(len(primes)):\n",
" # Only windows longer than the current best are worth examining.\n",
" for j in range(i + best_len + 1, len(primes) + 1):\n",
" s = prefix[j] - prefix[i]\n",
" if s >= limit:\n",
" break\n",
" if is_p[s]:\n",
" best_len, best_sum = j - i, s\n",
" return best_sum\n",
"run(euler_50)\n"
]
},
{
"cell_type": "markdown",
"id": "e13d51f4",
"metadata": {},
"source": [
"# Project Euler Problems 51–60"
]
},
{
"cell_type": "markdown",
"id": "996690c4",
"metadata": {},
"source": [
"## [Problem 51](https://projecteuler.net/problem=51)"
]
},
{
"cell_type": "code",
"execution_count": 53,
"id": "f043c31f",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
" 51: Prime Digit Replacements 72 msec ⇒ 121313 ✅ "
]
},
"execution_count": 53,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def euler_51():\n",
" \"\"\"Prime Digit Replacements: Find the smallest prime which, by replacing part of\n",
" the number with the same digit, is part of an eight prime value family.\"\"\"\n",
" limit = million\n",
" is_p = bytearray(b'\\x01') * limit\n",
" is_p[0:2] = b'\\x00\\x00'\n",
" for n in range(2, isqrt(limit) + 1):\n",
" if is_p[n]:\n",
" is_p[n*n::n] = b'\\x00' * len(range(n*n, limit, n))\n",
" primes = [n for n in range(limit) if is_p[n]]\n",
" # A family of 8 needs exactly 3 replaced digits: with 1 or 2 wildcards some member\n",
" # is divisible by 3, and 4+ wildcards cap the family at 7 members.\n",
" for L in range(2, 7):\n",
" families = defaultdict(list) # digit pattern with '*' wildcards -> primes matching\n",
" lo = 10 ** (L - 1)\n",
" for p in primes:\n",
" if p < lo:\n",
" continue\n",
" if p >= 10 * lo:\n",
" break\n",
" s = str(p)\n",
" for d, c in Counter(s).items():\n",
" if c >= 3:\n",
" positions = [i for i, ch in enumerate(s) if ch == d]\n",
" for mask in combinations(positions, 3):\n",
" key = ''.join('*' if i in mask else s[i] for i in range(L))\n",
" families[key].append(p)\n",
" winners = [min(g) for g in families.values() if len(g) >= 8]\n",
" if winners:\n",
" return min(winners)\n",
"run(euler_51)\n"
]
},
{
"cell_type": "markdown",
"id": "356542fa",
"metadata": {},
"source": [
"## [Problem 52](https://projecteuler.net/problem=52)"
]
},
{
"cell_type": "code",
"execution_count": 54,
"id": "5584061d",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
" 52: Permuted Multiples 22 msec ⇒ 142857 ✅ "
]
},
"execution_count": 54,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def euler_52():\n",
" \"\"\"Permuted Multiples: Find the smallest positive integer x such that 2x, 3x, 4x,\n",
" 5x and 6x contain the same digits.\"\"\"\n",
" # 6x must have as many digits as x, so x < 10^L/6 for an L-digit x (starts with 1).\n",
" for L in count(1):\n",
" for x in range(10 ** (L - 1), 10 ** L // 6 + 1):\n",
" s = sorted(str(x))\n",
" if all(sorted(str(k * x)) == s for k in (2, 3, 4, 5, 6)):\n",
" return x\n",
"run(euler_52)\n"
]
},
{
"cell_type": "markdown",
"id": "b488fd22",
"metadata": {},
"source": [
"## [Problem 53](https://projecteuler.net/problem=53)"
]
},
{
"cell_type": "code",
"execution_count": 55,
"id": "22807d3f",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
" 53: Combinatoric Selections 0 msec ⇒ 4075 ✅ "
]
},
"execution_count": 55,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def euler_53():\n",
" \"\"\"Combinatoric Selections: How many values of C(n, r), for 1 <= n <= 100,\n",
" exceed one million?\"\"\"\n",
" return quantify((comb(n, r) for n in range(1, 101) for r in range(n + 1)),\n",
" lambda c: c > million)\n",
"run(euler_53)\n"
]
},
{
"cell_type": "markdown",
"id": "c4d5cf94",
"metadata": {},
"source": [
"## [Problem 54](https://projecteuler.net/problem=54)"
]
},
{
"cell_type": "code",
"execution_count": 56,
"id": "49c8c995",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
" 54: Poker Hands 4 msec ⇒ 376 ✅ "
]
},
"execution_count": 56,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def euler_54(data=DATA[54]):\n",
" \"\"\"Poker Hands: Given 1000 random hands dealt to two players, how many does\n",
" player 1 (the first five cards) win?\"\"\"\n",
" def score(hand):\n",
" values = sorted(('23456789TJQKA'.index(c[0]) for c in hand), reverse=True)\n",
" if values == [12, 3, 2, 1, 0]: # wheel: ace plays low in a 5-high straight\n",
" values = [3, 2, 1, 0, -1]\n",
" flush = len({c[1] for c in hand}) == 1\n",
" straight = len(set(values)) == 5 and values[0] - values[4] == 4\n",
" groups = sorted(Counter(values).items(), key=lambda kv: (kv[1], kv[0]), reverse=True)\n",
" tie = tuple(v for v, n in groups for _ in range(n))\n",
" kind = groups[0][1]\n",
" category = (8 if straight and flush else 7 if kind == 4 else\n",
" 6 if kind == 3 and groups[1][1] == 2 else 5 if flush else\n",
" 4 if straight else 3 if kind == 3 else\n",
" 2 if kind == 2 and groups[1][1] == 2 else 1 if kind == 2 else 0)\n",
" return (category, tie)\n",
" wins = 0\n",
" for line in data.splitlines():\n",
" cards = line.split()\n",
" if len(cards) == 10 and score(cards[:5]) > score(cards[5:]):\n",
" wins += 1\n",
" return wins\n",
"run(euler_54)\n"
]
},
{
"cell_type": "markdown",
"id": "081fd574",
"metadata": {},
"source": [
"## [Problem 55](https://projecteuler.net/problem=55)"
]
},
{
"cell_type": "code",
"execution_count": 57,
"id": "17e005b2",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
" 55: Lychrel Numbers 8 msec ⇒ 249 ✅ "
]
},
"execution_count": 57,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def euler_55():\n",
" \"\"\"Lychrel Numbers: How many Lychrel numbers are there below ten-thousand, i.e.\n",
" numbers that never form a palindrome within fifty reverse-and-add iterations?\"\"\"\n",
" def is_lychrel(n):\n",
" for _ in range(50):\n",
" n += int(str(n)[::-1])\n",
" s = str(n)\n",
" if s == s[::-1]:\n",
" return False\n",
" return True\n",
" return quantify(range(1, 10_000), is_lychrel)\n",
"run(euler_55)\n"
]
},
{
"cell_type": "markdown",
"id": "756966b7",
"metadata": {},
"source": [
"## [Problem 56](https://projecteuler.net/problem=56)"
]
},
{
"cell_type": "code",
"execution_count": 58,
"id": "9b09bf4a",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
" 56: Powerful Digit Sum 22 msec ⇒ 972 ✅ "
]
},
"execution_count": 58,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def euler_56():\n",
" \"\"\"Powerful Digit Sum: Considering natural numbers a, b < 100, what is the\n",
" maximum digital sum of a^b?\"\"\"\n",
" return max(sum(map(int, str(a ** b))) for a in range(1, 100) for b in range(1, 100))\n",
"run(euler_56)\n"
]
},
{
"cell_type": "markdown",
"id": "44c04e82",
"metadata": {},
"source": [
"## [Problem 57](https://projecteuler.net/problem=57)"
]
},
{
"cell_type": "code",
"execution_count": 59,
"id": "93dd2801",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
" 57: Square Root Convergents 1 msec ⇒ 153 ✅ "
]
},
"execution_count": 59,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def euler_57():\n",
" \"\"\"Square Root Convergents: In the first one-thousand expansions of the continued\n",
" fraction for the square root of two, how many fractions have a numerator with more\n",
" digits than the denominator?\"\"\"\n",
" n, d = 1, 1\n",
" found = 0\n",
" for _ in range(1000):\n",
" n, d = n + 2 * d, n + d # next convergent of sqrt(2)\n",
" found += len(str(n)) > len(str(d))\n",
" return found\n",
"run(euler_57)\n"
]
},
{
"cell_type": "markdown",
"id": "c4b116a0",
"metadata": {},
"source": [
"## [Problem 58](https://projecteuler.net/problem=58)"
]
},
{
"cell_type": "code",
"execution_count": 60,
"id": "bd56ce35",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
" 58: Spiral Primes 44 msec ⇒ 26241 ✅ "
]
},
"execution_count": 60,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def euler_58():\n",
" \"\"\"Spiral Primes: What is the side length of the square spiral for which the ratio\n",
" of primes along both diagonals first falls below 10%?\"\"\"\n",
" def is_prime(n):\n",
" # Deterministic Miller-Rabin for n < 3.3e9 (corners stay below 7e8).\n",
" if n < 2:\n",
" return False\n",
" for p in (2, 3, 5, 7, 11):\n",
" if n % p == 0:\n",
" return n == p\n",
" d, s = n - 1, 0\n",
" while d % 2 == 0:\n",
" d, s = d // 2, s + 1\n",
" for a in (2, 3, 5, 7, 11):\n",
" x = pow(a, d, n)\n",
" if x == 1 or x == n - 1:\n",
" continue\n",
" for _ in range(s - 1):\n",
" x = x * x % n\n",
" if x == n - 1:\n",
" break\n",
" else:\n",
" return False\n",
" return True\n",
" primes = 0\n",
" for layer in count(1):\n",
" side = 2 * layer + 1\n",
" sq = side * side\n",
" # The fourth corner sq is itself a square, so only three can be prime.\n",
" primes += quantify((sq - k * (side - 1) for k in (1, 2, 3)), is_prime)\n",
" if primes / (2 * side - 1) < 0.1:\n",
" return side\n",
"run(euler_58)\n"
]
},
{
"cell_type": "markdown",
"id": "44ab2370",
"metadata": {},
"source": [
"## [Problem 59](https://projecteuler.net/problem=59)"
]
},
{
"cell_type": "code",
"execution_count": 61,
"id": "9c14d1b5",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
" 59: XOR Decryption 25 msec ⇒ 107359 ✅ "
]
},
"execution_count": 61,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def euler_59(data=DATA[59]):\n",
" \"\"\"XOR Decryption: The given ASCII codes were XOR-encrypted with a repeating key of\n",
" three lowercase letters; decrypt the text and give the sum of its ASCII codes.\"\"\"\n",
" codes = [int(x) for x in re.findall(r'\\d+', data)]\n",
" printable = set(range(32, 127))\n",
" # Each key byte only touches every third code; filter bytes that keep text printable.\n",
" candidates = [[k for k in range(ord('a'), ord('z') + 1)\n",
" if all((c ^ k) in printable for c in codes[j::3])]\n",
" for j in range(3)]\n",
" def decrypt(key):\n",
" return bytes(c ^ key[i % 3] for i, c in enumerate(codes))\n",
" def english_score(key):\n",
" text = decrypt(key)\n",
" return 100 * text.count(b' the ') + text.count(b' ')\n",
" return sum(decrypt(max(product(*candidates), key=english_score)))\n",
"run(euler_59)\n"
]
},
{
"cell_type": "markdown",
"id": "0af8a41e",
"metadata": {},
"source": [
"## [Problem 60](https://projecteuler.net/problem=60)"
]
},
{
"cell_type": "code",
"execution_count": 62,
"id": "20d60f39",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
" 60: Prime Pair Sets 350 msec ⇒ 26033 ✅ "
]
},
"execution_count": 62,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def euler_60():\n",
" \"\"\"Prime Pair Sets: Find the lowest sum for a set of five primes for which any two\n",
" primes concatenated in either order produce another prime.\"\"\"\n",
" limit = 10_000\n",
" is_p = bytearray(b'\\x01') * limit\n",
" is_p[0:2] = b'\\x00\\x00'\n",
" for n in range(2, isqrt(limit) + 1):\n",
" if is_p[n]:\n",
" is_p[n*n::n] = b'\\x00' * len(range(n*n, limit, n))\n",
" primes = [n for n in range(limit) if is_p[n]]\n",
" # Composites are rejected wholesale by one gcd against a primorial; the survivors\n",
" # get a deterministic Miller-Rabin (bases 2, 7, 61: valid below 4.76e9, while all\n",
" # concatenations tested here are below 1e8).\n",
" primorial = prod(p for p in primes if 5 <= p <= 397)\n",
"\n",
" def is_prime(n):\n",
" if n < 10_000:\n",
" return is_p[n]\n",
" if gcd(n, primorial) != 1:\n",
" return False\n",
" d, s = (n - 1) >> 1, 1\n",
" while d % 2 == 0:\n",
" d, s = d >> 1, s + 1\n",
" for a in (2, 7, 61):\n",
" x = pow(a, d, n)\n",
" if x != 1 and x != n - 1:\n",
" for _ in range(s - 1):\n",
" x = x * x % n\n",
" if x == n - 1:\n",
" break\n",
" else:\n",
" return False\n",
" return True\n",
"\n",
" best = inf\n",
" def search(cands, chosen, total):\n",
" nonlocal best\n",
" if len(chosen) == 5:\n",
" best = min(best, total)\n",
" return\n",
" for i, p in enumerate(cands):\n",
" if total + p >= best:\n",
" break # cands is ascending, so nothing later can improve on best\n",
" search([q for q in cands[i+1:] if q in nbrs[p]], chosen + [p], total + p)\n",
"\n",
" # For primes > 3 the concatenation p|q is divisible by 3 unless p and q share a\n",
" # residue mod 3, so a valid set lies inside one residue class (optionally together\n",
" # with 3). 2 and 5 can never appear: a concatenation ending in 2 or 5 is composite.\n",
" for residue in (1, 2):\n",
" group = [p for p in primes if p % 3 == residue]\n",
" scale = [10 ** len(str(p)) for p in group]\n",
" nbrs = {p: set() for p in group}\n",
" for i, p in enumerate(group):\n",
" sp = scale[i]\n",
" for j in range(i + 1, len(group)):\n",
" q = group[j]\n",
" if is_prime(p * scale[j] + q) and is_prime(q * sp + p):\n",
" nbrs[p].add(q)\n",
" nbrs[q].add(p)\n",
" search(group, [], 0)\n",
" search([p for i, p in enumerate(group)\n",
" if is_prime(3 * scale[i] + p) and is_prime(10 * p + 3)], [3], 3)\n",
" return best\n",
"run(euler_60)\n"
]
},
{
"cell_type": "markdown",
"id": "85f4b0ad",
"metadata": {},
"source": [
"# Project Euler Problems 61–70"
]
},
{
"cell_type": "markdown",
"id": "1bf6c0ba",
"metadata": {},
"source": [
"## [Problem 61](https://projecteuler.net/problem=61)"
]
},
{
"cell_type": "code",
"execution_count": 63,
"id": "c3d85b79",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
" 61: Cyclical Figurate Numbers 5 msec ⇒ 28684 ✅ "
]
},
"execution_count": 63,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def euler_61():\n",
" \"\"\"Cyclical Figurate Numbers: Find the sum of the only ordered set of six cyclic 4-digit numbers for which each polygonal type, triangle to octagonal, is represented by a different number in the set.\"\"\"\n",
" def poly(kind, n):\n",
" return n * ((kind - 2) * n - (kind - 4)) // 2\n",
" # 4-digit polygonal numbers per kind; an entry needs a two-digit suffix to link onward from.\n",
" numbers = {}\n",
" for kind in range(3, 9):\n",
" entries = []\n",
" n = 1\n",
" while poly(kind, n) < 10_000:\n",
" value = poly(kind, n)\n",
" if value >= 1000 and value % 100 >= 10:\n",
" entries.append(value)\n",
" n += 1\n",
" numbers[kind] = entries\n",
"\n",
" def extend(kinds, chain):\n",
" if len(chain) == 6:\n",
" return chain if chain[-1] % 100 == chain[0] // 100 else None\n",
" link = chain[-1] % 100\n",
" for kind in range(3, 9):\n",
" if kind not in kinds:\n",
" for value in numbers[kind]:\n",
" if value // 100 == link:\n",
" found = extend(kinds | {kind}, chain + [value])\n",
" if found:\n",
" return found\n",
" return None\n",
"\n",
" for kind in range(3, 9):\n",
" for start in numbers[kind]:\n",
" cycle = extend({kind}, [start])\n",
" if cycle:\n",
" return sum(cycle)\n",
"run(euler_61)\n"
]
},
{
"cell_type": "markdown",
"id": "0cc1415c",
"metadata": {},
"source": [
"## [Problem 62](https://projecteuler.net/problem=62)"
]
},
{
"cell_type": "code",
"execution_count": 64,
"id": "ee1824b9",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
" 62: Cubic Permutations 27 msec ⇒ 127035954683 ✅ "
]
},
"execution_count": 64,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def euler_62(target=5):\n",
" \"\"\"Cubic Permutations: Find the smallest cube for which exactly five permutations of its digits are also cubes.\"\"\"\n",
" classes = defaultdict(list) # sorted digits -> cubes with those digits, in increasing order\n",
" n = 1\n",
" while True:\n",
" digits = len(str(n ** 3))\n",
" while len(str(n ** 3)) == digits: # finish a whole digit length so its classes are complete\n",
" cube = n ** 3\n",
" classes[tuple(sorted(str(cube)))].append(cube)\n",
" n += 1\n",
" complete = [members[0] for members in classes.values() if len(members) == target]\n",
" if complete:\n",
" return min(complete)\n",
"run(euler_62)\n"
]
},
{
"cell_type": "markdown",
"id": "bac96322",
"metadata": {},
"source": [
"## [Problem 63](https://projecteuler.net/problem=63)"
]
},
{
"cell_type": "code",
"execution_count": 65,
"id": "0598762e",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
" 63: Powerful Digit Counts 0 msec ⇒ 49 ✅ "
]
},
"execution_count": 65,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def euler_63():\n",
" \"\"\"Powerful Digit Counts: Count how many positive integers are both an n-th power and have exactly n digits, for some integer n >= 1.\"\"\"\n",
" total = 0\n",
" for b in count(1):\n",
" # a^b has exactly b digits iff 10^(b-1) <= a^b (and a <= 9 keeps a^b < 10^b).\n",
" hits = quantify(a ** b >= 10 ** (b - 1) for a in range(1, 10))\n",
" if hits == 0:\n",
" return total\n",
" total += hits\n",
"run(euler_63)\n"
]
},
{
"cell_type": "markdown",
"id": "e88ad670",
"metadata": {},
"source": [
"## [Problem 64](https://projecteuler.net/problem=64)"
]
},
{
"cell_type": "code",
"execution_count": 66,
"id": "19ee2110",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
" 64: Odd Period Square Roots 19 msec ⇒ 1322 ✅ "
]
},
"execution_count": 66,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def euler_64(limit=10_000):\n",
" \"\"\"Odd Period Square Roots: Count how many continued fractions for sqrt(n) with n <= 10000 have an odd period.\"\"\"\n",
" def period(n):\n",
" root = isqrt(n)\n",
" if root * root == n:\n",
" return 0\n",
" m, d, a = 0, 1, root\n",
" length = 0\n",
" while a != 2 * root: # the period ends when a reaches twice the leading term\n",
" m = d * a - m\n",
" d = (n - m * m) // d\n",
" a = (root + m) // d\n",
" length += 1\n",
" return length\n",
" return quantify(period(n) % 2 for n in range(2, limit + 1))\n",
"run(euler_64)\n"
]
},
{
"cell_type": "markdown",
"id": "ad9c8f3e",
"metadata": {},
"source": [
"## [Problem 65](https://projecteuler.net/problem=65)"
]
},
{
"cell_type": "code",
"execution_count": 67,
"id": "e10cc766",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
" 65: Convergents of e 0 msec ⇒ 272 ✅ "
]
},
"execution_count": 67,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def euler_65(which=100):\n",
" \"\"\"Convergents of e: Find the sum of the digits in the numerator of the 100th convergent of the continued fraction for e.\"\"\"\n",
" # e = [2; 1, 2, 1, 1, 4, 1, 1, 6, ...]: every third multiplier is 2k, the rest are 1.\n",
" multipliers = [2] + [2 * (i // 3 + 1) if i % 3 == 2 else 1 for i in range(1, which)]\n",
" h_prev2, h_prev1 = 0, 1\n",
" for a in multipliers:\n",
" h_prev2, h_prev1 = h_prev1, a * h_prev1 + h_prev2\n",
" return sum(int(d) for d in str(h_prev1))\n",
"run(euler_65)\n"
]
},
{
"cell_type": "markdown",
"id": "82cd1c6b",
"metadata": {},
"source": [
"## [Problem 66](https://projecteuler.net/problem=66)"
]
},
{
"cell_type": "code",
"execution_count": 68,
"id": "8f4ddee1",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
" 66: Diophantine Equation 2 msec ⇒ 661 ✅ "
]
},
"execution_count": 68,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def euler_66(limit=1000):\n",
" \"\"\"Diophantine Equation: Among minimal solutions of x^2 - D*y^2 = 1 for nonsquare D <= 1000, find the D with the largest minimal x.\"\"\"\n",
" def minimal_x(D):\n",
" # Walk the convergents of sqrt(D); the first one solving Pell's equation is minimal.\n",
" root = isqrt(D)\n",
" m, d, a = 0, 1, root\n",
" h2, h1 = 0, 1 # convergent numerators h[-2], h[-1]\n",
" k2, k1 = 1, 0 # convergent denominators\n",
" while True:\n",
" h2, h1 = h1, a * h1 + h2\n",
" k2, k1 = k1, a * k1 + k2\n",
" if h1 * h1 - D * k1 * k1 == 1:\n",
" return h1\n",
" m = d * a - m\n",
" d = (D - m * m) // d\n",
" a = (root + m) // d\n",
"\n",
" best_D, best_x = 0, 0\n",
" for D in range(2, limit + 1):\n",
" if isqrt(D) ** 2 != D:\n",
" x = minimal_x(D)\n",
" if x > best_x:\n",
" best_D, best_x = D, x\n",
" return best_D\n",
"run(euler_66)\n"
]
},
{
"cell_type": "markdown",
"id": "63c04c31",
"metadata": {},
"source": [
"## [Problem 67](https://projecteuler.net/problem=67)"
]
},
{
"cell_type": "code",
"execution_count": 69,
"id": "c8fc2e1c",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
" 67: Maximum Path Sum II 0 msec ⇒ 7273 ✅ "
]
},
"execution_count": 69,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def euler_67(data=DATA[67]):\n",
" \"\"\"Maximum Path Sum II: Find the maximum total from top to bottom of the 100-row triangle, moving to adjacent numbers on the row below.\"\"\"\n",
" triangle = [[int(cell) for cell in line.split()] for line in data.strip().splitlines()]\n",
" best = triangle[-1] # fold rows upward, tracking the best subtotal at each position\n",
" for row in reversed(triangle[:-1]):\n",
" best = [row[i] + max(best[i], best[i + 1]) for i in range(len(row))]\n",
" return best[0]\n",
"run(euler_67)\n"
]
},
{
"cell_type": "markdown",
"id": "55639f31",
"metadata": {},
"source": [
"## [Problem 68](https://projecteuler.net/problem=68)"
]
},
{
"cell_type": "code",
"execution_count": 70,
"id": "14eec884",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
" 68: Magic 5-gon Ring 1 msec ⇒ 6531031914842725 ✅ "
]
},
"execution_count": 70,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def euler_68():\n",
" \"\"\"Magic 5-gon Ring: Find the maximum 16-digit string describing a magic 5-gon ring filled with the numbers 1 to 10, concatenated clockwise starting from the lowest outer node.\"\"\"\n",
" best = 0\n",
" for inner in combinations(range(1, 11), 5):\n",
" outer = sorted(set(range(1, 11)) - set(inner))\n",
" # Each inner node sits in two lines, so 5 * line_sum = sum(outer) + 2 * sum(inner).\n",
" total = 55 + sum(inner)\n",
" if total % 5:\n",
" continue\n",
" line_sum = total // 5\n",
" anchor = min(inner) # fix the rotation to avoid counting the same ring repeatedly\n",
" for tail in permutations([x for x in inner if x != anchor]):\n",
" ring = (anchor,) + tail\n",
" outers = [line_sum - ring[i] - ring[(i + 1) % 5] for i in range(5)]\n",
" if sorted(outers) != outer:\n",
" continue\n",
" start = outers.index(min(outers))\n",
" string = ''.join(str(outers[(start + j) % 5]) + str(ring[(start + j) % 5])\n",
" + str(ring[(start + j + 1) % 5]) for j in range(5))\n",
" if len(string) == 16:\n",
" best = max(best, int(string))\n",
" return best\n",
"run(euler_68)\n"
]
},
{
"cell_type": "markdown",
"id": "ed0596e2",
"metadata": {},
"source": [
"## [Problem 69](https://projecteuler.net/problem=69)"
]
},
{
"cell_type": "code",
"execution_count": 71,
"id": "6e0108c6",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
" 69: Totient Maximum 0 msec ⇒ 510510 ✅ "
]
},
"execution_count": 71,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def euler_69(limit=1_000_000):\n",
" \"\"\"Totient Maximum: Find the value of n <= 1,000,000 for which n/phi(n) is a maximum.\"\"\"\n",
" # n/phi(n) = product of p/(p-1) over distinct prime factors p, so the winner is\n",
" # the largest primorial within the limit.\n",
" bound = 100 # the primes needed stay well below this\n",
" sieve = bytearray(b'\\x01') * bound\n",
" sieve[0:2] = b'\\x00\\x00'\n",
" for p in range(2, isqrt(bound) + 1):\n",
" if sieve[p]:\n",
" sieve[p * p::p] = bytes(len(sieve[p * p::p]))\n",
" result = 1\n",
" for p in range(2, bound):\n",
" if sieve[p]:\n",
" if result * p > limit:\n",
" return result\n",
" result *= p\n",
"run(euler_69)\n"
]
},
{
"cell_type": "markdown",
"id": "9a122070",
"metadata": {},
"source": [
"## [Problem 70](https://projecteuler.net/problem=70)"
]
},
{
"cell_type": "code",
"execution_count": 72,
"id": "5b0387bd",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
" 70: Totient Permutation 38 msec ⇒ 8319823 ✅ "
]
},
"execution_count": 72,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def euler_70(limit=10_000_000):\n",
" \"\"\"Totient Permutation: Find the n below 10^7 for which phi(n) is a permutation of n and n/phi(n) is minimal.\"\"\"\n",
" # The minimum of n/phi(n) = product of p/(p-1) over distinct prime factors turns out\n",
" # to be below 1.001 (a witness is found below), and any n with ratio < 1.001 has a\n",
" # very special shape, so a full totient sieve is unnecessary:\n",
" # * every prime factor p of n satisfies p/(p-1) < 1.001, hence p > 1001;\n",
" # * three such factors already exceed the limit (1009 * 1013 * 1019 > 10^7), as does\n",
" # any power beyond the second (1009^2 * 1013 > 10^7) or cube (1009^3 > 10^7);\n",
" # * so n is a prime (phi = n-1, never a digit permutation of n since n and n-1\n",
" # differ mod 9), a prime square p^2, or a semiprime p*q with p < q.\n",
" top = limit // 1000 + 1 # primes stay below this\n",
" sieve = bytearray(b'\\x01') * (top + 1)\n",
" sieve[0:2] = b'\\x00\\x00'\n",
" for p in range(2, isqrt(top) + 1):\n",
" if sieve[p]:\n",
" sieve[p * p::p] = bytes(len(sieve[p * p::p]))\n",
" primes = [p for p in range(2, top + 1) if sieve[p]]\n",
"\n",
" best_n, best_phi = 0, 1\n",
" root = isqrt(limit - 1)\n",
" for i, p in enumerate(primes):\n",
" if p < 1009 or p > root:\n",
" continue\n",
" candidates = [(p * p, p * (p - 1))]\n",
" qmax = (limit - 1) // p\n",
" for q in primes[i + 1:]:\n",
" if q > qmax:\n",
" break\n",
" candidates.append((p * q, (p - 1) * (q - 1)))\n",
" for n, f in candidates:\n",
" if 1000 * n < 1001 * f and sorted(str(n)) == sorted(str(f)):\n",
" if best_n == 0 or n * best_phi < best_n * f:\n",
" best_n, best_phi = n, f\n",
" return best_n\n",
"run(euler_70)\n"
]
},
{
"cell_type": "markdown",
"id": "6bedc54a",
"metadata": {},
"source": [
"# Project Euler Problems 71–80"
]
},
{
"cell_type": "markdown",
"id": "9bd91d7b",
"metadata": {},
"source": [
"## [Problem 71](https://projecteuler.net/problem=71)"
]
},
{
"cell_type": "code",
"execution_count": 73,
"id": "6bc55197",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
" 71: Ordered Fractions 57 msec ⇒ 428570 ✅ "
]
},
"execution_count": 73,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def euler_71(limit=1_000_000):\n",
" \"\"\"Ordered Fractions: Find the numerator of the fraction immediately to the left of 3/7 in the sorted set of reduced proper fractions with denominator at most one million.\"\"\"\n",
" best_n, best_d = 0, 1\n",
" for d in range(2, limit + 1):\n",
" n = (3 * d - 1) // 7 # largest numerator still keeping n/d < 3/7\n",
" if n * best_d > best_n * d:\n",
" best_n, best_d = n, d\n",
" return best_n // gcd(best_n, best_d)\n",
"run(euler_71)\n"
]
},
{
"cell_type": "markdown",
"id": "6eab4715",
"metadata": {},
"source": [
"## [Problem 72](https://projecteuler.net/problem=72)"
]
},
{
"cell_type": "code",
"execution_count": 74,
"id": "3f462982",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
" 72: Counting Fractions 129 msec ⇒ 303963552391 ✅ "
]
},
"execution_count": 74,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def euler_72(limit=1_000_000):\n",
" \"\"\"Counting Fractions: Count the elements of the set of reduced proper fractions with denominator at most one million.\"\"\"\n",
" # Linear totient sieve: each composite is written once, by its smallest prime factor.\n",
" phi = [0] * (limit + 1)\n",
" phi[1] = 1\n",
" primes = []\n",
" for i in range(2, limit + 1):\n",
" if phi[i] == 0: # i is prime\n",
" phi[i] = i - 1\n",
" primes.append(i)\n",
" fi = phi[i]\n",
" for p in primes:\n",
" m = i * p\n",
" if m > limit:\n",
" break\n",
" if i % p == 0:\n",
" phi[m] = fi * p\n",
" break\n",
" phi[m] = fi * (p - 1)\n",
" return sum(phi) - 1 # every d >= 2 contributes phi(d) fractions; subtract phi(1)\n",
"run(euler_72)\n"
]
},
{
"cell_type": "markdown",
"id": "b1f67390",
"metadata": {},
"source": [
"## [Problem 73](https://projecteuler.net/problem=73)"
]
},
{
"cell_type": "code",
"execution_count": 75,
"id": "2c2d59c3",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
" 73: Counting Fractions in a Range 2 msec ⇒ 7295372 ✅ "
]
},
"execution_count": 75,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def euler_73(limit=12_000):\n",
" \"\"\"Counting Fractions in a Range: Count the reduced proper fractions lying strictly between 1/3 and 1/2 with denominator at most 12,000.\"\"\"\n",
" # Mobius inversion: count = sum_d mu(d) * G(limit // d), where G(M) counts all pairs\n",
" # (a, b) with b <= M and b/3 < a < b/2, reduced or not.\n",
" mu = [1] * (limit + 1)\n",
" composite = bytearray(limit + 1)\n",
" primes = []\n",
" for i in range(2, limit + 1):\n",
" if not composite[i]:\n",
" primes.append(i)\n",
" mu[i] = -1\n",
" for p in primes:\n",
" m = i * p\n",
" if m > limit:\n",
" break\n",
" composite[m] = 1\n",
" if i % p == 0:\n",
" mu[m] = 0\n",
" break\n",
" mu[m] = -mu[i]\n",
"\n",
" def G(M):\n",
" # Per b the admissible a number floor((b+1)/2) - floor(b/3) - 1; sum closed forms.\n",
" q, r = divmod(M, 3)\n",
" return (M + 1) ** 2 // 4 - (3 * q * (q - 1) // 2 + q * (r + 1)) - M\n",
"\n",
" return sum(mu[d] * G(limit // d) for d in range(1, limit + 1))\n",
"run(euler_73)\n"
]
},
{
"cell_type": "markdown",
"id": "5231e85b",
"metadata": {},
"source": [
"## [Problem 74](https://projecteuler.net/problem=74)"
]
},
{
"cell_type": "code",
"execution_count": 76,
"id": "0c8452d1",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
" 74: Digit Factorial Chains 115 msec ⇒ 402 ✅ "
]
},
"execution_count": 76,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def euler_74(limit=1_000_000, target=60):\n",
" \"\"\"Digit Factorial Chains: Count how many starting numbers below one million produce a digit-factorial chain with exactly sixty non-repeating terms.\"\"\"\n",
" fact = [factorial(d) for d in range(10)]\n",
" pow10 = [10 ** d for d in range(10)]\n",
" # The digit-factorial sum depends only on the multiset of digits, whose signature\n",
" # (digit d counted at place 10^d) memoizes a whole permutation class at once.\n",
" sig_of = [0] * limit\n",
" for n in range(1, limit):\n",
" sig_of[n] = sig_of[n // 10] + pow10[n % 10]\n",
"\n",
" def signature(n):\n",
" sig = 0\n",
" while n:\n",
" n, d = divmod(n, 10)\n",
" sig += pow10[d]\n",
" return sig\n",
"\n",
" def digit_facts(n):\n",
" total = 0\n",
" while n:\n",
" n, d = divmod(n, 10)\n",
" total += fact[d]\n",
" return total\n",
"\n",
" chain_len = {} # signature -> count of non-repeating chain terms from there\n",
" hits = 0\n",
" for start in range(1, limit):\n",
" s0 = sig_of[start]\n",
" if s0 not in chain_len:\n",
" trail, marks = [], set()\n",
" v, s = start, s0\n",
" while s not in chain_len and s not in marks:\n",
" marks.add(s)\n",
" trail.append(s)\n",
" v = digit_facts(v)\n",
" s = signature(v)\n",
" if s in chain_len: # ran into a solved signature\n",
" base, cycle_at = chain_len[s] + len(trail), len(trail)\n",
" else: # closed a fresh cycle within this trail\n",
" base, cycle_at = len(trail), trail.index(s)\n",
" for i, g in enumerate(trail):\n",
" chain_len[g] = base - i if i < cycle_at else base - cycle_at\n",
" hits += chain_len[s0] == target\n",
" return hits\n",
"run(euler_74)\n"
]
},
{
"cell_type": "markdown",
"id": "a3173a96",
"metadata": {},
"source": [
"## [Problem 75](https://projecteuler.net/problem=75)"
]
},
{
"cell_type": "code",
"execution_count": 77,
"id": "8d42b311",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
" 75: Singular Integer Right Triangles 84 msec ⇒ 161667 ✅ "
]
},
"execution_count": 77,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def euler_75(limit=1_500_000):\n",
" \"\"\"Singular Integer Right Triangles: Count the perimeters up to 1,500,000 that can be bent into exactly one integer-sided right angle triangle.\"\"\"\n",
" counts = [0] * (limit + 1)\n",
" for m in range(2, isqrt(limit // 2) + 2):\n",
" for n in range(1 + m % 2, m, 2): # n < m of the opposite parity\n",
" if gcd(m, n) == 1: # Euclid's formula: primitive triple with perimeter 2*m*(m+n)\n",
" perimeter = 2 * m * (m + n)\n",
" if perimeter > limit:\n",
" break\n",
" for p in range(perimeter, limit + 1, perimeter):\n",
" counts[p] += 1 # every multiple of a primitive triple is a triple too\n",
" return counts.count(1)\n",
"run(euler_75)\n"
]
},
{
"cell_type": "markdown",
"id": "cf38fd21",
"metadata": {},
"source": [
"## [Problem 76](https://projecteuler.net/problem=76)"
]
},
{
"cell_type": "code",
"execution_count": 78,
"id": "00fe403e",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
" 76: Counting Summations 0 msec ⇒ 190569291 ✅ "
]
},
"execution_count": 78,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def euler_76(n=100):\n",
" \"\"\"Counting Summations: Count the ways to write 100 as a sum of at least two positive integers.\"\"\"\n",
" ways = [1] + [0] * n\n",
" for part in range(1, n): # restricting parts to 1..99 rules out the bare sum \"100\"\n",
" for total in range(part, n + 1):\n",
" ways[total] += ways[total - part]\n",
" return ways[n]\n",
"run(euler_76)\n"
]
},
{
"cell_type": "markdown",
"id": "00f1f0b5",
"metadata": {},
"source": [
"## [Problem 77](https://projecteuler.net/problem=77)"
]
},
{
"cell_type": "code",
"execution_count": 79,
"id": "e0eb2669",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
" 77: Prime Summations 0 msec ⇒ 71 ✅ "
]
},
"execution_count": 79,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def euler_77(target=5000):\n",
" \"\"\"Prime Summations: Find the first value that can be written as a sum of primes in over five thousand different ways.\"\"\"\n",
" bound = 200 # the answer lies well below this\n",
" sieve = bytearray(b'\\x01') * (bound + 1)\n",
" sieve[0:2] = b'\\x00\\x00'\n",
" for p in range(2, isqrt(bound) + 1):\n",
" if sieve[p]:\n",
" sieve[p * p::p] = bytes(len(sieve[p * p::p]))\n",
" ways = [1] + [0] * bound\n",
" for p in range(2, bound + 1):\n",
" if sieve[p]:\n",
" for total in range(p, bound + 1):\n",
" ways[total] += ways[total - p]\n",
" return first(n for n in range(2, bound + 1) if ways[n] > target)\n",
"run(euler_77)\n"
]
},
{
"cell_type": "markdown",
"id": "ab922822",
"metadata": {},
"source": [
"## [Problem 78](https://projecteuler.net/problem=78)"
]
},
{
"cell_type": "code",
"execution_count": 80,
"id": "e5a0926e",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
" 78: Coin Partitions 591 msec ⇒ 55374 ✅ "
]
},
"execution_count": 80,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def euler_78(modulus=1_000_000):\n",
" \"\"\"Coin Partitions: Find the least value of n for which the number of partitions of n is divisible by one million.\"\"\"\n",
" # Pentagonal number theorem:\n",
" # p(n) = sum over k of (-1)^(k+1) * (p(n - k(3k-1)/2) + p(n - k(3k+1)/2)).\n",
" parts = [1]\n",
" n = 0\n",
" while True:\n",
" n += 1\n",
" total = 0\n",
" # g tracks the pentagonal number k(3k-1)/2 (advanced by step = 3k+1); its\n",
" # partner k(3k+1)/2 equals g + k. Odd k adds, even k subtracts.\n",
" k, g, step = 1, 1, 4\n",
" while g + k <= n: # both pentagonals in range, so no per-term checks\n",
" total += parts[n - g] + parts[n - g - k]\n",
" g += step\n",
" step += 3\n",
" k += 1\n",
" if g + k > n:\n",
" break\n",
" total -= parts[n - g] + parts[n - g - k]\n",
" g += step\n",
" step += 3\n",
" k += 1\n",
" if g <= n: # leftover boundary term, with the sign of the pending k\n",
" total = total + parts[n - g] if k & 1 else total - parts[n - g]\n",
" if total % modulus == 0:\n",
" return n\n",
" parts.append(total % modulus)\n",
"run(euler_78)\n"
]
},
{
"cell_type": "markdown",
"id": "d3bd1929",
"metadata": {},
"source": [
"## [Problem 79](https://projecteuler.net/problem=79)"
]
},
{
"cell_type": "code",
"execution_count": 81,
"id": "1ae74b84",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
" 79: Passcode Derivation 0 msec ⇒ 73162890 ✅ "
]
},
"execution_count": 81,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def euler_79(data=DATA[79]):\n",
" \"\"\"Passcode Derivation: Given fifty successful three-digit login attempts, derive the shortest possible secret passcode consistent with them.\"\"\"\n",
" triples = [tuple(line) for line in data.split()]\n",
" before = {d: set() for d in set(chain.from_iterable(triples))}\n",
" for a, b, c in triples:\n",
" before[b].add(a)\n",
" before[c].update((a, b))\n",
" code = ''\n",
" while before: # repeatedly emit the unique digit nothing precedes (topological order)\n",
" digit = first(d for d, predecessors in before.items() if not predecessors)\n",
" code += digit\n",
" del before[digit]\n",
" for predecessors in before.values():\n",
" predecessors.discard(digit)\n",
" return int(code)\n",
"run(euler_79)\n"
]
},
{
"cell_type": "markdown",
"id": "c18f8706",
"metadata": {},
"source": [
"## [Problem 80](https://projecteuler.net/problem=80)"
]
},
{
"cell_type": "code",
"execution_count": 82,
"id": "d91ef3cc",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
" 80: Square Root Digital Expansion 0 msec ⇒ 40886 ✅ "
]
},
"execution_count": 82,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def euler_80(limit=100, digits=100):\n",
" \"\"\"Square Root Digital Expansion: For the first one hundred natural numbers, find the total of the digital sums of the first one hundred decimal digits of all the irrational square roots.\"\"\"\n",
" total = 0\n",
" for n in range(2, limit + 1):\n",
" if isqrt(n) ** 2 != n:\n",
" # floor(sqrt(n) * 10^99): the units digit followed by the first 99 decimals.\n",
" scaled = isqrt(n * 10 ** (2 * (digits - 1)))\n",
" total += sum(int(d) for d in str(scaled))\n",
" return total\n",
"run(euler_80)\n"
]
},
{
"cell_type": "markdown",
"id": "a16089cb",
"metadata": {},
"source": [
"# Project Euler Problems 81–90"
]
},
{
"cell_type": "markdown",
"id": "086b1623",
"metadata": {},
"source": [
"## [Problem 81](https://projecteuler.net/problem=81)"
]
},
{
"cell_type": "code",
"execution_count": 83,
"id": "2a2361f5",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
" 81: Path Sum 1 msec ⇒ 427337 ✅ "
]
},
"execution_count": 83,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def euler_81(data=DATA[81]):\n",
" \"\"\"Path Sum: Two Ways: Find the minimal path sum from the top-left to the\n",
" bottom-right of an 80x80 matrix when only right and down moves are allowed.\"\"\"\n",
" grid = [[int(x) for x in line.split(',')] for line in data.split()]\n",
" best = list(accumulate(grid[0])) # first row: only reachable from the left\n",
" for row in grid[1:]:\n",
" new = [best[0] + row[0]] # first cell: only reachable from above\n",
" for w, up in zip(row[1:], best[1:]):\n",
" new.append(w + min(new[-1], up))\n",
" best = new\n",
" return best[-1]\n",
"run(euler_81)\n"
]
},
{
"cell_type": "markdown",
"id": "517bd5a3",
"metadata": {},
"source": [
"## [Problem 82](https://projecteuler.net/problem=82)"
]
},
{
"cell_type": "code",
"execution_count": 84,
"id": "aad63d3f",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
" 82: Path Sum 1 msec ⇒ 260324 ✅ "
]
},
"execution_count": 84,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def euler_82(data=DATA[82]):\n",
" \"\"\"Path Sum: Three Ways: Find the minimal path sum from any cell of the left\n",
" column to any cell of the right column, moving up, down, or right.\"\"\"\n",
" grid = [[int(x) for x in line.split(',')] for line in data.split()]\n",
" n = len(grid)\n",
" cost = [row[0] for row in grid]\n",
" for c in range(1, n):\n",
" col = [grid[r][c] for r in range(n)]\n",
" new = [cost[r] + col[r] for r in range(n)] # step right into this column\n",
" for r in range(1, n): # relax downwards\n",
" new[r] = min(new[r], new[r - 1] + col[r])\n",
" for r in range(n - 2, -1, -1): # relax upwards\n",
" new[r] = min(new[r], new[r + 1] + col[r])\n",
" cost = new\n",
" return min(cost)\n",
"run(euler_82)\n"
]
},
{
"cell_type": "markdown",
"id": "bdf2550b",
"metadata": {},
"source": [
"## [Problem 83](https://projecteuler.net/problem=83)"
]
},
{
"cell_type": "code",
"execution_count": 85,
"id": "6712df29",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
" 83: Path Sum 6 msec ⇒ 425185 ✅ "
]
},
"execution_count": 85,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def euler_83(data=DATA[83]):\n",
" \"\"\"Path Sum: Four Ways: Find the minimal path sum from the top-left to the\n",
" bottom-right of the matrix when moves in all four directions are allowed.\"\"\"\n",
" grid = [[int(x) for x in line.split(',')] for line in data.split()]\n",
" n = len(grid)\n",
" dist = {(0, 0): grid[0][0]} # Dijkstra from the corner\n",
" heap = [(grid[0][0], 0, 0)]\n",
" while heap:\n",
" d, r, c = heapq.heappop(heap)\n",
" if (r, c) == (n - 1, n - 1):\n",
" return d\n",
" if d > dist[(r, c)]:\n",
" continue # stale heap entry\n",
" for r2, c2 in ((r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)):\n",
" if 0 <= r2 < n and 0 <= c2 < n:\n",
" d2 = d + grid[r2][c2]\n",
" if d2 < dist.get((r2, c2), inf):\n",
" dist[(r2, c2)] = d2\n",
" heapq.heappush(heap, (d2, r2, c2))\n",
"run(euler_83)\n"
]
},
{
"cell_type": "markdown",
"id": "8562ab0b",
"metadata": {},
"source": [
"## [Problem 84](https://projecteuler.net/problem=84)"
]
},
{
"cell_type": "code",
"execution_count": 86,
"id": "f49544bc",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
" 84: Monopoly Odds 32 msec ⇒ 101524 ✅ "
]
},
"execution_count": 86,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def euler_84(sides=4):\n",
" \"\"\"Monopoly Odds: Playing Monopoly with two 4-sided dice, which three squares\n",
" are most likely to be occupied? Answer as a six-digit string of the squares.\"\"\"\n",
" GO, JAIL, G2J = 0, 10, 30\n",
" CC, CH = {2, 17, 33}, {7, 22, 36}\n",
" RAILWAYS, UTILITIES = (5, 15, 25, 35), (12, 28)\n",
" def resolve(sq):\n",
" \"\"\"Outcomes after landing on `sq`: (destination, probability, sent_to_jail).\"\"\"\n",
" if sq == G2J:\n",
" return [(JAIL, 1.0, True)]\n",
" if sq in CC: # 2 of 16 cards move you\n",
" return [(GO, 1 / 16, False), (JAIL, 1 / 16, True), (sq, 14 / 16, False)]\n",
" if sq in CH: # 10 of 16 cards move you\n",
" rail = next((r for r in RAILWAYS if r > sq), RAILWAYS[0])\n",
" util = next((u for u in UTILITIES if u > sq), UTILITIES[0])\n",
" moves = [(GO, False), (JAIL, True), (11, False), (24, False), (39, False),\n",
" (5, False), (rail, False), (rail, False), (util, False), (sq - 3, False)]\n",
" return [(d, 1 / 16, jail) for d, jail in moves] + [(sq, 6 / 16, False)]\n",
" return [(sq, 1.0, False)]\n",
" rolls = Counter((a + b, a == b) for a in range(1, sides + 1)\n",
" for b in range(1, sides + 1))\n",
" trans = {} # (square, run of doubles) -> {state: prob}\n",
" for sq in range(40):\n",
" for dbl in range(3):\n",
" dest = defaultdict(float)\n",
" for (step, is_dbl), ways in rolls.items():\n",
" if is_dbl and dbl == 2: # three doubles in a row: go to jail\n",
" dest[(JAIL, 0)] += ways / (sides * sides)\n",
" else:\n",
" for sq2, p, jail in resolve((sq + step) % 40):\n",
" # a trip to jail ends the turn; otherwise doubles keep rolling\n",
" dest[(sq2, 0 if jail else (dbl + 1 if is_dbl else 0))] += p * ways / (sides * sides)\n",
" trans[(sq, dbl)] = dict(dest)\n",
" dist = {(GO, 0): 1.0} # iterate the Markov chain to equilibrium\n",
" for _ in range(300):\n",
" new = defaultdict(float)\n",
" for state, p in dist.items():\n",
" for state2, q in trans[state].items():\n",
" new[state2] += p * q\n",
" dist = new\n",
" by_square = defaultdict(float)\n",
" for (sq, _), p in dist.items():\n",
" by_square[sq] += p\n",
" top3 = sorted(by_square, key=by_square.get, reverse=True)[:3]\n",
" return int(''.join(f'{sq:02d}' for sq in top3))\n",
"run(euler_84)\n"
]
},
{
"cell_type": "markdown",
"id": "ef5b9f5c",
"metadata": {},
"source": [
"## [Problem 85](https://projecteuler.net/problem=85)"
]
},
{
"cell_type": "code",
"execution_count": 87,
"id": "93220a41",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
" 85: Counting Rectangles 0 msec ⇒ 2772 ✅ "
]
},
"execution_count": 87,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def euler_85(target=2_000_000):\n",
" \"\"\"Counting Rectangles: Which rectangular grid contains a number of rectangles\n",
" nearest to two million? Answer with the area of that grid.\"\"\"\n",
" def rects(a, b):\n",
" return a * (a + 1) * b * (b + 1) // 4 # tri(a) * tri(b)\n",
" best_diff, best_area = target, 0\n",
" a, b = 1, 1\n",
" while rects(a, b) < target:\n",
" b += 1 # smallest b with rects(1, b) >= target\n",
" while True:\n",
" while b > a and rects(a, b - 1) >= target:\n",
" b -= 1 # keep b minimal for this a (wlog a <= b)\n",
" for bb in {b - 1, b}: # closest counts straddle the target\n",
" if bb >= a:\n",
" diff = abs(rects(a, bb) - target)\n",
" if diff < best_diff:\n",
" best_diff, best_area = diff, a * bb\n",
" if rects(a, a) > target + best_diff: # bigger a can only do worse\n",
" return best_area\n",
" a += 1\n",
"run(euler_85)\n"
]
},
{
"cell_type": "markdown",
"id": "011771a5",
"metadata": {},
"source": [
"## [Problem 86](https://projecteuler.net/problem=86)"
]
},
{
"cell_type": "code",
"execution_count": 88,
"id": "fc9f0166",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
" 86: Cuboid Route 4 msec ⇒ 1818 ✅ "
]
},
"execution_count": 88,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def euler_86(goal=million):\n",
" \"\"\"Cuboid Route: Find the least M such that more than one million cuboids with\n",
" integer sides a <= b <= c <= M have an integer shortest path between opposite corners.\"\"\"\n",
" def tally(bound):\n",
" \"\"\"cnt[c] = number of (a, b) with a <= b <= c and (a+b)^2 + c^2 a perfect square.\"\"\"\n",
" # The shortest path squared is (a+b)^2 + c^2, so hunt Pythagorean pairs (s, c)\n",
" # with s = a+b <= 2*bound and c <= bound via Euclid's formula.\n",
" cnt = [0] * (bound + 1)\n",
" for m in range(2, 2 * isqrt(2 * bound) + 2):\n",
" for n in range(1 + m % 2, m, 2): # coprime m > n of opposite parity\n",
" if gcd(m, n) == 1:\n",
" x, y = m * m - n * n, 2 * m * n\n",
" for k in count(1):\n",
" if k * min(x, y) > bound:\n",
" break\n",
" for s, c in ((k * x, k * y), (k * y, k * x)):\n",
" if c <= bound and s <= 2 * bound:\n",
" lo, hi = max(1, s - c), s // 2 # a in [lo, hi] <=> 1<=a<=b<=c, a+b=s\n",
" if hi >= lo:\n",
" cnt[c] += hi - lo + 1\n",
" return cnt\n",
" bound = 512\n",
" while True: # double the search bound until the goal is crossed\n",
" total = 0\n",
" for c, ways in enumerate(tally(bound)):\n",
" total += ways\n",
" if total > goal:\n",
" return c\n",
" bound *= 2\n",
"run(euler_86)\n"
]
},
{
"cell_type": "markdown",
"id": "1c9d9ec4",
"metadata": {},
"source": [
"## [Problem 87](https://projecteuler.net/problem=87)"
]
},
{
"cell_type": "code",
"execution_count": 89,
"id": "bbc03ea3",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
" 87: Prime Power Triples 170 msec ⇒ 1097343 ✅ "
]
},
"execution_count": 89,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def euler_87(limit=50_000_000):\n",
" \"\"\"Prime Power Triples: How many numbers below fifty million can be written as\n",
" p^2 + q^3 + r^4 with p, q, r all prime?\"\"\"\n",
" def primes_upto(n):\n",
" sieve = bytearray(b'\\x01') * (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(2, n + 1) if sieve[i]]\n",
" primes = primes_upto(isqrt(limit)) # p^2 < limit, so p <= sqrt(limit)\n",
" cubes = [q for q in primes if q**3 < limit]\n",
" quarts = [r for r in primes if r**4 < limit]\n",
" seen = set()\n",
" for p in primes:\n",
" p2 = p * p\n",
" for q in cubes:\n",
" pq = p2 + q**3\n",
" if pq >= limit:\n",
" break\n",
" for r in quarts:\n",
" total = pq + r**4\n",
" if total >= limit:\n",
" break\n",
" seen.add(total)\n",
" return len(seen)\n",
"run(euler_87)\n"
]
},
{
"cell_type": "markdown",
"id": "27ccd15d",
"metadata": {},
"source": [
"## [Problem 88](https://projecteuler.net/problem=88)"
]
},
{
"cell_type": "code",
"execution_count": 90,
"id": "b8526753",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
" 88: Product-sum Numbers 48 msec ⇒ 7587457 ✅ "
]
},
"execution_count": 90,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def euler_88(K=12000):\n",
" \"\"\"Product-sum Numbers: What is the sum of all the minimal product-sum numbers\n",
" for sets of size k, for 2 <= k <= 12000?\"\"\"\n",
" best = [None] * (K + 1) # best[k] = smallest product-sum number for size k\n",
" def extend(start, product, summ, count):\n",
" # Appending (product - sum) ones to the factors gives a set of size k = product - sum + count.\n",
" k = product - summ + count\n",
" if k > K:\n",
" return\n",
" if best[k] is None or product < best[k]:\n",
" best[k] = product\n",
" f = start # factors in nondecreasing order avoid duplicates\n",
" while product * f <= 2 * K: # minimal product-sum numbers never exceed 2K\n",
" extend(f, product * f, summ + f, count + 1)\n",
" f += 1\n",
" extend(2, 1, 0, 0)\n",
" return sum(set(best[2:]))\n",
"run(euler_88)\n"
]
},
{
"cell_type": "markdown",
"id": "ee44e0a8",
"metadata": {},
"source": [
"## [Problem 89](https://projecteuler.net/problem=89)"
]
},
{
"cell_type": "code",
"execution_count": 91,
"id": "2b2bf378",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
" 89: Roman Numerals 1 msec ⇒ 743 ✅ "
]
},
"execution_count": 91,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def euler_89(data=DATA[89]):\n",
" \"\"\"Roman Numerals: How many characters are saved by rewriting each of the 1000\n",
" given Roman numerals in its minimal (canonical) form?\"\"\"\n",
" VAL = {'I': 1, 'V': 5, 'X': 10, 'L': 50, 'C': 100, 'D': 500, 'M': 1000}\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",
" def value(s):\n",
" nums = [VAL[c] for c in s] + [0] # a smaller value before a bigger one subtracts\n",
" return sum(-a if a < b else a for a, b in pairwise(nums))\n",
" def minimal(n):\n",
" out = ''\n",
" for v, sym in TABLE:\n",
" q, n = divmod(n, v)\n",
" out += sym * q\n",
" return out\n",
" return sum(len(s) - len(minimal(value(s))) for s in data.split())\n",
"run(euler_89)\n"
]
},
{
"cell_type": "markdown",
"id": "df3686bf",
"metadata": {},
"source": [
"## [Problem 90](https://projecteuler.net/problem=90)"
]
},
{
"cell_type": "code",
"execution_count": 92,
"id": "7778b334",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
" 90: Cube Digit Pairs 6 msec ⇒ 1217 ✅ "
]
},
"execution_count": 92,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def euler_90():\n",
" \"\"\"Cube Digit Pairs: In how many distinct ways can the digits 0-9 be placed on\n",
" two cubes (6 and 9 interchangeable) so that every square 01,04,...,81 is displayable?\"\"\"\n",
" squares = {(0, 1), (0, 4), (0, 6), (1, 6), (2, 5), (3, 6), (4, 6), (6, 4), (8, 1)} # 9 folded to 6\n",
" cubes = [frozenset(6 if d == 9 else d for d in combo)\n",
" for combo in combinations(range(10), 6)]\n",
" def displays_all(c1, c2):\n",
" return all((a in c1 and b in c2) or (a in c2 and b in c1) for a, b in squares)\n",
" return quantify(displays_all(c1, c2)\n",
" for i, c1 in enumerate(cubes) for c2 in cubes[i:])\n",
"run(euler_90)\n"
]
},
{
"cell_type": "markdown",
"id": "37d6ec92",
"metadata": {},
"source": [
"# Project Euler Problems 91–100"
]
},
{
"cell_type": "markdown",
"id": "f46ad276",
"metadata": {},
"source": [
"## [Problem 91](https://projecteuler.net/problem=91)"
]
},
{
"cell_type": "code",
"execution_count": 93,
"id": "286f8dca",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
" 91: Right Triangles with Integer Coordinates 2 msec ⇒ 14234 ✅ "
]
},
"execution_count": 93,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def euler_91(N=50):\n",
" \"\"\"Right Triangles with Integer Coordinates: How many right triangles can be formed\n",
" with vertices (0,0), (x1,y1), (x2,y2) where all coordinates are between 0 and 50?\"\"\"\n",
" def at_p(x, y):\n",
" \"\"\"Number of grid points Q such that triangle O, P=(x,y), Q has a right angle at P.\"\"\"\n",
" g = gcd(x, y)\n",
" u, v = -y // g, x // g # primitive step perpendicular to OP\n",
" total = 0\n",
" for sign in (1, -1): # walk the perpendicular line both ways\n",
" k = sign\n",
" while 0 <= x + k * u <= N and 0 <= y + k * v <= N:\n",
" total += 1\n",
" k += sign\n",
" return total\n",
" # N*N triangles have the right angle at O (P on the x-axis, Q on the y-axis);\n",
" # every other right triangle has its right angle at exactly one off-origin vertex.\n",
" return N * N + sum(at_p(x, y) for x in range(N + 1) for y in range(N + 1)\n",
" if (x, y) != (0, 0))\n",
"run(euler_91)\n"
]
},
{
"cell_type": "markdown",
"id": "edd1c5ee",
"metadata": {},
"source": [
"## [Problem 92](https://projecteuler.net/problem=92)"
]
},
{
"cell_type": "code",
"execution_count": 94,
"id": "7aa269b8",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
" 92: Square Digit Chains 10 msec ⇒ 8581146 ✅ "
]
},
"execution_count": 94,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def euler_92(digits=7):\n",
" \"\"\"Square Digit Chains: How many starting numbers below ten million have a\n",
" square-digit chain that ends at 89?\"\"\"\n",
" sq = [d * d for d in range(10)]\n",
" def fate(s):\n",
" while s not in (1, 89):\n",
" s = sum(sq[int(d)] for d in str(s))\n",
" return s\n",
" fates = {s: fate(s) for s in range(1, digits * 81 + 1)} # sums run up to 7*9^2 = 567\n",
" total = 0\n",
" # Count 7-digit strings (leading zeros allowed) by their multiset of digits.\n",
" for combo in combinations_with_replacement(range(10), digits):\n",
" if fates.get(sum(sq[d] for d in combo)) == 89:\n",
" total += factorial(digits) // prod(map(factorial, Counter(combo).values()))\n",
" return total\n",
"run(euler_92)\n"
]
},
{
"cell_type": "markdown",
"id": "4ad90522",
"metadata": {},
"source": [
"## [Problem 93](https://projecteuler.net/problem=93)"
]
},
{
"cell_type": "code",
"execution_count": 95,
"id": "433eeb4d",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
" 93: Arithmetic Expressions 132 msec ⇒ 1258 ✅ "
]
},
"execution_count": 95,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def euler_93():\n",
" \"\"\"Arithmetic Expressions: Which set of four distinct digits a 0}\n",
" n = 1\n",
" while Fraction(n) in ints:\n",
" n += 1\n",
" return n - 1\n",
" _, best = max((streak(ds), ds) for ds in combinations(range(1, 10), 4))\n",
" return int(''.join(map(str, best)))\n",
"run(euler_93)\n"
]
},
{
"cell_type": "markdown",
"id": "fc7ff50e",
"metadata": {},
"source": [
"## [Problem 94](https://projecteuler.net/problem=94)"
]
},
{
"cell_type": "code",
"execution_count": 96,
"id": "34aa90cd",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
" 94: Almost Equilateral Triangles 0 msec ⇒ 518408346 ✅ "
]
},
"execution_count": 96,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def euler_94(max_perimeter=10**9):\n",
" \"\"\"Almost Equilateral Triangles: Find the sum of the perimeters (not exceeding one\n",
" billion) of all triangles with sides (a, a, a+-1) that have an integer area.\"\"\"\n",
" # With equal side a and base b = a +/- 1, an integer area needs 4a^2 - b^2 square.\n",
" # Setting x = 3a -/+ 1 turns that into the Pell equation x^2 - 3m^2 = 4, whose\n",
" # solutions (x + m*sqrt(3)) = 2*(2 + sqrt(3))^k obey the recurrence u' = 4u - u_prev.\n",
" total = 0\n",
" x0, x1, m0, m1 = 2, 4, 0, 2\n",
" while True:\n",
" if m1: # skip the degenerate m = 0 solution\n",
" if x1 % 3 == 1: # x = 3a + 1 -> sides (a, a, a-1)\n",
" a = (x1 - 1) // 3\n",
" b, perimeter = a - 1, 3 * a - 1\n",
" elif x1 % 3 == 2: # x = 3a - 1 -> sides (a, a, a+1)\n",
" a = (x1 + 1) // 3\n",
" b, perimeter = a + 1, 3 * a + 1\n",
" else:\n",
" b = perimeter = 0\n",
" if b:\n",
" if perimeter > max_perimeter: # perimeters grow with x, so we can stop\n",
" return total\n",
" total += perimeter\n",
" x0, x1 = x1, 4 * x1 - x0\n",
" m0, m1 = m1, 4 * m1 - m0\n",
"run(euler_94)\n"
]
},
{
"cell_type": "markdown",
"id": "1004191d",
"metadata": {},
"source": [
"## [Problem 95](https://projecteuler.net/problem=95)"
]
},
{
"cell_type": "code",
"execution_count": 97,
"id": "fb269e87",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
" 95: Amicable Chains 358 msec ⇒ 14316 ✅ "
]
},
"execution_count": 97,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def euler_95(N=million):\n",
" \"\"\"Amicable Chains: For chains formed by iterating the sum of proper divisors,\n",
" find the smallest member of the longest amicable chain with all members <= 10^6.\"\"\"\n",
" # Sum-of-divisors sieve in O(N): sig[n] = sigma(n) (all divisors), built with a\n",
" # linear sieve over the least prime factor lp[n]; even arguments come for free from\n",
" # sigma(2^k * i) = sigma(2^k) * sigma(i), so only odd i are sieved.\n",
" lp = [0] * (N + 1)\n",
" sig = [1] * (N + 1)\n",
" pw = [1] * (N + 1) # pw[n] = exact power of lp[n] dividing n\n",
" primes = []\n",
" m, f = 2, 3\n",
" while m <= N: # powers of two: sigma(2^k) = 2^(k+1) - 1\n",
" sig[m] = f\n",
" m *= 2\n",
" f = 2 * f + 1\n",
" for i in range(3, N + 1, 2):\n",
" if lp[i]:\n",
" lpi, pwi, sigi = lp[i], pw[i], sig[i]\n",
" else:\n",
" lp[i] = pw[i] = lpi = pwi = i # i is prime\n",
" sigi = sig[i] = i + 1\n",
" primes.append(i)\n",
" m, f = 2 * i, 3 # all doublings 2^k * i of an odd part i\n",
" while m <= N:\n",
" sig[m] = sigi * f\n",
" m *= 2\n",
" f = 2 * f + 1\n",
" for p in primes:\n",
" if p > lpi:\n",
" break\n",
" ip = i * p\n",
" if ip > N:\n",
" break\n",
" lp[ip] = p\n",
" if p == lpi: # p already divides i: extend its power\n",
" pw[ip] = pwi * p\n",
" sig[ip] = sig[i // pwi] * (pwi * p * p - 1) // (p - 1)\n",
" break\n",
" pw[ip] = p # p coprime to i: sigma multiplies\n",
" sig[ip] = sigi * (p + 1)\n",
" sig[0] = N + 1 # make 0 a chain dead end (s(1) = 0)\n",
" # Follow divisor chains (s(n) = sigma(n) - n), stamping each visited node with the\n",
" # id of the chain that reached it; stopping at a node stamped by the CURRENT chain\n",
" # means we closed a loop.\n",
" stamp = [0] * (N + 1)\n",
" best_len = best_min = 0\n",
" for start in range(2, N + 1):\n",
" if stamp[start]:\n",
" continue\n",
" node = start\n",
" while node <= N and not stamp[node]:\n",
" stamp[node] = start\n",
" node = sig[node] - node\n",
" if node <= N and stamp[node] == start: # found a cycle; measure it once around\n",
" cyc_len, cyc_min, m = 1, node, sig[node] - node\n",
" while m != node:\n",
" cyc_len += 1\n",
" if m < cyc_min:\n",
" cyc_min = m\n",
" m = sig[m] - m\n",
" if cyc_len > best_len:\n",
" best_len, best_min = cyc_len, cyc_min\n",
" return best_min\n",
"run(euler_95)\n"
]
},
{
"cell_type": "markdown",
"id": "70b7a4ad",
"metadata": {},
"source": [
"## [Problem 96](https://projecteuler.net/problem=96)"
]
},
{
"cell_type": "code",
"execution_count": 98,
"id": "371b27c9",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
" 96: Su Doku 116 msec ⇒ 24702 ✅ "
]
},
"execution_count": 98,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def euler_96(data=DATA[96]):\n",
" \"\"\"Su Doku: Solve all 50 grids and sum the 3-digit numbers in the top-left corner\n",
" of each solution.\"\"\"\n",
" def solve(grid):\n",
" \"\"\"Backtracking search with bitmask candidate tracking; solves in place.\"\"\"\n",
" def box(i):\n",
" return (i // 27) * 3 + (i % 9) // 3\n",
" rows, cols, boxes = [0] * 9, [0] * 9, [0] * 9\n",
" for i, d in enumerate(grid):\n",
" if d:\n",
" bit = 1 << d\n",
" rows[i // 9] |= bit\n",
" cols[i % 9] |= bit\n",
" boxes[box(i)] |= bit\n",
" def search():\n",
" pick, opts = -1, None\n",
" for i, d in enumerate(grid): # choose the empty cell with fewest options\n",
" if d == 0:\n",
" used = rows[i // 9] | cols[i % 9] | boxes[box(i)]\n",
" cand = [v for v in range(1, 10) if not used >> v & 1]\n",
" if not cand:\n",
" return False\n",
" if opts is None or len(cand) < len(opts):\n",
" pick, opts = i, cand\n",
" if pick == -1:\n",
" return True # no empty cell left: solved\n",
" i = pick\n",
" for v in opts:\n",
" bit = 1 << v\n",
" grid[i] = v\n",
" rows[i // 9] |= bit; cols[i % 9] |= bit; boxes[box(i)] |= bit\n",
" if search():\n",
" return True\n",
" grid[i] = 0\n",
" rows[i // 9] &= ~bit; cols[i % 9] &= ~bit; boxes[box(i)] &= ~bit\n",
" return False\n",
" search()\n",
" return grid\n",
" lines = data.strip().splitlines() # each grid: a \"Grid NN\" line + 9 digit rows\n",
" grids = (lines[i + 1:i + 10] for i in range(0, len(lines), 10))\n",
" total = 0\n",
" for rows_ in grids:\n",
" solved = solve([int(ch) for row in rows_ for ch in row])\n",
" total += 100 * solved[0] + 10 * solved[1] + solved[2]\n",
" return total\n",
"run(euler_96)\n"
]
},
{
"cell_type": "markdown",
"id": "26780d11",
"metadata": {},
"source": [
"## [Problem 97](https://projecteuler.net/problem=97)"
]
},
{
"cell_type": "code",
"execution_count": 99,
"id": "0aa13995",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
" 97: Large Non-Mersenne Prime 0 msec ⇒ 8739992577 ✅ "
]
},
"execution_count": 99,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def euler_97():\n",
" \"\"\"Large Non-Mersenne Prime: What are the last ten digits of the non-Mersenne\n",
" prime 28433 * 2^7830457 + 1?\"\"\"\n",
" return (28433 * pow(2, 7830457, 10**10) + 1) % 10**10\n",
"run(euler_97)\n"
]
},
{
"cell_type": "markdown",
"id": "3b628fdb",
"metadata": {},
"source": [
"## [Problem 98](https://projecteuler.net/problem=98)"
]
},
{
"cell_type": "code",
"execution_count": 100,
"id": "ab4b98f1",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
" 98: Anagramic Squares 49 msec ⇒ 18769 ✅ "
]
},
"execution_count": 100,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def euler_98(data=DATA[98]):\n",
" \"\"\"Anagramic Squares: Assigning digits to letters consistently across a pair of\n",
" anagram words, what is the largest square number formed by any such pair?\"\"\"\n",
" words = data.replace('\"', '').split(',')\n",
" groups = defaultdict(list)\n",
" for w in words:\n",
" groups[tuple(sorted(w))].append(w)\n",
" groups = [ws for ws in groups.values() if len(ws) > 1]\n",
" longest = max(len(ws[0]) for ws in groups)\n",
" squares, square_sets = defaultdict(list), {}\n",
" for n in integers(1):\n",
" if len(str(n * n)) > longest:\n",
" break\n",
" squares[len(str(n * n))].append(n * n)\n",
" square_sets = {L: set(ss) for L, ss in squares.items()}\n",
" best = 0\n",
" for ws in groups:\n",
" L = len(ws[0])\n",
" for w in ws:\n",
" for sq in squares[L]:\n",
" digits = str(sq)\n",
" mapping = {}\n",
" for ch, d in zip(w, digits): # word -> square, letter by letter\n",
" if mapping.setdefault(ch, d) != d:\n",
" break # same letter, two digits: inconsistent\n",
" else:\n",
" if len(set(mapping.values())) < len(mapping):\n",
" continue # two letters share a digit: not a bijection\n",
" for other in ws:\n",
" if other != w:\n",
" t = int(''.join(mapping[c] for c in other))\n",
" if len(str(t)) == L and t in square_sets[L]:\n",
" best = max(best, sq, t)\n",
" return best\n",
"run(euler_98)\n"
]
},
{
"cell_type": "markdown",
"id": "a2235d7a",
"metadata": {},
"source": [
"## [Problem 99](https://projecteuler.net/problem=99)"
]
},
{
"cell_type": "code",
"execution_count": 101,
"id": "18e497b5",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
" 99: Largest Exponential 0 msec ⇒ 709 ✅ "
]
},
"execution_count": 101,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def euler_99(data=DATA[99]):\n",
" \"\"\"Largest Exponential: Which line of the file of base/exponent pairs has the\n",
" greatest numerical value?\"\"\"\n",
" def value(line):\n",
" base, exp = line.split(',')\n",
" return int(exp) * log(int(base)) # compare on the log scale\n",
" return max(enumerate(map(value, data.split()), 1), key=lambda p: p[1])[0]\n",
"run(euler_99)\n"
]
},
{
"cell_type": "markdown",
"id": "f58e1105",
"metadata": {},
"source": [
"## [Problem 100](https://projecteuler.net/problem=100)"
]
},
{
"cell_type": "code",
"execution_count": 102,
"id": "eeff6586",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"100: Arranged Probability 0 msec ⇒ 756872327473 ✅ "
]
},
"execution_count": 102,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def euler_100(limit=10**12):\n",
" \"\"\"Arranged Probability: In the first arrangement with more than 10^12 discs where\n",
" the probability of drawing two blue discs is exactly 1/2, how many blue discs are there?\"\"\"\n",
" # 2*b*(b-1) = t*(t-1) <=> (2t-1)^2 - 2*(2b-1)^2 = -1, a Pell equation whose\n",
" # solutions (x, y) = (2t-1, 2b-1) step via (x, y) -> (3x + 4y, 2x + 3y).\n",
" x, y = 1, 1\n",
" while True:\n",
" x, y = 3 * x + 4 * y, 2 * x + 3 * y\n",
" t, b = (x + 1) // 2, (y + 1) // 2\n",
" if t > limit:\n",
" return b\n",
"run(euler_100)\n"
]
},
{
"cell_type": "markdown",
"id": "da78ec31",
"metadata": {},
"source": [
"# Summary of Runs\n",
"\n",
"Here are all the answers and their run times."
]
},
{
"cell_type": "code",
"execution_count": 103,
"id": "392fc65e",
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Problems: 100\n",
"Run time in seconds: total: 3.4, max: 0.6, mean: 0.034, median: 0.002\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 33 msec ⇒ 906609 ✅ \n",
" 5: Smallest Multiple 0 msec ⇒ 232792560 ✅ \n",
" 6: Sum Square Difference 0 msec ⇒ 25164150 ✅ \n",
" 7: 10001st Prime 2 msec ⇒ 104743 ✅ \n",
" 8: Largest Product in a Series 0 msec ⇒ 23514624000 ✅ \n",
" 9: Special Pythagorean Triplet 0 msec ⇒ 31875000 ✅ \n",
" 10: Summation of Primes 31 msec ⇒ 142913828922 ✅ \n",
" 11: Largest Product in a Grid 1 msec ⇒ 70600674 ✅ \n",
" 12: Highly Divisible Triangular Number 30 msec ⇒ 76576500 ✅ \n",
" 13: Large Sum 0 msec ⇒ 5537376230 ✅ \n",
" 14: Longest Collatz Sequence 255 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 8 msec ⇒ 871198282 ✅ \n",
" 23: Non-Abundant Sums 17 msec ⇒ 4179871 ✅ \n",
" 24: Lexicographic Permutations 0 msec ⇒ 2783915460 ✅ \n",
" 25: 1000-digit Fibonacci Number 0 msec ⇒ 4782 ✅ \n",
" 26: Reciprocal Cycles 7 msec ⇒ 983 ✅ \n",
" 27: Quadratic Primes 67 msec ⇒ -59231 ✅ \n",
" 28: Number Spiral Diagonals 0 msec ⇒ 669171001 ✅ \n",
" 29: Distinct Powers 2 msec ⇒ 9183 ✅ \n",
" 30: Digit Fifth Powers 131 msec ⇒ 443839 ✅ \n",
" 31: Coin Sums 0 msec ⇒ 73682 ✅ \n",
" 32: Pandigital Products 15 msec ⇒ 45228 ✅ \n",
" 33: Digit Cancelling Fractions 2 msec ⇒ 100 ✅ \n",
" 34: Digit Factorials 33 msec ⇒ 40730 ✅ \n",
" 35: Circular Primes 37 msec ⇒ 55 ✅ \n",
" 36: Double-base Palindromes 0 msec ⇒ 872187 ✅ \n",
" 37: Truncatable Primes 1 msec ⇒ 748317 ✅ \n",
" 38: Pandigital Multiples 4 msec ⇒ 932718654 ✅ \n",
" 39: Integer Right Triangles 5 msec ⇒ 840 ✅ \n",
" 40: Champernowne's Constant 8 msec ⇒ 210 ✅ \n",
" 41: Pandigital Prime 0 msec ⇒ 7652413 ✅ \n",
" 42: Coded Triangle Numbers 1 msec ⇒ 162 ✅ \n",
" 43: Sub-string Divisibility 0 msec ⇒ 16695334890 ✅ \n",
" 44: Pentagon Numbers 82 msec ⇒ 5482660 ✅ \n",
" 45: Triangular, Pentagonal, and Hexagonal 4 msec ⇒ 1533776805 ✅ \n",
" 46: Goldbach's Other Conjecture 1 msec ⇒ 5777 ✅ \n",
" 47: Distinct Primes Factors 26 msec ⇒ 134043 ✅ \n",
" 48: Self Powers 1 msec ⇒ 9110846700 ✅ \n",
" 49: Prime Permutations 0 msec ⇒ 296962999629 ✅ \n",
" 50: Consecutive Prime Sum 26 msec ⇒ 997651 ✅ \n",
" 51: Prime Digit Replacements 72 msec ⇒ 121313 ✅ \n",
" 52: Permuted Multiples 22 msec ⇒ 142857 ✅ \n",
" 53: Combinatoric Selections 0 msec ⇒ 4075 ✅ \n",
" 54: Poker Hands 4 msec ⇒ 376 ✅ \n",
" 55: Lychrel Numbers 8 msec ⇒ 249 ✅ \n",
" 56: Powerful Digit Sum 22 msec ⇒ 972 ✅ \n",
" 57: Square Root Convergents 1 msec ⇒ 153 ✅ \n",
" 58: Spiral Primes 44 msec ⇒ 26241 ✅ \n",
" 59: XOR Decryption 25 msec ⇒ 107359 ✅ \n",
" 60: Prime Pair Sets 350 msec ⇒ 26033 ✅ \n",
" 61: Cyclical Figurate Numbers 5 msec ⇒ 28684 ✅ \n",
" 62: Cubic Permutations 27 msec ⇒ 127035954683 ✅ \n",
" 63: Powerful Digit Counts 0 msec ⇒ 49 ✅ \n",
" 64: Odd Period Square Roots 19 msec ⇒ 1322 ✅ \n",
" 65: Convergents of e 0 msec ⇒ 272 ✅ \n",
" 66: Diophantine Equation 2 msec ⇒ 661 ✅ \n",
" 67: Maximum Path Sum II 0 msec ⇒ 7273 ✅ \n",
" 68: Magic 5-gon Ring 1 msec ⇒ 6531031914842725 ✅ \n",
" 69: Totient Maximum 0 msec ⇒ 510510 ✅ \n",
" 70: Totient Permutation 38 msec ⇒ 8319823 ✅ \n",
" 71: Ordered Fractions 57 msec ⇒ 428570 ✅ \n",
" 72: Counting Fractions 129 msec ⇒ 303963552391 ✅ \n",
" 73: Counting Fractions in a Range 2 msec ⇒ 7295372 ✅ \n",
" 74: Digit Factorial Chains 115 msec ⇒ 402 ✅ \n",
" 75: Singular Integer Right Triangles 84 msec ⇒ 161667 ✅ \n",
" 76: Counting Summations 0 msec ⇒ 190569291 ✅ \n",
" 77: Prime Summations 0 msec ⇒ 71 ✅ \n",
" 78: Coin Partitions 591 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 6 msec ⇒ 425185 ✅ \n",
" 84: Monopoly Odds 32 msec ⇒ 101524 ✅ \n",
" 85: Counting Rectangles 0 msec ⇒ 2772 ✅ \n",
" 86: Cuboid Route 4 msec ⇒ 1818 ✅ \n",
" 87: Prime Power Triples 170 msec ⇒ 1097343 ✅ \n",
" 88: Product-sum Numbers 48 msec ⇒ 7587457 ✅ \n",
" 89: Roman Numerals 1 msec ⇒ 743 ✅ \n",
" 90: Cube Digit Pairs 6 msec ⇒ 1217 ✅ \n",
" 91: Right Triangles with Integer Coordinates 2 msec ⇒ 14234 ✅ \n",
" 92: Square Digit Chains 10 msec ⇒ 8581146 ✅ \n",
" 93: Arithmetic Expressions 132 msec ⇒ 1258 ✅ \n",
" 94: Almost Equilateral Triangles 0 msec ⇒ 518408346 ✅ \n",
" 95: Amicable Chains 358 msec ⇒ 14316 ✅ \n",
" 96: Su Doku 116 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()"
]
}
],
"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
}