euler-050-consecutive-prime-sum-20130815.ipynb

{
 "metadata": {
  "name": "euler-050-consecutive-prime-sum-20130815"
 },
 "nbformat": 3,
 "nbformat_minor": 0,
 "worksheets": [
  {
   "cells": [
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "The prime 41, can be written as the sum of six consecutive primes: \n",
      "\n",
      "> 41 = 2 + 3 + 5 + 7 + 11 + 13 \n",
      "\n",
      "This is the longest sum of consecutive primes that adds to a prime below one-hundred. \n",
      "\n",
      "The longest sum of consecutive primes below one-thousand that adds to a prime, contains 21 terms, and is equal to 953. \n",
      "\n",
      "Which prime, below one-million, can be written as the sum of the most consecutive primes?"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "from euler import gen_lt, gen_prime"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 1
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def foo(n):\n",
      "    limit = 10 ** n\n",
      "    primes = list(gen_lt(gen_prime(), limit))\n",
      "    ps = set(primes)\n",
      "    delta_longest = 0\n",
      "    for i in range(len(primes)):\n",
      "        total = sum(primes[i:i+delta_longest])\n",
      "        for j in range(i + delta_longest, len(primes)):\n",
      "            total += primes[j]\n",
      "            if total > limit:\n",
      "                if j - i <= delta_longest:\n",
      "                    return sum(primes[i_longest:i_longest+delta_longest+1])\n",
      "                break\n",
      "            if total in ps and j - i > delta_longest:\n",
      "                delta_longest = j - i\n",
      "                i_longest = i\n",
      "    print i_longest, delta_longest+1, primes[i_longest:i_longest+delta_longest+1], sum(primes[i_longest:i_longest+delta_longest+1])\n",
      "    # print delta_longest+1\n",
      "    return sum(primes[i_longest:i_longest+delta_longest+1])\n"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 2
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "n = 2\n",
      "%timeit foo(n)\n",
      "foo(n)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "10000 loops, best of 3: 30.7 us per loop\n"
       ]
      },
      {
       "output_type": "pyout",
       "prompt_number": 3,
       "text": [
        "41"
       ]
      }
     ],
     "prompt_number": 3
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "n = 3\n",
      "%timeit foo(n)\n",
      "foo(n)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "10000 loops, best of 3: 100 us per loop\n"
       ]
      },
      {
       "output_type": "pyout",
       "prompt_number": 4,
       "text": [
        "953"
       ]
      }
     ],
     "prompt_number": 4
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "n = 6\n",
      "%timeit foo(n)\n",
      "foo(n)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "1 loops, best of 3: 41.3 ms per loop\n"
       ]
      },
      {
       "output_type": "pyout",
       "prompt_number": 5,
       "text": [
        "997651"
       ]
      }
     ],
     "prompt_number": 5
    }
   ],
   "metadata": {}
  }
 ]
}