142 lines
4.4 KiB
Plaintext
142 lines
4.4 KiB
Plaintext
{
|
|
"cells": [
|
|
{
|
|
"cell_type": "markdown",
|
|
"id": "a639246d",
|
|
"metadata": {},
|
|
"source": [
|
|
"# [Square Digit Chains](https://projecteuler.net/problem=92)\n",
|
|
"\n",
|
|
"It's easy enough to write a function that calculates the sum of the squares of the digits of a number."
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "code",
|
|
"execution_count": 1,
|
|
"id": "8b852b0c",
|
|
"metadata": {},
|
|
"outputs": [],
|
|
"source": [
|
|
"def sum_of_digit_squares(n):\n",
|
|
" total = 0\n",
|
|
" while n != 0:\n",
|
|
" total += (n % 10)^2\n",
|
|
" n //= 10\n",
|
|
" \n",
|
|
" return total"
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "markdown",
|
|
"id": "701c507a",
|
|
"metadata": {},
|
|
"source": [
|
|
"We can also write a memoized recursive function for determining whether a number arrives at 1 or 89 eventually."
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "code",
|
|
"execution_count": 2,
|
|
"id": "94553d41",
|
|
"metadata": {},
|
|
"outputs": [],
|
|
"source": [
|
|
"from functools import cache\n",
|
|
"\n",
|
|
"@cache\n",
|
|
"def arrives_at(n):\n",
|
|
" if n == 0:\n",
|
|
" return 0\n",
|
|
" \n",
|
|
" if n == 1:\n",
|
|
" return 1\n",
|
|
" \n",
|
|
" if n == 89:\n",
|
|
" return 89\n",
|
|
" \n",
|
|
" return arrives_at(sum_of_digit_squares(n))"
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "markdown",
|
|
"id": "628b83ee",
|
|
"metadata": {},
|
|
"source": [
|
|
"At this point, we could just evaluate `arrives_at` at every number from 1 to 10000000 and see how many starting numbers arrive at 89, but that's a little slow. To speed things up, observe that any pair of numbers with digits that are permutations of each other will arrive at the same number. For example, the sums of the squares of the digits of 112345 and 523141 are both 56, so they will both arrive at the same number (89), so we don't need to check both.\n",
|
|
"\n",
|
|
"So if we only check each distinct permutation of digits once, how many starting numbers does that leave us with? Well, it's the number of [multisets](https://en.wikipedia.org/wiki/Multiset) of (0,1,2,3,4,5,6,7,8,9) of cardinality 7, which is given by\n",
|
|
"$${10+7-1 \\choose 7} = 11440$$\n",
|
|
"Much better than $10^7$.\n",
|
|
"\n",
|
|
"However - continuing with the above example - even if we only check if 112345 arrives at 89, since all its distinct permutations also arrive at 89, we need to include all of them in our final total. Since there could be repeated digits, this isn't as simple as 7!. Fortunately, we can find the number of distinct permutations with the [multinomial coefficient](https://en.wikipedia.org/wiki/Multinomial_theorem). If the digit 0 shows up $k_0$ times in a seven digit number, the digit 1 $k_1$ times, and so on, the number of distinct permutations of the digits is\n",
|
|
"$${7 \\choose {k_0,k_1,k_2,\\ldots,k_9}} = \\frac{7!}{k_0! k_1! k_2!\\cdots k_9!}$$"
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "code",
|
|
"execution_count": 3,
|
|
"id": "9bde8257",
|
|
"metadata": {},
|
|
"outputs": [
|
|
{
|
|
"data": {
|
|
"text/plain": [
|
|
"8581146"
|
|
]
|
|
},
|
|
"execution_count": 3,
|
|
"metadata": {},
|
|
"output_type": "execute_result"
|
|
}
|
|
],
|
|
"source": [
|
|
"from itertools import combinations_with_replacement\n",
|
|
"from collections import Counter\n",
|
|
"\n",
|
|
"total = 0\n",
|
|
"for digits in combinations_with_replacement(range(0, 10), 7):\n",
|
|
" n = sum(10^k * d for (k, d) in enumerate(reversed(digits)))\n",
|
|
" if arrives_at(n) == 89:\n",
|
|
" c = Counter(digits)\n",
|
|
" total += multinomial(c.values())\n",
|
|
"\n",
|
|
"total"
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "markdown",
|
|
"id": "2ec607f2",
|
|
"metadata": {},
|
|
"source": [
|
|
"## Related sequences\n",
|
|
"* Numbers we iterate over: [A009994](https://oeis.org/A009994)\n",
|
|
"\n",
|
|
"#### Copyright (C) 2025 filifa\n",
|
|
"\n",
|
|
"This work is licensed under the [Creative Commons Attribution-ShareAlike 4.0 International license](https://creativecommons.org/licenses/by-sa/4.0/) and the [BSD Zero Clause license](https://spdx.org/licenses/0BSD.html)."
|
|
]
|
|
}
|
|
],
|
|
"metadata": {
|
|
"kernelspec": {
|
|
"display_name": "SageMath 9.5",
|
|
"language": "sage",
|
|
"name": "sagemath"
|
|
},
|
|
"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.11.2"
|
|
}
|
|
},
|
|
"nbformat": 4,
|
|
"nbformat_minor": 5
|
|
}
|