163 lines
4.3 KiB
Plaintext
163 lines
4.3 KiB
Plaintext
{
|
|
"cells": [
|
|
{
|
|
"cell_type": "markdown",
|
|
"id": "1c5feb53",
|
|
"metadata": {},
|
|
"source": [
|
|
"# [Consecutive Prime Sum](https://projecteuler.net/problem=50)\n",
|
|
"\n",
|
|
"Another way to phrase this problem is that we're looking for the longest subsequence of primes $p_i, p_{i+1}, p_{i+2}, \\ldots, p_{j-1}$ that sum to a prime below 1000000.\n",
|
|
"\n",
|
|
"If we let $p_0 = 2$, then $p_{41537} = 499979$, $p_{41538} = 500009$, and $p_{41539} = 500029$. Since $p_{41538} + p_{41539} > 1000000$, there's no point in checking any sum that's composed with a prime greater than 500010."
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "code",
|
|
"execution_count": 1,
|
|
"id": "8a9f568e",
|
|
"metadata": {},
|
|
"outputs": [],
|
|
"source": [
|
|
"primes = prime_range(500010)"
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "markdown",
|
|
"id": "c98ea076",
|
|
"metadata": {},
|
|
"source": [
|
|
"Now here's an algorithm for finding the longest consecutive prime sum. The clever bit about this algorithm is that it avoids repeatedly recalculating large sums - instead, we slide through the list of primes, growing and shrinking a running total. (As much as I'd like to take credit for this algorithm, the steps were outlined by the user tzaman on the problem thread.)"
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "code",
|
|
"execution_count": 2,
|
|
"id": "c7014e59",
|
|
"metadata": {},
|
|
"outputs": [],
|
|
"source": [
|
|
"def longest_consecutive_prime_sum(primes):\n",
|
|
" total = 0\n",
|
|
" end = 0\n",
|
|
" best = (0, 0)\n",
|
|
" for begin in range(0, len(primes)):\n",
|
|
" # grow the sum until it's larger than 1000000\n",
|
|
" for maximum in range(end, len(primes)):\n",
|
|
" total += primes[maximum]\n",
|
|
" if total >= 1000000:\n",
|
|
" break\n",
|
|
"\n",
|
|
" # shrink the sum until it's prime (or shorter than our best sum so far)\n",
|
|
" for end in reversed(range(begin, maximum + 1)):\n",
|
|
" total -= primes[end]\n",
|
|
" \n",
|
|
" if end - begin <= best[1] - best[0]:\n",
|
|
" break\n",
|
|
"\n",
|
|
" if is_prime(total):\n",
|
|
" best = (begin, end)\n",
|
|
" break\n",
|
|
"\n",
|
|
" # try again, starting one prime after our current start point\n",
|
|
" total -= primes[begin]\n",
|
|
" \n",
|
|
" return best"
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "markdown",
|
|
"id": "f274e457",
|
|
"metadata": {},
|
|
"source": [
|
|
"The algorithm returns the indices of the slice that's the longest sum."
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "code",
|
|
"execution_count": 3,
|
|
"id": "472dfc59",
|
|
"metadata": {},
|
|
"outputs": [
|
|
{
|
|
"data": {
|
|
"text/plain": [
|
|
"(3, 546)"
|
|
]
|
|
},
|
|
"execution_count": 3,
|
|
"metadata": {},
|
|
"output_type": "execute_result"
|
|
}
|
|
],
|
|
"source": [
|
|
"i, j = longest_consecutive_prime_sum(primes)\n",
|
|
"i, j"
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "markdown",
|
|
"id": "c495528f",
|
|
"metadata": {},
|
|
"source": [
|
|
"The longest prime sum starts at $p_3$ and ends with $p_{545}$."
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "code",
|
|
"execution_count": 4,
|
|
"id": "325f7bb3",
|
|
"metadata": {},
|
|
"outputs": [
|
|
{
|
|
"data": {
|
|
"text/plain": [
|
|
"997651"
|
|
]
|
|
},
|
|
"execution_count": 4,
|
|
"metadata": {},
|
|
"output_type": "execute_result"
|
|
}
|
|
],
|
|
"source": [
|
|
"sum(primes[i:j])"
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "markdown",
|
|
"id": "16a496a9",
|
|
"metadata": {},
|
|
"source": [
|
|
"## Relevant sequences\n",
|
|
"* Primes expressible as the sum of (at least two) consecutive primes in at least 1 way: [A067377](https://oeis.org/A067377)\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
|
|
}
|