euler-044-pentagon-numbers-kristian-20130610.ipynb

{
 "metadata": {
  "name": "euler-044-pentagon-numbers-kristian-20130610"
 },
 "nbformat": 3,
 "nbformat_minor": 0,
 "worksheets": [
  {
   "cells": [
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "import math\n",
      "from itertools import count\n",
      "from time import clock\n",
      "\n",
      "sqrt = math.sqrt\n",
      "\n",
      "def pe44(prove=False, printit=0):\n",
      "    \"\"\" D, a, b, S are pentagon numbers\n",
      "        a + b  = S \n",
      "        |b- a| = D \n",
      "        phase 1: search for a solution (0.2 s) -> min_D\n",
      "                 given D, b -> test a = b - D and S = 2 * b - D\n",
      "                 a < b < S, D < b < S in the method below\n",
      "                 a may be larger or smaller than D, but is positive\n",
      "                 As a < b, we can test if a in pentagonals.\n",
      "                 S is larger than b and we have to use is_pent\n",
      "        If prove is True then phase 2 proves that there is no solution with\n",
      "          a D lower than min_D:\n",
      "            phase 2: try to find a solution with a lower D\n",
      "            if D is smaller than b - b_prev it can be removed from Ds\n",
      "            search stops if D < b - b_prev for all D in Ds (Ds is empty)\n",
      "            total time 250 sec. In C this should be only a few secs.\n",
      "    \"\"\"\n",
      "    t0 = clock()\n",
      "    def pent(n): return n * (3 * n - 1) // 2\n",
      "    def is_pent(N): return ((sqrt(24 * N + 1) + 1) / 6.0).is_integer()\n",
      "    ps = set() # keeps pentagonal numbers smaller than b\n",
      "    Ds = []    # keeps the list of possible D\n",
      "    min_D = None\n",
      "    b = 0\n",
      "    # for b_index in xrange(1, 2000000): \n",
      "    for b_index in count(1): \n",
      "        b_prev = b\n",
      "        b = pent(b_index)\n",
      "        delta = b - b_prev \n",
      "        # any D smaller than delta can be removed, as a=b-D cannot be pentagonal\n",
      "        if Ds and Ds[0] < delta: \n",
      "            Ds.pop(0)\n",
      "        if printit and b_index % printit == 0:\n",
      "            print b_index, clock() - t0, len(Ds)\n",
      "        # if min_D is found and no Ds we can stop\n",
      "        if min_D and not (prove and Ds):\n",
      "            break\n",
      "        for D in Ds:\n",
      "            if b - D in ps and is_pent(2 * b - D): \n",
      "                min_D = D\n",
      "                while Ds[-1] >= min_D: # from now on only check D < min_D\n",
      "                    Ds.pop()\n",
      "                break\n",
      "        ps.add(b)\n",
      "        if not min_D: \n",
      "            Ds.append(b)\n",
      "    return min_D"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 14
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "pe44(prove=False, printit=100000)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "pyout",
       "prompt_number": 15,
       "text": [
        "5482660"
       ]
      }
     ],
     "prompt_number": 15
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "pe44(prove=True, printit=100000)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "100000 42.87 1464\n",
        "200000"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        " 93.46 1279\n",
        "300000"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        " 143.68 1137\n",
        "400000"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        " 190.73 1017\n",
        "500000"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        " 233.38 911\n",
        "600000"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        " 273.39 816\n",
        "700000"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        " 311.4 728\n",
        "800000"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        " 342.1 646\n",
        "900000"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        " 369.92 570\n",
        "1000000"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        " 394.94 497\n",
        "1100000"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        " 417.16 428\n",
        "1200000"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        " 436.61 362\n",
        "1300000"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        " 453.32 299\n",
        "1400000"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        " 467.48 238\n",
        "1500000"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        " 477.11 179\n",
        "1600000"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        " 484.21 122\n",
        "1700000"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        " 488.82 67\n",
        "1800000"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        " 490.94 14\n"
       ]
      },
      {
       "output_type": "pyout",
       "prompt_number": 16,
       "text": [
        "5482660"
       ]
      }
     ],
     "prompt_number": 16
    }
   ],
   "metadata": {}
  }
 ]
}