196 lines
4.9 KiB
Plaintext
196 lines
4.9 KiB
Plaintext
{
|
|
"cells": [
|
|
{
|
|
"cell_type": "markdown",
|
|
"id": "438be743",
|
|
"metadata": {},
|
|
"source": [
|
|
"# [Prime Digit Replacements](https://projecteuler.net/problem=51)\n",
|
|
"\n",
|
|
"We'll write a couple of simple functions to build up to the solution. First, a function to take a number and replace given digit places in the number with the same digit:"
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "code",
|
|
"execution_count": 1,
|
|
"id": "7dede7eb",
|
|
"metadata": {},
|
|
"outputs": [],
|
|
"source": [
|
|
"def replace(n, places, d):\n",
|
|
" digits = n.digits()\n",
|
|
" for i in places:\n",
|
|
" digits[i] = d\n",
|
|
"\n",
|
|
" q = ZZ(digits, 10)\n",
|
|
" return q"
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "markdown",
|
|
"id": "1bc82c3a",
|
|
"metadata": {},
|
|
"source": [
|
|
"Next, a function to replace once with every digit 0 to 9 and return the set of every resulting prime:"
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "code",
|
|
"execution_count": 2,
|
|
"id": "8b2de46d",
|
|
"metadata": {},
|
|
"outputs": [],
|
|
"source": [
|
|
"def prime_replacement_family(n, places):\n",
|
|
" family = set()\n",
|
|
" for d in range(0, 10):\n",
|
|
" p = replace(n, places, d)\n",
|
|
" if is_prime(p) and n.ndigits() == p.ndigits():\n",
|
|
" family.add(p)\n",
|
|
" \n",
|
|
" return family"
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "markdown",
|
|
"id": "ecad9b11",
|
|
"metadata": {},
|
|
"source": [
|
|
"And finally, a function to iterate over every possible combination of digit places and return any resulting prime replacement family that's the desired length. The `places_same_digit` function lets us skip any combination of digit places where those places aren't the same digit in the original number. For example, we don't want to try replacing digits 1 and 4 of 192317, since those digits are different and the resulting prime family wouldn't include 192317."
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "code",
|
|
"execution_count": 3,
|
|
"id": "99e9ee7e",
|
|
"metadata": {},
|
|
"outputs": [],
|
|
"source": [
|
|
"from itertools import combinations\n",
|
|
"\n",
|
|
"def places_same_digit(p, places):\n",
|
|
" digits = p.digits()\n",
|
|
" i = places[0]\n",
|
|
" for j in places:\n",
|
|
" if digits[i] != digits[j]:\n",
|
|
" return False\n",
|
|
" \n",
|
|
" return True\n",
|
|
"\n",
|
|
"\n",
|
|
"def search(p, n):\n",
|
|
" ndigits = p.ndigits()\n",
|
|
" for k in range(1, ndigits):\n",
|
|
" for places in combinations(range(0, ndigits), k):\n",
|
|
" if not places_same_digit(p, places):\n",
|
|
" continue\n",
|
|
" \n",
|
|
" f = prime_replacement_family(p, places)\n",
|
|
" if len(f) == n:\n",
|
|
" return f\n",
|
|
" \n",
|
|
" return None"
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "markdown",
|
|
"id": "99878911",
|
|
"metadata": {},
|
|
"source": [
|
|
"There are some optimizations that can be made for the specific problem of finding an eight prime family to reduce the search space (used by many in the problem thread), but writing it this way makes it more general."
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "code",
|
|
"execution_count": 4,
|
|
"id": "08f9eaab",
|
|
"metadata": {},
|
|
"outputs": [
|
|
{
|
|
"data": {
|
|
"text/plain": [
|
|
"{121313, 222323, 323333, 424343, 525353, 626363, 828383, 929393}"
|
|
]
|
|
},
|
|
"execution_count": 4,
|
|
"metadata": {},
|
|
"output_type": "execute_result"
|
|
}
|
|
],
|
|
"source": [
|
|
"from itertools import count\n",
|
|
"\n",
|
|
"for p in count(2):\n",
|
|
" if not is_prime(p):\n",
|
|
" continue\n",
|
|
" \n",
|
|
" f = search(p, 8)\n",
|
|
" if f is not None:\n",
|
|
" break\n",
|
|
" \n",
|
|
"f"
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "markdown",
|
|
"id": "b44779a0",
|
|
"metadata": {},
|
|
"source": [
|
|
"Our answer is the smallest value in this family."
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "code",
|
|
"execution_count": 5,
|
|
"id": "90ac02d3",
|
|
"metadata": {},
|
|
"outputs": [
|
|
{
|
|
"data": {
|
|
"text/plain": [
|
|
"121313"
|
|
]
|
|
},
|
|
"execution_count": 5,
|
|
"metadata": {},
|
|
"output_type": "execute_result"
|
|
}
|
|
],
|
|
"source": [
|
|
"min(f)"
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "markdown",
|
|
"id": "8cc3e0f4",
|
|
"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
|
|
}
|