eulerbooks/notebooks/problem0050.ipynb

{
 "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
}