255 lines
6.1 KiB
Plaintext
255 lines
6.1 KiB
Plaintext
{
|
|
"cells": [
|
|
{
|
|
"cell_type": "markdown",
|
|
"id": "6fcde6bd",
|
|
"metadata": {},
|
|
"source": [
|
|
"# [Truncatable Primes](https://projecteuler.net/problem=37)\n",
|
|
"\n",
|
|
"Apparently another term for these sorts of numbers is a [two-sided prime](https://en.wikipedia.org/wiki/Truncatable_prime).\n",
|
|
"\n",
|
|
"In case you're curious how we know there's only eleven of these primes (not including 2, 3, 5, or 7), this solution will outline it.\n",
|
|
"\n",
|
|
"We start by generating all the right-truncatable primes - the two-sided primes are necessarily a subset of these. If we know a number $n$ is *not* a right-truncatable prime, we know any number with $n$ as a prefix is *also* not a right-truncatable prime. This means we can start by looking at one-digit primes (2, 3, 5, and 7) and for each, try appending each of 1, 3, 7, and 9 and see which, if any, are also prime (appending any other digit would clearly result in a number divisible by 2 or 5). If we find another prime, we'll want to repeat the process of appending 1, 3, 7, or 9 to see if we can find more right-truncatable primes. We use a [depth-first search](https://en.wikipedia.org/wiki/Depth-first_search) for this."
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "code",
|
|
"execution_count": 1,
|
|
"id": "fecd8e1a",
|
|
"metadata": {},
|
|
"outputs": [
|
|
{
|
|
"data": {
|
|
"text/plain": [
|
|
"{23,\n",
|
|
" 29,\n",
|
|
" 31,\n",
|
|
" 37,\n",
|
|
" 53,\n",
|
|
" 59,\n",
|
|
" 71,\n",
|
|
" 73,\n",
|
|
" 79,\n",
|
|
" 233,\n",
|
|
" 239,\n",
|
|
" 293,\n",
|
|
" 311,\n",
|
|
" 313,\n",
|
|
" 317,\n",
|
|
" 373,\n",
|
|
" 379,\n",
|
|
" 593,\n",
|
|
" 599,\n",
|
|
" 719,\n",
|
|
" 733,\n",
|
|
" 739,\n",
|
|
" 797,\n",
|
|
" 2333,\n",
|
|
" 2339,\n",
|
|
" 2393,\n",
|
|
" 2399,\n",
|
|
" 2939,\n",
|
|
" 3119,\n",
|
|
" 3137,\n",
|
|
" 3733,\n",
|
|
" 3739,\n",
|
|
" 3793,\n",
|
|
" 3797,\n",
|
|
" 5939,\n",
|
|
" 7193,\n",
|
|
" 7331,\n",
|
|
" 7333,\n",
|
|
" 7393,\n",
|
|
" 23333,\n",
|
|
" 23339,\n",
|
|
" 23399,\n",
|
|
" 23993,\n",
|
|
" 29399,\n",
|
|
" 31193,\n",
|
|
" 31379,\n",
|
|
" 37337,\n",
|
|
" 37339,\n",
|
|
" 37397,\n",
|
|
" 59393,\n",
|
|
" 59399,\n",
|
|
" 71933,\n",
|
|
" 73331,\n",
|
|
" 73939,\n",
|
|
" 233993,\n",
|
|
" 239933,\n",
|
|
" 293999,\n",
|
|
" 373379,\n",
|
|
" 373393,\n",
|
|
" 593933,\n",
|
|
" 593993,\n",
|
|
" 719333,\n",
|
|
" 739391,\n",
|
|
" 739393,\n",
|
|
" 739397,\n",
|
|
" 739399,\n",
|
|
" 2339933,\n",
|
|
" 2399333,\n",
|
|
" 2939999,\n",
|
|
" 3733799,\n",
|
|
" 5939333,\n",
|
|
" 7393913,\n",
|
|
" 7393931,\n",
|
|
" 7393933,\n",
|
|
" 23399339,\n",
|
|
" 29399999,\n",
|
|
" 37337999,\n",
|
|
" 59393339,\n",
|
|
" 73939133}"
|
|
]
|
|
},
|
|
"execution_count": 1,
|
|
"metadata": {},
|
|
"output_type": "execute_result"
|
|
}
|
|
],
|
|
"source": [
|
|
"right_truncatable_primes = set()\n",
|
|
"\n",
|
|
"visited = set()\n",
|
|
"stack = [2, 3, 5, 7]\n",
|
|
"while stack != []:\n",
|
|
" n = stack.pop()\n",
|
|
" if n in visited:\n",
|
|
" continue\n",
|
|
" visited.add(n)\n",
|
|
" \n",
|
|
" for d in (1,3,7,9):\n",
|
|
" m = 10*n + d\n",
|
|
" if is_prime(m):\n",
|
|
" right_truncatable_primes.add(m)\n",
|
|
" stack.append(m)\n",
|
|
"\n",
|
|
"right_truncatable_primes"
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "markdown",
|
|
"id": "95481066",
|
|
"metadata": {},
|
|
"source": [
|
|
"Next, we write a function for checking if a prime is left-truncatable."
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "code",
|
|
"execution_count": 2,
|
|
"id": "6922aa89",
|
|
"metadata": {},
|
|
"outputs": [],
|
|
"source": [
|
|
"from itertools import count\n",
|
|
"\n",
|
|
"def is_left_truncatable_prime(p):\n",
|
|
" for k in count(1):\n",
|
|
" t = p % 10^k\n",
|
|
" if not is_prime(t):\n",
|
|
" return False\n",
|
|
" if t == p:\n",
|
|
" break\n",
|
|
" \n",
|
|
" return True"
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "markdown",
|
|
"id": "f20fe991",
|
|
"metadata": {},
|
|
"source": [
|
|
"Now just check all our right-truncatable primes to see if they are also left-truncatable."
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "code",
|
|
"execution_count": 3,
|
|
"id": "995c5372",
|
|
"metadata": {},
|
|
"outputs": [
|
|
{
|
|
"data": {
|
|
"text/plain": [
|
|
"{23, 37, 53, 73, 313, 317, 373, 797, 3137, 3797, 739397}"
|
|
]
|
|
},
|
|
"execution_count": 3,
|
|
"metadata": {},
|
|
"output_type": "execute_result"
|
|
}
|
|
],
|
|
"source": [
|
|
"two_sided_primes = {p for p in right_truncatable_primes if is_left_truncatable_prime(p)}\n",
|
|
"two_sided_primes"
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "markdown",
|
|
"id": "97f60cbd",
|
|
"metadata": {},
|
|
"source": [
|
|
"Sure enough, only eleven two-sided primes."
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "code",
|
|
"execution_count": 4,
|
|
"id": "3851ffee",
|
|
"metadata": {},
|
|
"outputs": [
|
|
{
|
|
"data": {
|
|
"text/plain": [
|
|
"748317"
|
|
]
|
|
},
|
|
"execution_count": 4,
|
|
"metadata": {},
|
|
"output_type": "execute_result"
|
|
}
|
|
],
|
|
"source": [
|
|
"sum(two_sided_primes)"
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "markdown",
|
|
"id": "8f55a757",
|
|
"metadata": {},
|
|
"source": [
|
|
"## Relevant sequences\n",
|
|
"* Two-sided primes: [A020994](https://oeis.org/A020994)\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
|
|
}
|