149 lines
4.6 KiB
Plaintext
149 lines
4.6 KiB
Plaintext
{
|
|
"cells": [
|
|
{
|
|
"cell_type": "markdown",
|
|
"id": "ec776294",
|
|
"metadata": {},
|
|
"source": [
|
|
"# [Totient Permutation](https://projecteuler.net/problem=70)\n",
|
|
"\n",
|
|
"SageMath's implementation of $\\phi(n)$ is fast enough that you could brute force this if you wanted, but if we're clever, we can solve more quickly.\n",
|
|
"\n",
|
|
"We'll write a simple function for determining if two numbers are digit permutations of each other."
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "code",
|
|
"execution_count": 1,
|
|
"id": "e6757165",
|
|
"metadata": {},
|
|
"outputs": [],
|
|
"source": [
|
|
"def is_permutation_pair(a, b):\n",
|
|
" s, t = str(a), str(b)\n",
|
|
" return sorted(s) == sorted(t)"
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "markdown",
|
|
"id": "bdeb8c77",
|
|
"metadata": {},
|
|
"source": [
|
|
"As in [problem 69](https://projecteuler.net/problem=69),\n",
|
|
"$$\\phi(n) = n\\prod_{p | n} \\left(1 - \\frac{1}{p}\\right)$$\n",
|
|
"\n",
|
|
"We can calculate the totients of the numbers up to $10^7$ using a very similar approach to the [sieve of Eratosthenes](https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes) for generating prime numbers (see [problem 10](https://projecteuler.net/problem=10)). Iterating over values of $n$, if `totients[n] == n - 1`, then $n$ is prime, and we'll update all its multiples using the above formula."
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "code",
|
|
"execution_count": 2,
|
|
"id": "54065139",
|
|
"metadata": {},
|
|
"outputs": [],
|
|
"source": [
|
|
"def totient_range(limit):\n",
|
|
" totients = [n - 1 for n in range(0, limit)]\n",
|
|
" totients[0] = 0\n",
|
|
" totients[1] = 1\n",
|
|
" \n",
|
|
" for n in range(0, limit):\n",
|
|
" yield totients[n]\n",
|
|
" if n == 0 or n == 1 or totients[n] != n - 1:\n",
|
|
" continue\n",
|
|
"\n",
|
|
" for k in range(2 * n, limit, n):\n",
|
|
" totients[k] -= totients[k] // n"
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "markdown",
|
|
"id": "45a80c4b",
|
|
"metadata": {},
|
|
"source": [
|
|
"$n-1$ can't be a permutation of $n$, so our solution won't be prime. If $n$ is composite, then we'll check if $n/\\phi(n)$ is small and if $\\phi(n)$ is a permutation of $n$, keeping track of the best answer so far."
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "code",
|
|
"execution_count": 3,
|
|
"id": "60741588",
|
|
"metadata": {},
|
|
"outputs": [],
|
|
"source": [
|
|
"limit = 10^7\n",
|
|
"\n",
|
|
"answer = None\n",
|
|
"ratio = float('inf')\n",
|
|
"\n",
|
|
"for (n, totient) in enumerate(totient_range(limit)):\n",
|
|
" if n == 0 or n == 1 or totient == n - 1:\n",
|
|
" continue\n",
|
|
" \n",
|
|
" r = n / totient\n",
|
|
" if r < ratio and is_permutation_pair(n, totient):\n",
|
|
" ratio = r\n",
|
|
" answer = n"
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "code",
|
|
"execution_count": 4,
|
|
"id": "d4819aa5",
|
|
"metadata": {},
|
|
"outputs": [
|
|
{
|
|
"data": {
|
|
"text/plain": [
|
|
"8319823"
|
|
]
|
|
},
|
|
"execution_count": 4,
|
|
"metadata": {},
|
|
"output_type": "execute_result"
|
|
}
|
|
],
|
|
"source": [
|
|
"answer"
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "markdown",
|
|
"id": "40cf1e01",
|
|
"metadata": {},
|
|
"source": [
|
|
"Note: lots of people in the problem thread make the assumption that the answer must be a [semiprime](https://en.wikipedia.org/wiki/Semiprime). However, Steendor points out that for certain upper bounds, this assumption does not hold. For instance, $2817 = 3^2 \\times 313$ and $\\phi(2817) = 1872$, and 2817/1872 is the lowest ratio until 2991. 2817 may be an exception rather than the norm (all the other numbers in A102018 up to $10^8$ are semiprimes); nevertheless, this solution avoids making the assumption.\n",
|
|
"\n",
|
|
"## Relevant sequences\n",
|
|
"* All numbers $n$ such that $\\phi(n)$ is a digit permutation: [A115921](https://oeis.org/A115921)\n",
|
|
"* Subsequence of A115921 such that $n/\\phi(n)$ is a record low: [A102018](https://oeis.org/A102018)\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
|
|
}
|