252 lines
6.2 KiB
Plaintext
252 lines
6.2 KiB
Plaintext
{
|
|
"cells": [
|
|
{
|
|
"cell_type": "markdown",
|
|
"id": "deed1692",
|
|
"metadata": {},
|
|
"source": [
|
|
"# [Prime Pair Sets](https://projecteuler.net/problem=60)\n",
|
|
"\n",
|
|
"There's a very elegant way to approach this problem with [graph theory](https://en.wikipedia.org/wiki/Graph_theory). First, we'll want to generate some primes (we'll start with primes below 10000 as a guess, and later determine a more precise bound)."
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "code",
|
|
"execution_count": 1,
|
|
"id": "92815331",
|
|
"metadata": {},
|
|
"outputs": [],
|
|
"source": [
|
|
"primes = prime_range(10000)"
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "markdown",
|
|
"id": "014d5611",
|
|
"metadata": {},
|
|
"source": [
|
|
"Then, we'll construct a graph where each vertex represents a prime, and there's an edge between any two primes that can be concatenated either way to create another prime. For example, referring to the the problem statement, each pair of 3, 7, 109, and 673 would have an edge between them."
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "code",
|
|
"execution_count": 2,
|
|
"id": "838ccfa7",
|
|
"metadata": {},
|
|
"outputs": [],
|
|
"source": [
|
|
"from itertools import combinations\n",
|
|
"\n",
|
|
"def prime_pair_graph(primes):\n",
|
|
" G = Graph()\n",
|
|
" for (u, v) in combinations(primes, 2):\n",
|
|
" if is_prime(int(f\"{u}{v}\")) and is_prime(int(f\"{v}{u}\")):\n",
|
|
" G.add_edge((u, v))\n",
|
|
" \n",
|
|
" return G"
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "code",
|
|
"execution_count": 3,
|
|
"id": "8a4087f6",
|
|
"metadata": {},
|
|
"outputs": [
|
|
{
|
|
"data": {
|
|
"text/plain": [
|
|
"Graph on 1227 vertices (use the .plot() method to plot)"
|
|
]
|
|
},
|
|
"execution_count": 3,
|
|
"metadata": {},
|
|
"output_type": "execute_result"
|
|
}
|
|
],
|
|
"source": [
|
|
"G = prime_pair_graph(primes)\n",
|
|
"G"
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "markdown",
|
|
"id": "ab8e7abc",
|
|
"metadata": {},
|
|
"source": [
|
|
"In the language of graph theory, the problem is to find a [5-clique](https://w.wiki/EoNJ) in this graph where the sum of the vertices is minimized. [The problem of finding cliques](https://en.wikipedia.org/wiki/Clique_problem) is hard (i.e. NP-complete) in general, but we can find 5-cliques in our graph in polynomial time by simply iterating through every combination of 5 vertices in the graph and seeing if those vertices form a complete subgraph.\n",
|
|
"\n",
|
|
"Alternatively, SageMath includes an algorithm for finding cliques."
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "code",
|
|
"execution_count": 4,
|
|
"id": "89e26388",
|
|
"metadata": {},
|
|
"outputs": [
|
|
{
|
|
"data": {
|
|
"text/plain": [
|
|
"[[13, 5197, 5701, 6733, 8389]]"
|
|
]
|
|
},
|
|
"execution_count": 4,
|
|
"metadata": {},
|
|
"output_type": "execute_result"
|
|
}
|
|
],
|
|
"source": [
|
|
"cliques = list(G.all_cliques(5, 5))\n",
|
|
"cliques"
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "markdown",
|
|
"id": "e2f81c45",
|
|
"metadata": {},
|
|
"source": [
|
|
"It turns out that there's only one 5-clique in this graph."
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "code",
|
|
"execution_count": 5,
|
|
"id": "81c49dec",
|
|
"metadata": {},
|
|
"outputs": [
|
|
{
|
|
"data": {
|
|
"text/plain": [
|
|
"26033"
|
|
]
|
|
},
|
|
"execution_count": 5,
|
|
"metadata": {},
|
|
"output_type": "execute_result"
|
|
}
|
|
],
|
|
"source": [
|
|
"sum(cliques[0])"
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "markdown",
|
|
"id": "c188a9df",
|
|
"metadata": {},
|
|
"source": [
|
|
"This ends up being the answer!\n",
|
|
"\n",
|
|
"Now, although this is clearly the minimum sum of any 5-clique in the primes below 10000, how do we know it's the minimum sum across *all* the primes? Well, to confirm, we can construct the same graph, but this time include primes up to 26034. We don't need to include any primes beyond this, because if a 5-clique existed that included a prime larger than 26034, that 5-clique's sum would have to be greater than 26033, so it can't be a minimal sum. Therefore, the minimal sum must exist somewhere in the primes below 26034."
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "code",
|
|
"execution_count": 6,
|
|
"id": "c9739298",
|
|
"metadata": {},
|
|
"outputs": [
|
|
{
|
|
"data": {
|
|
"text/plain": [
|
|
"Graph on 2862 vertices (use the .plot() method to plot)"
|
|
]
|
|
},
|
|
"execution_count": 6,
|
|
"metadata": {},
|
|
"output_type": "execute_result"
|
|
}
|
|
],
|
|
"source": [
|
|
"primes = prime_range(26034)\n",
|
|
"G = prime_pair_graph(primes)\n",
|
|
"G"
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "code",
|
|
"execution_count": 7,
|
|
"id": "d8a27ddd",
|
|
"metadata": {},
|
|
"outputs": [
|
|
{
|
|
"data": {
|
|
"text/plain": [
|
|
"[[467, 941, 25253, 19793, 2099],\n",
|
|
" [13, 5197, 5701, 6733, 8389],\n",
|
|
" [1237, 2341, 12409, 18433, 7]]"
|
|
]
|
|
},
|
|
"execution_count": 7,
|
|
"metadata": {},
|
|
"output_type": "execute_result"
|
|
}
|
|
],
|
|
"source": [
|
|
"cliques = list(G.all_cliques(5,5))\n",
|
|
"cliques"
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "markdown",
|
|
"id": "34eda2aa",
|
|
"metadata": {},
|
|
"source": [
|
|
"We've found two more 5-cliques, but the one we found before has the minimal sum."
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "code",
|
|
"execution_count": 8,
|
|
"id": "43e040f3",
|
|
"metadata": {},
|
|
"outputs": [
|
|
{
|
|
"data": {
|
|
"text/plain": [
|
|
"[13, 5197, 5701, 6733, 8389]"
|
|
]
|
|
},
|
|
"execution_count": 8,
|
|
"metadata": {},
|
|
"output_type": "execute_result"
|
|
}
|
|
],
|
|
"source": [
|
|
"min_clique = min(cliques, key=sum)\n",
|
|
"min_clique"
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "markdown",
|
|
"id": "07fc52d8",
|
|
"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
|
|
}
|