126 lines
3.8 KiB
Plaintext
126 lines
3.8 KiB
Plaintext
{
|
|
"cells": [
|
|
{
|
|
"cell_type": "markdown",
|
|
"id": "c117cd3c",
|
|
"metadata": {},
|
|
"source": [
|
|
"# [Cubic Permutations](https://projecteuler.net/problem=62)\n",
|
|
"\n",
|
|
"Fortunately, the numbers stay small enough here that we can just brute force this. We'll just iterate over cubes and store them in a dictionary, keyed on the sorted digits of the cubes. This way, two cubes that are permutations of each other will be under the same key, making it easy to tell when a cube has five cubic permutations.\n",
|
|
"\n",
|
|
"There's one little wrinkle to consider. Suppose we find a cube $c$ with five cubic permutations. If we continued on with the loop, we'd find more cubes that might be permutations of cubes smaller than $c$. This means if we stop as soon as we know that $c$ has five cubic permutations, it's possible we miss a that different, smaller cube *also* has five cubic permutations. To make sure this doesn't cause a problem, as soon as we find a cube with five cubic permutations, we'll set a limit of $10^k$, where $k$ is the number of digits in $c$. Once we pass that limit, we exit the loop - at that point, we know we have all cubes with $k$ or fewer digits represented in the dictionary.\n",
|
|
"\n",
|
|
"(If you failed to consider this and left it out of the program... you would actually still get the correct answer. So this isn't necessary to solve the problem, but is nice to know if want assurance that you have *the* smallest cube.)"
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "code",
|
|
"execution_count": 1,
|
|
"id": "0b6d278c",
|
|
"metadata": {},
|
|
"outputs": [],
|
|
"source": [
|
|
"from itertools import count\n",
|
|
"\n",
|
|
"permutations = dict()\n",
|
|
"limit = None\n",
|
|
"for n in count(1):\n",
|
|
" cube = n^3\n",
|
|
" if limit is not None and cube >= limit:\n",
|
|
" break\n",
|
|
" \n",
|
|
" digits = tuple(sorted(cube.digits()))\n",
|
|
" if digits not in permutations:\n",
|
|
" permutations[digits] = set()\n",
|
|
" permutations[digits].add(cube)\n",
|
|
" \n",
|
|
" if len(permutations[digits]) == 5:\n",
|
|
" limit = 10^len(digits)"
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "markdown",
|
|
"id": "bce01772",
|
|
"metadata": {},
|
|
"source": [
|
|
"Once we exit the loop, we just find the largest set in the dictionary."
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "code",
|
|
"execution_count": 2,
|
|
"id": "0153c670",
|
|
"metadata": {},
|
|
"outputs": [
|
|
{
|
|
"data": {
|
|
"text/plain": [
|
|
"{127035954683, 352045367981, 373559126408, 569310543872, 589323567104}"
|
|
]
|
|
},
|
|
"execution_count": 2,
|
|
"metadata": {},
|
|
"output_type": "execute_result"
|
|
}
|
|
],
|
|
"source": [
|
|
"s = max(permutations.values(), key=len)\n",
|
|
"s"
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "code",
|
|
"execution_count": 3,
|
|
"id": "9beac72e",
|
|
"metadata": {},
|
|
"outputs": [
|
|
{
|
|
"data": {
|
|
"text/plain": [
|
|
"127035954683"
|
|
]
|
|
},
|
|
"execution_count": 3,
|
|
"metadata": {},
|
|
"output_type": "execute_result"
|
|
}
|
|
],
|
|
"source": [
|
|
"min(s)"
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "markdown",
|
|
"id": "1701dfc7",
|
|
"metadata": {},
|
|
"source": [
|
|
"#### 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
|
|
}
|