54 lines
1.9 KiB
Plaintext
54 lines
1.9 KiB
Plaintext
{
|
|
"cells": [
|
|
{
|
|
"cell_type": "markdown",
|
|
"id": "829a3994",
|
|
"metadata": {},
|
|
"source": [
|
|
"# [Powerful Digit Counts](https://projecteuler.net/problem=63)\n",
|
|
"\n",
|
|
"This problem can be solved with a calculator.\n",
|
|
"\n",
|
|
"For $x^n$ to have $n$ digits, the following inequality must hold:\n",
|
|
"$$10^{n-1} \\leq x^n < 10^n$$\n",
|
|
"If we solve for $x$, we get\n",
|
|
"$$10^\\frac{n-1}{n} \\leq x < 10$$\n",
|
|
"In other words, if $10^\\frac{n-1}{n} \\leq x < 10$ for some $x$, then $x^n$ will have $n$ digits. Therefore, the number of $n$ digit numbers that are also $n$th powers is simply the number of integers between $10^\\frac{n-1}{n}$ and 10. This can be computed as\n",
|
|
"$$\\lfloor 10 - 10^\\frac{n-1}{n} \\rfloor$$\n",
|
|
"At $n=22$, the lower bound is greater than 9, so we only need to consider values between $n=1$ and $n=21$.\n",
|
|
"\n",
|
|
"Evaluating this expression for $n=1,2,3,\\ldots,21$ and summing, we get\n",
|
|
"$$9 + 6 + 5 + 4 + 3 + 3 + 2 + 2 + 2 + 2 + 1 \\times 11 = 49$$\n",
|
|
"\n",
|
|
"## Relevant sequences\n",
|
|
"* Numbers with $k$ digits that are also $k$th powers: [A132722](https://oeis.org/A132722)\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
|
|
}
|