{
 "metadata": {
  "name": "",
  "signature": "sha256:abfea37f08512ec7d0447a7e1b6b101959312f477e28a1cb8c2901a14bcf6900"
 },
 "nbformat": 3,
 "nbformat_minor": 0,
 "worksheets": [
  {
   "cells": [
    {
     "cell_type": "heading",
     "level": 2,
     "metadata": {},
     "source": [
      "Problem 5"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.\n",
      "\n",
      "What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?\n",
      "\n",
      "---"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "This is an interesting problem! \n",
      "\n",
      "First thing's first, we can establish that the largest positive number that meets the condition is $1\u00d72\u00d73..\u00d720$ or simply $20!$\n",
      "We can work our way down by repeatedly dividing this upper boundary number by any number in the range [1,20] and seeing if it's an even division. \n",
      "\n",
      "This approach results in a runtime complexity of O(log(n!)), better known as O(n log n)\n"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "factors = 20\n",
      "\n",
      "upper = math.factorial(factors)\n",
      "divisors = range(2, factors+1)\n",
      "current = upper\n",
      "\n",
      "#repeatedly attempt to divide current number by prime factors ordered \n",
      "#from largest to smallest as long as the result has a remainder of 0\n",
      "while True:\n",
      "    found = False\n",
      "    for p in reversed(divisors):\n",
      "        c = current / p\n",
      "        if c % p == 0:\n",
      "            found = True\n",
      "            current = c\n",
      "            break\n",
      "            \n",
      "    if not found:\n",
      "       break\n",
      "        \n",
      "    print 'divided by', p, 'got', current"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "divided by 20 got 121645100408832000\n",
        "divided by 20 got 6082255020441600\n",
        "divided by 20 got 304112751022080\n",
        "divided by 18 got 16895152834560\n",
        "divided by 18 got 938619601920\n",
        "divided by 18 got 52145533440\n",
        "divided by 16 got 3259095840\n",
        "divided by 14 got 232792560\n",
        "divided by 12 got 19399380\n",
        "divided by 2 got 9699690\n"
       ]
      }
     ],
     "prompt_number": 16
    },
    {
     "cell_type": "heading",
     "level": 2,
     "metadata": {},
     "source": [
      "Problem 6"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "The sum of the squares of the first ten natural numbers is, 1<sup>2</sup> + 2<sup>2</sup> + ... + 10<sup>2</sup> = 385\n",
      "\n",
      "The square of the sum of the first ten natural numbers is, (1 + 2 + ... + 10)<sup>2</sup> = 552 = 3025\n",
      "\n",
      "Hence the difference between the sum of the squares of the first ten natural numbers and the square of the sum is 3025 \u2212 385 = 2640.\n",
      "\n",
      "Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.\n",
      "\n",
      "---"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "**Method 1: brute force**\n",
      "\n",
      "Complexity: O(N)"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def squareDiff(x):\n",
      "    s = range(1, x+1)\n",
      "    sumSquares = sum([x*x for x in s])\n",
      "    squareSum = math.pow(sum(s),2)\n",
      "    diff = squareSum - sumSquares\n",
      "    return diff\n",
      "\n",
      "squareDiff(100)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 10,
       "text": [
        "25164150.0"
       ]
      }
     ],
     "prompt_number": 10
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Easy enough, however it's well known that the sum of a series of natural numbers up to n can be calculated as  $\\frac{n(n+1)}{2}$\n",
      "\n",
      "Is it possible that the sum of a series of natural numbers squared up to n can be calculated in constant time as well? I didn't know the answer and cheated by using a genetic algorithm to attempt to fit an equation to match *sumSquares* for the first 140 inputs. \n",
      "\n",
      "Amazingly, it came back with a polynomial that had 0 residual error: $\\frac{1}{6}n + \\frac{1}{2}n^2 + \\frac{1}{3}n^3$\n",
      "\n",
      "Let's plot this polynomial to double check"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "brute = lambda n: sum([x*x for x in xrange(1,n+1)])\n",
      "poly = lambda n: round(1./6 * n + 1./2 * pow(n, 2) + 1./3 * pow(n, 3))\n",
      "\n",
      "x = np.array(range(1,2200))\n",
      "brute_y = np.array([brute(t) for t in x])\n",
      "poly_y = np.array([poly(t) for t in x])\n",
      "\n",
      "plt.plot(x, brute_y, label='Brute Force', color='blue')\n",
      "plt.plot(x, poly_y, label='Polynomial', color='red')\n",
      "plt.legend()\n",
      "\n",
      "print 'max error:', max(brute_y - poly_y)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "max error: 1431655765.0\n"
       ]
      },
      {
       "metadata": {},
       "output_type": "display_data",
       "png": "iVBORw0KGgoAAAANSUhEUgAAAXkAAAEGCAYAAACAd+UpAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAIABJREFUeJzt3Xl8VNXdx/HPSUggEAiBsMgSIgLuiIoLm0bqglZQRFSQ\nTaxVq2DVVgrUh1i16qPWtT5YBREsSEUFAVEBiWBRCQICEhCQsC9GMCSQBJKc5487hARDCJn9zvf9\nes0rM3du7v3NyeQ3Z8459xxjrUVERNwpKtgBiIiI/yjJi4i4mJK8iIiLKcmLiLiYkryIiIspyYuI\nuJjfk7wxZrwxZrcxZlUV9m1ljJlvjPnOGLPAGNPc3/GJiLhZIGrybwE9qrjvc8AEa+15wN+Ap/wW\nlYhIBPB7krfWLgL2ld1mjDnNGDPHGLPUGLPQGHO656kzgc8999OBG/wdn4iImwWrTf5fwDBrbUfg\nz8Brnu3fAX0893sDdY0xiUGIT0TEFWoE+oTGmHigE/CeMebI5ljPzz8BrxpjhgALge1AcaBjFBFx\ni4AneZxvD79Ya88/9glr7U48NXnPh0Efa+3+AMcnIuIaXjXXGGNqGWO+McasMMasMcacsKPUk7Q3\nGWNu9hzDGGPae+43NMYciWkkMM6b+EREIp1XSd5aWwBcYa3tALQHrjDGdC27jzFmCrAYON0Ys9UY\ncwdwO3CnMWYFsBro5dn9CmCtMWYd0Ah40pv4REQinfHVVMPGmNrAF8Bga+0anxxURES84vXoGmNM\nlKdGvhtYoAQvIhI6vE7y1toST3NNC+AyY0yq11GJiIhP+Gx0jbU2xxgzG+iIcyETAG3atLEbN270\n1WlERCLFRmttG28P4u3omiRjTH3P/TjgKmB52X02btyItVY3axkzZkzQYwiVm8pCZaGyqPwGnOZN\nfj7C25r8KcDbnmGPUcAka+1878MSERFf8CrJW2tXARf4KBYREfExzScfQKmpqcEOIWSoLI5SWRyl\nsvA9n42TP+4JjLH+PoeIiNsYY7DWmhPvWblgzF0jIj7UoEED9u3bd+IdJSQlJiayd+9evx1fNXmR\nMOep8QU7DKmm4/39fFWTV5u8iIiLKcmLiLiYkryIiIspyYuIuJiSvIj4TUpKCrVr16Zu3bo0aNCA\n66+/nm3btnl1zKioKH788Uevfj8+Pp66deuWxuVmSvIi4jfGGGbNmkVubi47d+6kSZMmDBs27Lj7\nl5SUVOm43o4mWrlyJbm5ueTm5lZr+GJxcfgsPa0kLyIBUbNmTfr06cOaNUeXnBgyZAj33nsv1113\nHfHx8SxYsIDU1FTGjTu68ueECRPo1q0bAJdddhkA5513HnXr1uW9994DYNasWXTo0IHExES6dOnC\nqlWrTjq+nJwcBg0aROPGjUlJSeHJJ58s/TCZMGECXbp04aGHHiIpKYnHHnuMgoICHn74YVJSUqhf\nvz7dunWjoKAAgK+//prOnTuTmJhIhw4d+OKLL6pXaD6gi6FExK+OJMqDBw8ydepUOnXqVO75KVOm\nMGfOHDp16kRhYSHGGIypeHj4woULiYqKYuXKlbRu3RqA5cuXc+eddzJr1iw6duzIpEmT6NWrF+vW\nrSM2NrbSmMoaNmwYubm5bNq0iezsbK6++mpOOeUUhg4dCsCSJUvo378/e/bs4dChQzz88MNkZmby\n1Vdf0aRJE5YsWUJUVBTbt2/n+uuv55133qFHjx7MmzePPn36sHbtWpKSkqpdjtUWgOkyrYj4z4n+\nx8A3t+po1aqVjY+Pt/Xr17cxMTG2efPmdtWqVaXPDxkyxA4ePLjc76Smptpx48aVPn7rrbds165d\nSx8bY+zGjRtLH99zzz320UcfLXeM008/3X7xxRcVxmSMsfXq1bP169e39evXtw888IAtKiqysbGx\nNjMzs3S/119/3aamppbGkJycXPpccXGxjYuLsytXrvzV8Z9++mk7cODActuuueYa+/bbb1cYz/H+\nfp7tXudg1eRFXC6YF8MaY5gxYwbdu3fHWsv06dO5/PLLyczMpHHjxgC0bNnSq3Ns3ryZiRMn8sor\nr5RuO3z4MDt37jzu7yxfvrz0mwDA7t27OXz4MK1atSrdlpyczPbt20sfl40zOzubgoICTjvt11O+\nb968mffee4+ZM2eWbisqKqJ79+4n/+J8QG3yIhIQxhh69+5NdHQ0X3755XH3q1OnDgcOHCh9vGvX\nrkqPm5yczOjRo9m3b1/pLS8vj1tvvbXKsSUlJRETE0NWVlbpti1bttCiRYty8Zfdv1atWmzYsKHC\neAYOHFguntzcXB555JEqx+NLSvIi4lfW81XCWsuMGTPYt28fZ555ZrnnyurQoQMffPAB+fn5bNiw\noVwnLECTJk0ou6ToXXfdxdixY1myZAnWWg4cOMDs2bPJy8urcozR0dHccsstjB49mry8PDZv3swL\nL7zAgAEDKtw/KiqKoUOH8tBDD7Fz506Ki4v56quvOHToEAMGDGDmzJl89tlnFBcXU1BQQHp6erlv\nBYGkJC8iftWzZ0/q1q1LQkICjz76KBMnTixN8hV1sj744IPExsbSpEkT7rjjDgYMGFBun7S0NAYP\nHkxiYiLTpk3jwgsv5I033uD++++nQYMGtG3blokTJx43nuN16r7yyivUqVOH1q1b061bN26//Xbu\nuOOO48b53HPPce6553LRRRfRsGFDRo4cSUlJCS1atGDGjBn8/e9/p3HjxiQnJ/P8889XeXior2kW\nSpEwp1kow5tmoRQRkWpTkhcRcTEleRERF1OSFxFxMSV5EREXU5IXEXExJXkRERdTkhcRcTEleREJ\nGSkpKcyfPz/YYZRz3XXXMWnSpCrtG4rxaxZKEfGLlJQU9uzZQ3R0NHXq1OHaa6/l1VdfpU6dOsf9\nncrmkg+Wjz/+uMr7hmL8XtXkjTEtjTELjDHfG2NWG2OG+yowEQlvZZf+W7ZsGUuXLuWJJ54IdlgR\nx9vmmsPAg9bas4FLgfuMMWd6H5aIuEmzZs3o0aMHq1ev5qOPPuLss88mMTGRK664grVr1/5q/127\ndlGnTp1y668uW7aMxo0bU1RUxIQJE+jatSt//vOfadCgAa1bt+aTTz4p3XfHjh306tWLhg0b0rZt\nW958883S59LS0ujbty8DBw6kXr16tG/fnvXr1/PUU0/RpEkTWrVqxdy5c0v3L7sc4caNG+nevTtJ\nSUk0atSIAQMGkJOT448i8xmvkry1dpe1doXnfh6QCTTzRWAiEv6OTLy1detW5syZQ926denfvz8v\nv/wy2dnZXHfddfTs2ZOioqJyv9e0aVNSU1P5z3/+U7pt0qRJ9OvXjxo1nFbmJUuWcMYZZ/Dzzz/z\nyCOPcOedd5bue9ttt5GcnMzOnTuZNm0ao0aNYsGCBaXPz5o1i0GDBrFv3z7OP/98rrrqKsD5cHj0\n0Ue5++67S/c9tglm9OjR7Ny5k8zMTLZu3UpaWprvCswffLG8lOcPmQJsBuKP2V7h0lYi4hsn/B8L\n0vp/ZZf+a9Wqlb3vvvvs448/bm+99dbSfUpKSmzz5s1Ll+pLSUmx8+fPt9Za++6779ouXbpYa60t\nKiqyTZs2tRkZGdZaZzm+Nm3alB7nwIED1hhjd+/ebbds2WKjo6NtXl5e6fMjR460Q4YMsdZaO2bM\nGHv11VeXPvfRRx/Z+Ph4W1JSYq21dv/+/dYYY3Nycqy1v16OsKwPP/zQnn/++aWPy8ZfVcf7++Gj\n5f98MrrGGBMPTAMesE6NXkRCha/S/Ek6svTfvn37yMrK4tVXX2XHjh0kJyeX26dly5YVLqhxww03\nsGbNGrKyspg7dy4JCQl07Nix9PmmTZuW3q9duzYAeXl57NixgwYNGpTr4D12Kb8jSw8CxMXFkZSU\nVFpbj4uLKz3WsXbv3s1tt91GixYtSEhIYODAgfz8888nXTaB5PXoGmNMDPA+8I61dnpF+5T9OpOa\nmkpqaqq3pxWRMNSsWTNWrVpV+thay9atW2nevPmv9q1VqxZ9+/blnXfeYe3atQwaNKjK59i7dy95\neXnEx8cDv17Kr7pGjRpFdHQ0q1evpn79+kyfPp1hw4Z5fVyA9PR00tPTfXKssrxK8sb56BsHrLHW\nvni8/UK+zUpEAuKWW27h6aef5vPPP6dbt2689NJL1KpVi86dO1e4/6BBgxg0aBA//fQTTz31VJXO\n0bJlSzp37szIkSN57rnnWLduHePHj2fy5Mlex5+Xl0dCQgL16tVj+/btPPvss14f84hjK8CPPfaY\nT47rbXNNF2AAcIUxZrnn1sMHcYmIC7Vr14533nmHYcOG0ahRI2bPns3MmTNLO1OP1aVLF6Kiorjw\nwgtp2bJl6faKxqOXfTxlyhSysrJo1qwZN910E3/729/o3r17lX63osdHjBkzhmXLlpGQkEDPnj3p\n06dPyI2LP5aW/xMJc25f/u/KK6+kf//+DB06NNih+IW/l/9TkhcJc25O8hkZGVxzzTVs3bq10itl\nw5nWeBWRiDR48GCuuuoqXnzxRdcm+EBQTV4kzLm5Jh8JVJMXEZFqU5IXEXExJXkRERfTfPIiYS4x\nMTHkx2rL8SUmJvr1+Op4FYkgq1ZBr14wYAA89hhEefld/uWXYcMG56f4lq86XlWTF4kQU6fC/ffD\nSy9B//6+O67qcKFNSV7E5YqK4C9/gQ8+gM8+g/PPD3ZEEkhK8iIutmcP3Hor1KwJGRnQsGGwI5JA\n0+gaEZdasgQ6doQuXWD2bP8kePX3hj7V5EVcxloYNw5GjYLXX4fevYMdkQSTkryIi+TlwR/+AN9+\nCwsXwhln+P+c6ngNbWquEXGJVavgoougRg2nqSYQCV5Cn5K8SJizFt54A7p3d5poxo+HQE3aqDb5\n0KfmGpEwlpsLd9/t1OIXLVLtXX5NNXmRMLVsGVx4IcTHq3lGjk9JXiTMFBfDM89Ajx7O1AT/+hfE\nxQUvHnW8hjY114iEkc2bYdAgpy08IwNatQp2RBLqVJMXCQPWwr//7Yye+e1vYf780Ejw6ngNfarJ\ni4S4ffucse8rV8Knn2ruGTk5qsmLhLCPP4b27aFxY1i6NDQTvNrkQ5tq8iIhaN8+ePBB56rVt992\nxsCLVIdq8iIh5qOP4NxzoW5dp4lGCV68oZq8SIj4+WcYPhy++QYmT4bLLgt2RCemjtfQp5q8SJBZ\n66zadO65Ttv7ypXhkeAlPKgmLxJEGzc6I2d27IBp06Bz52BHdPLU8RraVJMXCYJDh+DJJ+GSS+A3\nv3GmKAjHBC+hz+uavDFmPPBbYI+19lzvQxJxt4UL4Z574LTTnGGRKSnBjqj61CYf+nxRk38L6OGD\n44i42q5dcMcdcPvt8MQTziiacE7wEh68TvLW2kXAPh/EIuJKhYXw7LNwzjnQqBF8/z3cdJNqwRIY\n6ngV8RNrnQW0H3zQmQZ48WJo1y7YUfmeOl5DW0CSfFpaWun91NRUUlNTA3FakaBZu9ZJ7ps2wSuv\nONMCi1QmPT2d9PR0nx/XWB98DBtjUoCZFXW8GmOsL84hEg727IHHH4d334WRI+H++yE2NthR+c/Y\nsbBihfNTfMsYg7XW60Y9DaEU8YEDB5zkftZZEBUFa9bAQw+5O8FLePA6yRtjpgCLgXbGmK3GmDu8\nD0skPBw+DK+/Dm3bQmamswzfSy85HayRQl/UQ5vXbfLW2n6+CEQknJSUwIcfwqhR0LIlzJzprLcq\nEmo0ukbkJFgLM2Y4a6tGRcHLL8PVV2s4pIQuJXmRKrDWqa2npTn3H3sMevZUco/01x8OlORFKnFk\nrHtamtP+npYGN96o5CbhQ0lepALFxfDBB/D0085kYmlp0Lu300Qj5anjNbQpyYuUUVAAEyc60xAk\nJcGYMXD99UruEr6U5EWA/dv2s/SeN2n5yRtkdJnBuHHt6NZNzTKVKinhkg9HUScvBbgn2NHIcah+\nIhFt68JNpHf8E4eTWxO3agnJpxzijad/5rLLlOArVVQEd97JOfNfpGnOumBHc3Kys52OlcLCYEcS\nEEryEnFsiWX5PxbwzSk3Ujv1IjCG/IVL6bT5XWq2aKxG5hMpLITbboPt21l+3V+BMCqvkhIYNMiZ\nMa5mzWBHExBK8hIx8vfms2jwm6yvcx71Rt5H4RU9qLVrM6kZz9Kia4qzkzFK8pU5eBBuuMFJljNn\nUlSzTniV1zPPQE6OMwdFhFCbvLjexlmZbB3zBucsn0TNRpeQO+Z5LnjkSk6LUnvMScnJcXqhW7eG\nceOgRg0sYVSGCxY4V68tXQoxMcGOJmCU5MWV8vfms2z0+8RP/hdN89bDxUM4MO9rLu5+WuW/qJp8\nxXbtgmuvha5dncl5jgw3ijKYcCivHTucJbkmTYLmzYMdTUCpuUZcZf2Hq/miwwMcTGpJ7LR/k3/3\nH2mQu4XUr56i1YkSPCjJV+SHH5xVxvv0cWrCx4wnNaHeJl9U5PQh3HsvXHllsKMJONXkJez9tHo3\nax6dQuNPJ1G/cBe281DyFy7loiPt7FJ9S5Y4bfCPPw6/+10FO4R8indmkatdG0aPDnYkQaEkL2Hp\nYPZBVjw2g5ipk2ib/RXRp/YiP+0Z2v3xCk6Jja7+gVWTP2rOHGckyvjxzkQ9FTEh3lwzfTpMnQrf\nfhuxV7QpyUvYOJR3iO/+MZ/CiVM558cZxDa4hMJbBhKT9h5dG9fx3YlCOWkFyttvw4gR8NFH0KlT\nsKOpno0b4fe/d15DUlKwowkaJXkJaYX7C/nuubkcmjyNs36cSc34MzjQ/WYKpz1Fxw6n+P6EkX4F\nlLXOhD2vvw7p6c548soYQ0iOk8/Ph5tvhkcfhUsvDXY0QaUkLyEnf28+K5/7jMPvTuOcrFnUrHsO\n+Vf2pXDKE7S/qIV/Tx7JzTWHD8Mf/gAZGbB4MTRrdsJfsaHYXGOts7huu3bOzwinJC8hYefS7ax/\ncTY1583izN3p1Ey4gIKrbqZg2jOcd8GJk41PhVrSCoR9+6BvX4iLgy+/hPj4YEdUff/3f06H8Vdf\n6ZsZSvISJCVFJaz997fsGT+LJhmzaFKQRXRyD4r79qP4jxPocFqD4AQWiUnhxx/ht7+Fa66B55+H\n6JPpuA6x5ppFi5wVXRYvDu8PKh9SkpeA2f7VFn781zyiFsyj3Zb51IxpCOddz6FnXqDeXZ3pUisE\n3o6R1lyzeLEz/v2vf4X77jv53w+l5ppt2+DWW51O49OqcE1EhAiB/ypxq5zNv5D52gIKP55H8rp5\n1C3aS3TLKym+4koKf/d3TuuaQkj+K4ZK0vK3KVPggQecCfR79Ah2NN4pKICbboLhw8P/tfiYkrz4\nzO4VO/lx4pccmr+Ixuu/pEX+emo07ELBpVdy6K9TadCnPZ1rhPhY5UhorikpcVZDmTgR5s+Hc8+t\n/rFCYXSNtU6HcUqKM+xTylGSl2opKSoha+56tk/9Ev77JclZi6hXvJfoRl2wF3aj6A+vEtvvQjrW\nC7PpXN3eXJOTAwMGOD8zMqBxY68PGfTmmtdecyYdW7w4Mj6kT5KSvJyQLbHszNjGlvczKFiUQb11\nGbT+5Vtio+oR1aIrxZ26cuh/Hyah51lcHOo19Ui2bp0zRcFvfgMvvACxsV4f0gY7qS5cCH/7mzpa\nK6EkL+WUFJWwffFmdnyykvyvv6P29xmkZGcQY0uITroIzrqI4uEPcrjvRbQ4uzF+HrUeeG6tyc+a\nBUOHwt//fpw5aKrHBLO5JivLmXhs0iR1tFZCST6C5WzJYfOsVexbuBKzciWJW1fSKm81NaLqEdWw\nPbRuT/GAwRy66VWad0qmUSTMv+62JG+tk9hfew1mzAjfKQqOlZvrzKczYgRcfXWwowlpSvIuV3yo\nmG1fZrFn0ToOrvgB88M66u5YR9P966hbkkNUnbMxLdpjz2lP8d39KL7+XE45rQF+mDBAAi0nx6m9\nb9vmXBzkh3nULUEYQllcDP37O9MfDx8e2HOHISV5F8jdkcvOr7L4ZUUW+ZlZ2E2bqLVzE0l7f6B5\n4Y/UiG5EVMLp0Px07JlnUTKgN8WXnU7tS1pyjtrQy3NLTX7FCmfulmuugcmT/beeaTCaa0aMcJYh\nfPVVdbRWgddJ3hjTA3gRiAbetNY+43VUUupg9kF+WrmTX9bs4MD6HRzavAO2bafmrs0k7NtEk/ws\n4uxBomNTMAmnQpMUSE7BXt6J4kvbYbu3pXlSbSJrLRwvhHuSt9ZZmm/kSGeBj379gh2Rb40b5zQ7\nffNNRC3h5w2vkrwxJhp4FbgS2A5kGGM+stZm+iI4NyopKiFn8y/8siGbvKxsDm7+iUM7sinenQ3Z\n2dTYu4e4X3aQcGAHSYd2UMvmY2o0w8Q1wyQ0wyQ1w57SDNvlIkrap1By6anEndmI06JMaF5YJIFz\n4IAzXvzbb53L+080g6QvBPKK1y++cBYAWbgQGgRp2osw5G1N/mJgg7U2C8AY8y5wA+C6JG9LLAW/\nFFCwL5+CvQcp/CWf/D25FOzO4VD2fg5n51C8Nwebsx9ycojK20+NAznE5OdQs2A/dQr3Uu9wNol2\nL8bUhRqNoGYS1EmCeklQPwkaNcKeexa0bY49oxm2fTNqnppIcpQhOdgFECnCtSa/dq3TPHPBBU4t\nt44P59evTKCaazZudKYs+Pe/4fTT/X8+F/E2yTcHtpZ5vA245Nidvhk5HVtiwVqstVDBfawt3edE\nz1X0fOm2w0XYQ4edaVOPuZki50bRYaI896OKD2OKnZ81DucTc/ggsUX5xBYfpGZJPrVKDlLL5lOL\nAqAmmDgwtSE6DmrUhZoJUKse1E6AOvWgbgI0bAhtWmMT60GjBGicQMkp9aFtI2zrBtSvHUN9Lwte\n/CTckry1MGECPPLI0eGRgW6n9ndx/fILXH+9c5VuBK7R6i1vk3yV/rxvvDICMGDggthGXFCrsTMP\nNQaM8VxQYTAV3a/iY4xnW3QNp62uRozzMyYGatVyfsbGYGNiMLEx2NgYiK3h/KwZA7VioW4cJNSG\n+rWx9eKgQW1s/ThoWBvq1yKuRhRxXhaYiM/88gvcfTesWQMLFsA55wQ8BIvx7yqvhYXQu7fTgXzv\nvf47TwhIT08nPT3d58f1NslvB1qWedwSpzZfzpt567w8jUiAhEtN/ssvnekJevZ0avJxwal+mCg/\nNtdY6wwBTUx0pkB2udTUVFJTU0sfP/bYYz45rrdJfinQ1hiTAuwAbgVc1p0vESeUk3xRETzxBIwd\nC2+8cfwFtt1g9GhnrvvPPz/JOe6lLK+SvLW2yBhzP/ApzhDKcRpZI2EtlMddb9oEAwc6tfZly6q0\nPJ+/WQxR/vhQfP11eO89Z06aIH1LcQuvr4Sx1s6x1p5urW1jrX3KF0GJBE0oNtdY6yS9iy+GG2+E\nTz8NiQQP+OdDcfZsSEuDOXOgUSPfHz/C6IpXkWOFUpLftg3uvBP27nXGiZ91VrAjqoAPy2vpUhgy\nBGbOhDZtfHfcCKZr2kXKCpXmGmudRT0uuAC6dXOaLUIxwfvyYqisLGcq5DfegEsv9c0xRTV5kXJC\noblm1y5naGRWFnz2GXToENx4KuOrD8U9e5zZJEeOdJqkxGdUkxc5VrCSvLXw1lvQvr0z5n3JktBO\n8Ed4W1779zvrsvbrB/ff75uYpJRq8iJlBau5ZsMGp/aek+N0rJ5/fnDiOEleXwxVUOA00XTq5HS2\nis+pJi9SVqCbaw4fhqefdtqgf/tb+PrrsEnwgHcfikVFTu29SRNnxsxQ6Q9xGdXkRYJlyRK46y44\n5RRnUe1TTw12RCfNycvV+FC0Fu65x5kXfupUXezkR0ryImUFoia/dy/89a/wwQfO5fr9+4dtLbba\nK0ONHAmrV8O8eT5ZUFyOT801ImX5M8mXlDjDA8880znPmjVw++1hm+CB6sX+7LPw0UfORU/x8b6P\nScpRTV4kEDIy4L77nNlQP/kkvNrdT+gkPhRfe825LVrkTMktfqeavEhZvq7JZ2fD73/vjCC5/34n\nubkpwZ9MTX78eKeT+fPPoUUL/8Uk5SjJi5TlqyRfWOi0t595JtSuDZmZMGgQRLnvX65KbfKTJ8Oj\njzpt8GHYwRzO1Fwj4kvWOrMn/uUvcO65zrzvbl6uzlRhnPz778NDDzkJvl27wMQlpZTkRcrypia/\neDE8/DAcOuQ0TZRZAMKtrDlBip8921lc/JNPgrJylSjJi/zaySb59eudBS6+/hqefNIZMePCZpnj\nOW5zzbx5cMcdzoySbuqHCDOR804UqYqT6UjcvNlZOLtzZ2eOmbVrnUU9IinBm+Ms//f5587VrO+/\nD5dcEvC45KjIeTeKVEVVmmt27oRhw5xpgJs2hR9+gFGjnA7WCGMr+lCcOxduuw2mTXOmSZagUpIX\nOdbxkvzPP8Mjj8DZZzvj3TMznfVWExMDG1+IKddc8+mnTnPV++/D5ZcHLygppSQvUlZFNdPdu53R\nMu3aOdPirlwJ//gHNG4c+PhCTpnmmjlznOaqDz9UDT6EKMmLlFW2uWbrVhg+3BnrnpvrLJ49dqwu\n5CnryIfirFkweLAzXUGXLsGNScrR6BqRY23c6MwO+f77zvqq33/vzBQpFTp177cw9L9Oor/44mCH\nI8dQkhcpKzbWaYoZNswZGqn5VSpVElOTuMO58PFc6Ngx2OFIBYz187Sqxhjr73OI+MxPP0HNmlCv\nXrAjCQuTJxbxxfR9vP5Bo2CHUmVFRfDPfzrXaMXEBDua4zPGYK31eopStcmLlNWokRL8SbDRNcit\nFT4JHuB//sfpI46UdUrUXCMi1RZuU+F/8glMnOj0oUfKNWtK8iISEbZsgSFDnPnjImn0a4R8lolI\nJCsshL594U9/irwh/EryIuKVcBhX8ac/QbNmziShkabaSd4Y09cY870xptgYc4EvgxIR8ZV333U6\nWt96K/z6EHzBm5r8KqA3sNBHsYhImAn1pJmZ6VzyMG0a1K8f7GiCo9odr9batXBkqlERkdCSlwc3\n3+wsK9uhQ7CjCR61yYuIV0KxTd5auOceZ5aFoUODHU1wVVqTN8bMBZpW8NQoa+3Mqp4kLS2t9H5q\naiqpEbBt0FixAAAJQ0lEQVQsmogEz9ixzmShX38d+k1KR6Snp5Oenu7z43o9rYExZgHwsLV22XGe\n17QGIi41ZQrMmOF0boaK//4Xevd2frZtG+xoqi/UpjUIk89KEfGlUKslb98Ot9wCb78d3gnel7wZ\nQtnbGLMVuBSYbYyZ47uwREROTmEh9OkD990H114b7GhChzejaz4EPvRhLCIShkKhNdZaJ7m3aAEj\nRwY7mtCiuWtEJOyNHet0soZTR2ugKMmLSLWFQkJdtAjS0pyO1vj4YEcTejROXkTC1rZtcOutTkdr\nmzbBjiY0KcmLSFjKz4ebbnLWWu/RI9jRhC4leRHxSjA6Xq11rmRt0wZGjAj8+cOJ2uRFJOw8/jhs\n2gQLFoRGv0AoU5IXkWoLRoL9z39g3Dj45huIiwv8+cONkryIhI2MDGc8/Lx50LSiWbXkV9QmLyJe\nCVSb/LZtzpw048bBeecF5pxuoCQvIiHvwAHo1csZSdOrV7CjCS9K8iIS0kpKYNAgp/b+5z8HO5rw\nozZ5Eam2QHS8jhgBP/0EkydrJE11KMmLSMh69VWYNcuZsqBmzWBHE56U5EXEK/7qeJ0xA556Cr78\nEho08M85IoGSvIiEnG++gd/9DubMgVNPDXY04U0dryJSbf5oI9+4EW68Ed56Czp29P3xI42SvIiE\njOxsZ1WntDS4/vpgR+MOSvIiEhLy850x8H36wN13Bzsa91CSFxGv+KLjtagI+vVz2t+ffNL748lR\n6ngVkaCyFn7/eygocCYfi1LV06eU5EWk2nzR8TpiBGRmOpOOxcZ6fzwpT0leRILm2Wdh9mxnndY6\ndYIdjTspyYuIV6rbJj9+PPzzn7rYyd+U5EUk4KZPh9Gj4YsvoEWLYEfjbkryIhJQ6elOR+ucOdCu\nXbCjcT8leRGptpPteP36a+jbF6ZOhQsv9E9MUp4GK4lIQCxbBjfcAG+/Dd27BzuayKEkLyJeqUrH\n6+rVcN11MHas81MCp9pJ3hjzrDEm0xjznTHmA2NMgi8DExF3+OEHuOYaeOEFZ41WCSxvavKfAWdb\na88DfgBG+iYkEQkXJ2qT//FHuPJKZ6qCfv0CE5OUV+0kb62da60t8Tz8BtBAKBEptXUr/OY3MHIk\nDBkS7Ggil6/a5IcCH/voWCIS5rZvdxL88OFw773BjiayVTqE0hgzF2hawVOjrLUzPfuMBg5Zayf7\nIT4RCXHHdrxu2wZXXAF33QUPPhicmOSoSpO8tfaqyp43xgwBrgN+U9l+aWlppfdTU1NJTU2tanwi\nEka2bHES/B/+AA8/HOxowkt6ejrp6ek+P66x1Zx4whjTA3geuNxam13Jfra65xCR0DZ9OkyY4PzM\nynLGvw8fDn/8Y7AjC3/GGKy1Xs/z6U2b/CtAPDDXGLPcGPOat8GISHjatAlSU53mGSX40FLtaQ2s\ntW19GYiIhKctW5wEP2KE00wjoUVz14iIV5Yvd65k1bqsoanabfJVPoHa5EVca+9eyMhwrmgV3/JV\nm7ySvIhICAqFjlcREQlxSvIiIi6mJC8i4mJK8iIiLqYkLyLiYkryIiIupiQvIuJiSvIiIi6mJC8i\n4mJK8iIiLqYkLyLiYkryIiIupiQvIuJiSvIiIi6mJC8i4mJK8iIiLqYkLyLiYkryIiIupiQvIuJi\nSvIiIi6mJC8i4mJK8iIiLqYkLyLiYkryIiIupiQvIuJi1U7yxpjHjTHfGWNWGGPmG2Na+jIwERHx\nnjc1+f+11p5nre0ATAfG+Cgm10pPTw92CCFDZXGUyuIolYXvVTvJW2tzyzyMB7K9D8fd9AY+SmVx\nlMriKJWF79Xw5peNMU8CA4GDwKU+iUhERHym0pq8MWauMWZVBbeeANba0dbaZGAC8EIA4hURkZNg\nrLXeH8SYZOBja+05FTy3ATjN65OIiESWjdbaNt4epNrNNcaYttba9Z6HNwDLK9rPF0GKiEj1VLsm\nb4yZBpwOFAMbgXuttXt8GJuIiHjJJ801IiISmvx2xasxpocxZq0xZr0xZoS/zhNKjDFZxpiVxpjl\nxpglnm0NPB3YPxhjPjPG1C+z/0hP+aw1xlwdvMi9Z4wZb4zZbYxZVWbbSb92Y8yFns799caYlwL9\nOnzhOGWRZozZ5nlvLDfGXFvmOTeXRUtjzAJjzPfGmNXGmOGe7RH33qikLPz73rDW+vwGRAMbgBQg\nBlgBnOmPc4XSDdgENDhm2/8Cj3jujwCe9tw/y1MuMZ5y2gBEBfs1ePHauwHnA6uq+dqPfKtcAlzs\nuf8x0CPYr81HZTEGeKiCfd1eFk2BDp778cA64MxIfG9UUhZ+fW/4qyZ/MbDBWptlrT0MvIvTORsJ\nzDGPewFve+6/DdzouX8DMMVae9ham4XzB7w4IBH6gbV2EbDvmM0n89ovMcacAtS11i7x7DexzO+E\njeOUBfz6vQHuL4td1toVnvt5QCbQnAh8b1RSFuDH94a/knxzYGuZx9s4+mLczALzjDFLjTF3ebY1\nsdbu9tzfDTTx3G+GUy5HuLGMTva1H7t9O+4qk2Ge+Z7GlWmeiJiyMMak4HzD+YYIf2+UKYuvPZv8\n9t7wV5KP1N7cLtba84FrgfuMMd3KPmmd71aVlY1ry60Kr93t/g84FegA7ASeD244gWWMiQfeBx6w\n5adEibj3hqcspuGURR5+fm/4K8lvB8rOStmS8p88rmSt3en5+RPwIU7zy25jTFMAz9esI8NMjy2j\nFp5tbnIyr32bZ3uLY7a7okystXusB/AmR5vmXF8WxpgYnAQ/yVo73bM5It8bZcrinSNl4e/3hr+S\n/FKgrTEmxRgTC9wKfOSnc4UEY0xtY0xdz/06wNXAKpzXPdiz22CcGTvxbL/NGBNrjDkVaIvTmeIm\nJ/XarbW7gP3GmEuMMQZnXqTpxx40HHkS2RG9cd4b4PKy8MQ+DlhjrX2xzFMR9944Xln4/b3hx57k\na3F6jzcAI4Pds+3vG87XrRWe2+ojrxloAMwDfgA+A+qX+Z1RnvJZC1wT7Nfg5eufAuwADuH0x9xR\nndcOXOh5k28AXg726/JRWQzF6RxbCXzn+YdsEiFl0RUo8fxfLPfcekTie+M4ZXGtv98buhhKRMTF\ntPyfiIiLKcmLiLiYkryIiIspyYuIuJiSvIiIiynJi4i4mJK8iIiLKcmLiLjY/wNlc8PVQU8NxAAA\nAABJRU5ErkJggg==\n",
       "text": [
        "<matplotlib.figure.Figure at 0x9fc15c0>"
       ]
      }
     ],
     "prompt_number": 11
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Looks like the polynomial solution suffers from integer overflow at around n$\\approx$1300; earlier than the brute force solution. This is understandable considering the polynomial solution deals with n<sup>3</sup> while brute force only deals with n<sup>2</sup>. We'll switch to floats to overcome overflow issues in both cases."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "brute = lambda n: sum([1.*x*x for x in xrange(1,n+1)])\n",
      "poly = lambda n: round(1./6 * n + 1./2 * pow(n, 2.) + 1./3 * pow(n, 3.))\n",
      "\n",
      "x = np.array(range(1,2200))\n",
      "brute_y = np.array([brute(t) for t in x])\n",
      "poly_y = np.array([poly(t) for t in x])\n",
      "\n",
      "plt.plot(x, brute_y, label='Brute Force', color='blue')\n",
      "plt.plot(x, poly_y, label='Polynomial', color='red')\n",
      "plt.legend()\n",
      "\n",
      "print 'max error:', max(brute_y - poly_y)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "max error: 0.0\n"
       ]
      },
      {
       "metadata": {},
       "output_type": "display_data",
       "png": "iVBORw0KGgoAAAANSUhEUgAAAXwAAAEGCAYAAABmXi5tAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAIABJREFUeJzt3Xl8VNXdx/HPL4GwhCXBQBBIiAjiggoFF1ZHHhfgEaxa\nxQ0UfdRa9bFitUWroHVrlUerVqWKItCCSqssQhXRQWmRRXYJCCgQtrCFQBIhJDnPHxljiIEMMJk7\nmfm+X695cZczd35zuPnl5NxzzzXnHCIiEv3ivA5ARETCQwlfRCRGKOGLiMQIJXwRkRihhC8iEiOU\n8EVEYkTYEr6ZvWlm2Wa2PIiyrc1slpktNbPPzKxlOGIUEYlm4WzhvwX0CbLsc8AY59zZwOPA09UW\nlYhIjAhbwnfOfQHklN9mZieb2QwzW2hmn5tZ+8Cu04BPA8t+4PJwxSkiEq287sP/K3CPc64L8ADw\nSmD7UuCqwPIVQEMzS/YgPhGRqFHLqw82swZAV+A9M/thc0Lg398AL5vZzcDnwGagONwxiohEE88S\nPqV/XexxznWquMM5t5VACz/wi+Eq59zeMMcnIhJVgurSMbN4M1tsZlMPs/9FM1sTGFXzkwRemUAC\n/87MfhE4hpnZWYHlE8zsh9iGAaODOaaIiBxesH349wIrgZ9MrWlm/YC2zrl2wO3Aq5UdwMwmAP8B\n2ptZlpkNAW4AbjWzJcAKYECg+IXAKjNbDTQFngz+K4mISGWsqumRzawVMIbSpDvUOde/wv7XgM+c\nc+8E1lcBFzjnsqslYhEROSbBtPCfp3QETclh9rcEssqtbwJaHWdcIiISYkdM+GZ2GbDdObcYsCMV\nrbCup6qIiESYqkbpdAMGBPrp6wKNzGysc25wuTKbgbRy660C2w7Rtm1bt27duuONV0Qk1qxzzrUN\nyZGcc0G9gAuAqZVs7wdMDyyfD3x5mPc7KTV8+HCvQ4gYqosfqS5+pLr4USB3Bp2rj/Q62nH4DsDM\n7ghk8FHOuelm1s/M1gL5wJAQ/B4SEZEQCzrhO+dmA7MDy6Mq7Ls7xHGJiEiIeT2XTkzy+XxehxAx\nVBc/Ul38SHVRPaochx+yDzJz4fosEZFoYWY45440SjJoXs6lIyIh1KRJE3JycqouKBEpOTmZ3bt3\nV+tnqIUvEiUCLUGvw5BjdLj/v1C28NWHLyISI5TwRURihBK+iEiMUMIXEYkRSvgiEhYZGRnUr1+f\nhg0b0qRJEy677DI2bdp0XMeMi4vj22+/Pa73N2jQgIYNG5bFFc2U8EUkLMyMadOmsW/fPrZu3Upq\nair33HPPYcuXlBxuRvZDHe/IpGXLlrFv3z727dt3TMMii4trzuO2lfBFJOzq1KnDVVddxcqVK8u2\n3Xzzzdx5553069ePBg0a8Nlnn+Hz+Rg9+scnnI4ZM4aePXsC0KtXLwDOPvtsGjZsyHvvvQfAtGnT\n6NixI8nJyXTv3p3ly5cfdXy5ubkMHjyYZs2akZGRwZNPPln2i2XMmDF0796doUOHkpKSwmOPPcb+\n/fu5//77ycjIICkpiZ49e7J//34AvvzyS7p160ZycjIdO3Zk9uzZx1ZpIaAbr0QkbH5ImgUFBbzz\nzjt07dr1kP0TJkxgxowZdO3alQMHDmBmmFU+BP3zzz8nLi6OZcuW0aZNGwAWL17MrbfeyrRp0+jS\npQvjxo1jwIABrF69moSEhCPGVN4999zDvn37+O6779i5cyeXXHIJJ554IrfccgsA8+fP5/rrr2f7\n9u0UFhZy//33k5mZydy5c0lNTWX+/PnExcWxefNmLrvsMsaPH0+fPn345JNPuOqqq1i1ahUpKSnH\nXI/HLFTTblb1QtMji1SrYH7G4Phfx6p169auQYMGLikpydWuXdu1bNnSLV++vGz/zTff7G666aZD\n3uPz+dzo0aPL1t966y3Xo0ePsnUzc+vWrStb/+Uvf+keeeSRQ47Rvn17N3v27EpjMjPXqFEjl5SU\n5JKSkty9997rioqKXEJCgsvMzCwrN2rUKOfz+cpiSE9PL9tXXFzs6tWr55YtW/aT4z/zzDNu0KBB\nh2y79NJL3dtvv/2Tsof7/8PD6ZFFpAbz8kZcM2Py5Mn07t0b5xwffPABF1xwAZmZmTRr1gyAtLS0\nKo5yZBs2bGDs2LG89NJLZdsOHjzI1q1bD/uexYsXl/2FAJCdnc3Bgwdp3bp12bb09HQ2b/7xuU7l\n49y5cyf79+/n5JNPrjSe9957j6lTp5ZtKyoqonfv3kf/5UJAffgiEnZmxhVXXEF8fDxz5sw5bLnE\nxETy8/PL1rdt23bE46anp/Pwww+Tk5NT9srLy2PgwIFBx5aSkkLt2rVZv3592baNGzfSqtWPj+ou\n382UkpJC3bp1Wbt2baXxDBo06JB49u3bx4MPPhh0PKGkhC8iYeMCf2I455g8eTI5OTmcdtpph+wr\nr2PHjvzzn//k+++/Z+3atYdcwAVITU2l/KNTb7vtNl577TXmz5+Pc478/Hw+/PBD8vLygo4xPj6e\na665hocffpi8vDw2bNjA888/z4033lhp+bi4OG655RaGDh3K1q1bKS4uZu7cuRQWFnLjjTcydepU\nPv74Y4qLi9m/fz9+v/+QvxbCSQlfRMKmf//+NGzYkMaNG/PII48wduzYsoRf2QXa++67j4SEBFJT\nUxkyZAg33njjIWVGjBjBTTfdRHJyMpMmTaJz5868/vrr3H333TRp0oR27doxduzYw8ZzuAvCL730\nEomJibRp04aePXtyww03MGTIkMPG+dxzz3HmmWdyzjnncMIJJzBs2DBKSkpo1aoVkydP5qmnnqJZ\ns2akp6czcuTIoIechppmyxSJEpots2bTbJkiIhIyVSZ8M6trZvPMbImZrTSzpysp4zOzXDNbHHj9\nvnrCFRGRY1XlsEzn3H4zu9A5V2BmtYA5ZtbDOVfx0vps59yA6glTRESOV1BdOs65gsBiAhAPVDbh\nREj6mEREpHoElfDNLM7MlgDZwGfOuZUVijigm5ktNbPpZnZ6qAMVEZHjE2wLv8Q51xFoBfQyM1+F\nIouANOfc2cBLwAchjVJERI7bUU2t4JzLNbMPgS6Av9z2feWWZ5jZK2bWxDl3SNfPiBEjypZ9Ph8+\nn+/YohYRiVJ+vx+/318tx65yHL6ZpQBFzrk9ZlYP+Ah4zDk3q1yZVGB7YDKic4F3nXMZFY6jcfgi\n1Ujj8Gu2SBmHfyLwaaAPfx4w1Tk3y8zuMLM7AmV+ASwPlHkBuDYUwYlI7MrIyGDWrFlVFwyjfv36\nMW7cuKDKRmL8wQzLXA78rJLto8ot/wX4S2hDE5FokZGRwfbt24mPjycxMZG+ffvy8ssvk5iYeNj3\nHGkufK9Mnz496LKRGL/utBWRalf+8YaLFi1i4cKFPPHEE16HFXOU8EUkrFq0aEGfPn1YsWIFU6ZM\n4YwzziA5OZkLL7yQVatW/aT8tm3bSExMPOR5s4sWLaJZs2YUFRUxZswYevTowQMPPECTJk1o06YN\n//rXv8rKbtmyhQEDBnDCCSfQrl073njjjbJ9I0aM4Oqrr2bQoEE0atSIs846izVr1vD000+TmppK\n69atmTlzZln58o9cXLduHb179yYlJYWmTZty4403kpubWx1VFjJK+CISFj9ckMzKymLGjBk0bNiQ\n66+/nhdffJGdO3fSr18/+vfvT1FR0SHva968OT6fj3fffbds27hx47juuuuoVau0V3r+/Pmceuqp\n7Nq1iwcffJBbb721rOy1115Leno6W7duZdKkSTz00EN89tlnZfunTZvG4MGDycnJoVOnTlx88cVA\n6S+KRx55hDvuuKOsbMVumocffpitW7eSmZlJVlbWISMRI1KoHp1V1Qs94lCkWgX1M+bRMw7LP96w\ndevW7q677nJ/+MMf3MCBA8vKlJSUuJYtW5Y9jjAjI8PNmjXLOefcxIkTXffu3Z1zzhUVFbnmzZu7\nBQsWOOdKHznYtm3bsuPk5+c7M3PZ2dlu48aNLj4+3uXl5ZXtHzZsmLv55pudc84NHz7cXXLJJWX7\npkyZ4ho0aOBKSkqcc87t3bvXmZnLzc11zv30kYvlvf/++65Tp05l6+XjD8bh/v8I4SMO1cIXiSWh\nSPnH4IfHG+bk5LB+/XpefvlltmzZQnp6+iFl0tLSKn04yOWXX87KlStZv349M2fOpHHjxnTp0qVs\nf/PmzcuW69evD0BeXh5btmyhSZMmh1wcrvi4wh8erwhQr149UlJSylrx9erVKztWRdnZ2Vx77bW0\natWKxo0bM2jQIHbt2nXUdRNOSvgi4okWLVqwYcOGsnXnHFlZWbRs2fInZevWrcvVV1/N+PHjGT9+\nPIMHDw76M3bv3n1Iwq74uMJj9dBDDxEfH8+KFSvIzc1l3Lhxnj3YJFhK+CLiiWuuuYYPP/yQTz/9\nlIMHDzJy5Ejq1q1Lt27dKi0/ePBg3nrrLaZMmcKgQYOC+oy0tDS6devGsGHDOHDgAMuWLePNN988\n7OMKj0ZeXh6JiYk0atSIzZs38+yzzx73MaubEr6IeOKUU05h/Pjx3HPPPTRt2pQPP/yQqVOnll2I\nrah79+7ExcXRuXNn0tLSyrZXNt69/PqECRNYv349LVq04Morr+Txxx+nd+/eQb23svUfDB8+nEWL\nFtG4cWP69+/PVVddFXHj7ivSIw5FokQsTK1w0UUXcf3113PLLbd4HUrIhWNqBSV8kSgR7Ql/wYIF\nXHrppWRlZR3xDt2aKlLm0hER8dRNN93ExRdfzAsvvBCVyT5c1MIXiRLR3sKPdmrhi4hIyCjhi4jE\nCCV8EZEYcVSPOBSRyJWcnBzx48Dl8JKTk6v9M3TRVkSiwoIRH5L8zIOctHcZ8QnxXocTMrpoKyJS\nTnFhMUnP/I5d9z0ZVck+1JTwRaTG+8/tYyiok8S5T17udSgR7YgJ38zqmtk8M1tiZivN7OnDlHvR\nzNaY2VIz61Q9oYqI/FT+9nzajnuU+P97DovTNYwjOeJFW+fcfjO70DlXYGa1gDlm1sM5N+eHMmbW\nD2jrnGtnZucBrwLnV2/YIiKlFlw7koSWPel263lehxLxqhyl45wrCCwmAPHA7gpFBgBvB8rOM7Mk\nM0t1zmWHNFIRkQq2L9vGWf4/k+9f6HUoNUKVffhmFmdmS4Bs4DPn3MoKRVoCWeXWNwHH/3QBEZEq\nrBo4nGU/G0Jar5O8DqVGCKaFXwJ0NLPGwEdm5nPO+SsUq9hxVun4y/IP+PX5fPh8vqOJVUSkzNrJ\nX3Pa6vepvW6116GElN/vx+/3V8uxj2ocvpk9AnzvnHuu3LbXAL9zbmJgfRVwQcUuHY3DF5FQmp96\nGQVd/wvfB/d5HUq1Cts4fDNLMbOkwHI94GJgcYViU4DBgTLnA3vUfy8i1WnxyE9pvnslXcf+yutQ\napSqunROBN42szhKfzmMc87NMrM7AJxzo5xz082sn5mtBfKBIdUbsojEspKiEuo+8hs23f0M6Y3q\neB1OjaKpFUSkRpnzy3Ekjf8LZ+ydGxPj7kPZpaPJ00SkxsjblsfJrw9j5yvvxkSyDzW18EWkxvD3\nfITaWd/Sff3fvA4lbNTCF5GYs2nOes769yscmLfU61BqLLXwRaRGmJt2DQdOORPfrEe8DiWs1MIX\nkZiy5M+zSds6jxOWvu11KDWapkcWkYhWXFhMvd/dy8Z7nqVek3peh1OjKeGLSET79y2j2Z/QiK4j\nr/Y6lBpPXToiErFyN+zh1AmPsnv8DA3DDAFdtBWRiOXvcj9x+fvolflXr0PxjC7aikjU+3bGas5c\n9DYlyyvOyC7HSn34IhJxXIlj96D/ZXn/h2h6RjOvw4kaauGLSMT58rf/JCVvC2dPuMfrUKKKEr6I\nRJT87fmkP38fO58fT+36tb0OJ6rooq2IRBT/+b+j1vbN9Ph2nNehRARdtBWRqLRuWiYd5o+mZMly\nr0OJSrpoKyIRwZU4cgffw9c//z3NzmrudThRSS18EYkIc+9/jxO+38FZf7/L61CilhK+iHhu35Z9\nnPTiUHa8NJFadZWWqosu2oqI5/znPECtnB30WDvG61AiTlgv2ppZGjAWaAY44K/OuRcrlPEBk4Fv\nA5v+4Zx7IhQBikh0Wzv5azp8NQa3bIXXoUS9YP52Ogjc55xbYmYNgK/MbKZzLrNCudnOuQGhD1FE\nolVJUQkFg25ny8DH6dUh1etwol6Vo3Scc9ucc0sCy3lAJtCikqKayk5Ejsqcm17HnKPHuDu8DiUm\nHNWwTDPLADoB8yrsckA3M1tqZtPN7PTQhCci0Sp7yVZOn/B76o79K3G1NEI8HIK+HB7ozpkE3Bto\n6Ze3CEhzzhWYWV/gA+CUiscYMWJE2bLP58Pn8x1DyCISDb7tfy8Hut6O74oOXocSUfx+P36/v1qO\nHdQoHTOrDUwDZjjnXgii/HdAZ+fc7nLbNEpHRACY/+g0mj1zH6nblumxhVUI5SidKv+OMjMDRgMr\nD5fszSw1UA4zO5fSXyS7KysrIrEtb1seLZ66i91PvqZkH2ZVtvDNrAfwObCM0r56gIeAdADn3Cgz\nuwu4EygCCoChzrkvKxxHLXwRwd95KLX27KLHure9DqVGCGULXzdeiUjYZI7/ipTB/YjL/JoT2qd4\nHU6NENYuHRGRUCjaXwS3387qW/+kZO8RJXwRCYs5V4ykoF4Tuo8a7HUoMUuzFIlItft2+io6fPQc\n+z9fgMXpHk2vqIUvItWquLCY/IFD+Pqax2jVI8PrcGKaEr6IVKsvrnmR4vg69Bz/S69DiXnq0hGR\narNh1lrOnPIkeTO/1PQJEUDDMkWkWpQUlbAs5UL2+H6O74P7vA6nxtKwTBGJeF9c/yrxxQfp+e7/\neh2KBKhLR0RCbtOc9XSYNJzcaXOIT4j3OhwJUJeOiIRUSVEJS5pdwt7zLsY347deh1PjqUtHRCLW\nF9f+hdoH8+nx/v1ehyIVqEtHRELm2+mrOOOfj5P30X+oVVfpJdKohS8iIXGw4CD7rx7EyoGPk3Fx\nO6/DkUqoD19EQsJ/4WM0WD6XzttnaPqEEAplH77+5hKR47Zy7ELOmP0XiuYvVrKPYOrSEZHj8v3u\n76lz2yDW3P0iJ3Zp6XU4cgTq0hGR4zK706+pvWsb3TZO9DqUqKQuHRGJCIuencUpyyZR95tlXoci\nQVCXjogck91rdtF82M1sfnw0ySc38TocCUKVCd/M0szsMzP72sxWmFmlE2OY2YtmtsbMlppZp9CH\nKiKRwpU41vS6lW/OvpouD1/qdTgSpGC6dA4C9znnlphZA+ArM5vpnMv8oYCZ9QPaOufamdl5wKvA\n+dUTsoh47YsbXqNp7kY6rn7H61DkKFTZwnfObXPOLQks5wGZQIsKxQYAbwfKzAOSzCw1xLGKSARY\nO/lrznjnEer8YwJ1GtXxOhw5CkfVh29mGUAnYF6FXS2BrHLrm4BWxxOYiESe/Xv2U3Ltdawc/Efa\n9G3vdThylIIepRPozpkE3Bto6f+kSIX1n4zBHDFiRNmyz+fD5/MF+/EiEgHm9XqAhJRT6fHmLV6H\nErX8fj9+v79ajh3UOHwzqw1MA2Y4516oZP9rgN85NzGwvgq4wDmXXa6MxuGL1GDzH5lKi6fvoeG6\nJTRuneR1ODEjrNMjm5kBo4GVlSX7gCnA4ED584E95ZO9iNRs2xZtIeOp29j90t+U7GuwKlv4ZtYD\n+BxYxo/dNA8B6QDOuVGBci8DfYB8YIhzblGF46iFL1IDFe0vYkXzi9jzs974Pn3U63BiTihb+Jpa\nQUSOyN/9YRquWkDHrTP0uEIPaGoFEQmLBY/P4JR5Y6m99Csl+yigqRVEpFJb5mXR+rEh7Hjh7zQ9\no5nX4UgIqEtHRH6iMK+Q1SdewK6eV+Cb/qDX4cQ09eGLSLXyd7mf+lnf0GXzZOJqqSPAS+rDF5Fq\n8+Vv36ftkn+QuHqRkn2U0f+miJTZMGstJz97B3tGvaMpj6OQunREBIC8bXlszejK1it+Ra8Jd3od\njgSoD19EQsqVOL5sPZCieg3pseoNPYg8gqgPX0RCavZlz9I0Zz0nL/9cyT6KKeGLxLivnpnJaR89\nT/F/5lM3qa7X4Ug10kVbkRiW9fl3pD90I1v/byItzkvzOhypZurDF4lRBTsLyErrxra+Q7jgn/d6\nHY4chi7aishxcSWO/7S5ERcXR/e1Y9VvH8F00VZEjsvsPk/TbMc3ZGyYrWQfQ5TwRWLMlw/+k1M+\nfZW4+fOon1Lf63AkjHTRViSGZP5tEW2fu4PcMR/Q/GctvA5HwkwJXyRGZC/ZSqObfs6a+17ltBs7\nex2OeEAXbUViwPe7v+fb9AvYcf4AfJ/83utw5CholI6IBM2VOOZmXIeLi6fbt+N1kbaGCWXCr7JL\nx8zeNLNsM1t+mP0+M8s1s8WBl5oPIhFkdu/HaLR7PZ2XjFayj3HBjNJ5C3gJGHuEMrOdcwNCE5KI\nhMoXt7xFm3+Ppd7iuZo2Qapu4TvnvgByqiimZoNIhFn45Ee0f3sYRVNm0LRDqtfhSAQIxSgdB3Qz\ns6VmNt3MTg/BMUXkOKyasJjWjwxi28v/oE3f9l6HIxEiFDdeLQLSnHMFZtYX+AA4pbKCI0aMKFv2\n+Xz4fL4QfLyIlLd57kYa39iftfe/Stc7u3sdjhwlv9+P3++vlmMHNUrHzDKAqc65M4Mo+x3Q2Tm3\nu8J2jdIRqWZ7vsth52k92Nz3Ni54/9dehyMhENZROkEEk2pmFlg+l9JfIrureJuIhNiBvQdY3+kK\nNp1xqZK9VKrKLh0zmwBcAKSYWRYwHKgN4JwbBfwCuNPMioAC4NrqC1dEKlNcWMyi02+ABk3pNe85\nr8ORCKUbr0RqOFfimHPabdTfuYEO302jTqM6XockIaTpkUWkzOyuvyNl8woy1n6iZC9HpIQvUoP5\n+/6RVkun0WT55zRo3sDrcCTCKeGL1FCfD36dNp+MovbcL2jS7gSvw5EaQAlfpAaaO/Q92v1tBIUf\nz+bELi29DkdqCM2HL1LDzH90Gm1fuJu9E6bT+r/aeh2O1CBK+CI1yMIn/sVJT9zC9tFTaX/N2V6H\nIzWMEr5IDbHoT5/Q+tHBbHv1A84Ycq7X4UgNpIQvUgMs+fNs0n93HVv+PIkz7+jmdThSQynhi0S4\nZa/ModV9vyDr2Xc4+55eXocjNZgSvkgEW/HGl5x495VsePJvdLq/t9fhSA2nhC8SoZa9MofU2wew\nfvgYOg+7xOtwJAoo4YtEoMUjP6XF3Vew8cnxnDO8n9fhSJRQwheJMAuf+BdpDwxk0/OT1LKXkNKd\ntiIRZN7DU2jz9P+w9dXJdNRoHAkxJXyRCDF36Hu0feFudoyZzpmDu3gdjkQhJXyRCDDnf8bQ7q1h\n7J74MafrDlqpJkr4Ih7z//eztP3oL+RP/Yz2/U71OhyJYkr4Ih5xJY7Z5z1I2rIPiZ87hzbntPI6\nJIlySvgiHijaX8SXHf6HE7JXk7xC89lLeFQ5LNPM3jSzbDNbfoQyL5rZGjNbamadQhuiSHT5fvf3\nfJVxJXVys2mz7hMlewmbYMbhvwX0OdxOM+sHtHXOtQNuB14NUWwiUSdn3W6+OekSiuo25OzvJpPY\nLNHrkCSGVJnwnXNfADlHKDIAeDtQdh6QZGapoQlPJHps+HQde07rSk678+i6dhwJDRK8DkliTCju\ntG0JZJVb3wTo6pNIOctH/Ye6F/cg66pf41v4HHG1dJO7hF+oLtpahXVXWaERI0aULft8Pnw+X4g+\nXiRyzR36Hu1e+BXfjRhLr0f7eh2ORDi/34/f76+WY5tzlebmQwuZZQBTnXNnVrLvNcDvnJsYWF8F\nXOCcy65QzgXzWSLRwpU4Zv/3nzhl5svs+9tU2g/s6HVIUgOZGc65io3qYxKKFv4U4G5gopmdD+yp\nmOxFYk1hXiFfdrmLEzcswObOpb3G2EsEqDLhm9kE4AIgxcyygOFAbQDn3Cjn3HQz62dma4F8YEh1\nBiwS6XasyGZrt6uok5hCi3Vf0LBFQ69DEgGC7NIJyQepS0diQOb4r2h08xWs6T6EXrOG6+KsHLdQ\ndunobBQJkX/f9XeaDu5D1tAX8M1+TMleIo6mVhA5TsWFxXzRYxhtFk9i93ufcv5VPxnbIBIRlPBF\njsPOzB1s6HE9jVwJDVYuIF3TJEgE09+cIsdo2av/pvDMn7Gv/TmcteUjzYkjEU8JX+QouRKHv/9I\nTrzrSjY99Cq+/zxFrbr6Y1kin85SkaOQu2EPmV1voeneTRz4fB7n9sjwOiSRoKmFLxKkzPFfsadt\nFw6ktKDtli9opWQvNYwSvkgViguL8ff9IymD+7L57qe4YNnL1GlUx+uwRI6aunREjmDrgk1su2QQ\nySXFFP57Id26pnsdksgxUwtf5DDmPvAPap3XmdwuF9Fhx2e0VLKXGk4tfJEK9m3Zx+LeQ2m97jOy\nX5+C79bzvA5JJCTUwhcpZ9Gzs8hNPxMrKaHJhsV0ULKXKKIWvgiBVv3FD9J29TQ2P/pXeupBJRKF\n1MKXmLd45KfsaX0WdvAAieuWc46SvUQptfAlZuVuzGVpv2G0y5zCpkf/Ss/h/bwOSaRaqYUvMceV\nOOYOfY+Ck06H4iLqrV3OOUr2EgPUwpeYsmnOerZeeRdN965nx0vv0OtXPbwOSSRs1MKXmHCw4CD+\nfn+iXq8u5HfqQfrOxZylZC8xJqiEb2Z9zGyVma0xs99Wst9nZrlmtjjw+n3oQxU5NouencX6Jp1o\nMH8WeZ/Mw/fRMBIaJHgdlkjYBfMQ83jgZeAiYDOwwMymOOcyKxSd7ZwbUA0xihyTjf5v2XL9b2i5\nYzGb7xvJec9cgcWF5NGgIjVSMC38c4G1zrn1zrmDwETg8krK6SdJIkLetjz83R8msfe57O/QhaY7\nMjn/T1cq2UvMCybhtwSyyq1vCmwrzwHdzGypmU03s9NDFaBIsIoLi5lz29vsa3kqtbZupHD+Unwf\nP0TdpLpehyYSEYIZpeOCKLMISHPOFZhZX+AD4JTjikwkSK7EsWDEhyT/aRiNEhqz89X36HF7V6/D\nEok4wSS+ipK0AAAKHklEQVT8zUBaufU0Slv5ZZxz+8otzzCzV8ysiXNud/lyI0aMKFv2+Xz4fL5j\nCFnkR8tH/YeSB39LkwO72XX/05z7h/7qupEaze/34/f7q+XY5tyRG/BmVgtYDfwXsAWYD1xX/qKt\nmaUC251zzszOBd51zmVUOI6r6rNEgrV28tfsvPP3tNq+iPU3P0bXVwYRnxDvdVgiIWdmOOdC0oqp\nsoXvnCsys7uBj4B4YLRzLtPM7gjsHwX8ArjTzIqAAuDaUAQnUtE3/1jOrl//gbabZ7Ppvx8kZdwE\nWqmPXiQoVbbwQ/ZBauHLcfhm0jJ2/fpxTt46h5V9f8M5b95JYrNEr8MSqXahbOHrTluJaJl/W8SX\nLa6g8cBLOdC5Gw2yv8U37TdK9iLHQHPpSMRxJY6FT/yL+Beeo/neb9je/34avv43fCn1vQ5NpEZT\nwpeIcWDvARYMnUDq+OdoZLXYefNvaDpyIC3q1/Y6NJGooD588dzOzB2s+PUbtP/kZbYknQEPPMDP\nHrxIwytFCPMoHZHq4EocK974ktxnXqHD+mnEn/xz9k6YTudrzvY6NJGopYQvYZW/PZ+vfvN3mk16\nhYZFeezqeydu5p/peXITr0MTiXrq0pFq50ocX781n90j36LDqvdYk9qTWv/7Kzo9cBFxtTRQTORI\n1KUjNcK2RVtY9fvxpM0aQ6IrYqfvZva/tYTzzkur+s0iEnJK+BJSedvyWPbkVGq/M562O+cSd8pV\n5L/wOmfe0Y2TdBFWxFNK+HLcCnYWsPTp6fDOO5y++WNqN+3OgSuvI+Hxd+mlG6REIoYSvhyT/O35\nrHh+JkUT3qXDhukkNDmHgssGUvz71zin3QlehycilVDCl6BlL9nK6v+bRt2PpnDq9tnUTj6HA5f+\ngsIPX6DzGc28Dk9EqqCEL4dVUlTC6omLyX77X6TMnULLgjXEp/ehaOANuPvH8bPWSV6HKCJHQcMy\n5RCb527k21Ezif90JqdsmsXe2ieQddqlNBp0OR3u7EltTXMgElahHJaphB/jti/bxrq351A400/6\nqpk0LNrNN2kXUdz7Yk7+5cW00BBKEU8p4csxcSWO9TPXsGniHJjzBWkb5tC4aBdrmnanoHNPUm+4\niPYDO+pmKJEIooQvQdnx9XbWT1pI/uyF1P96ASftmE9hXB3Wt+pJcdcenHhNT07uf7oSvEgEU8KX\nQ7gSx7avNrP5oxXkzVlC3eULaJW9kIbFuaxL7sLeU7pQp+c5pF95Di27pnsdrogcBSX8GJazbjcb\nZ3zNnjnLseXLabxpBa33reAgCWQlncnek84iods5tBjQhfQLT1brXaSGC2vCN7M+wAuUPsD8Defc\nHysp8yLQl9IHmN/snFtcSRkl/CDlbsxls38NexasofDrNdRav4ak7WtoUbCGWu4gGxqcQU7LDrgz\nzqRRtw606tOBphoHLxKVwpbwzSweWA1cBGwGFgDXOecyy5XpB9ztnOtnZucBf3bOnV/JsZTwgeLC\nYj5465+cYq3Yl5lF4ZqNWNZG6m7fSKPcjTTbv5E6bj+b6rUj54R2HEhrS/yp7WjcpR0n9mpHyunN\nourBIH6/H5/P53UYEUF18SPVxY/COVvmucBa59z6wAdPBC4HMsuVGQC8DeCcm2dmSWaW6pzLDkWA\nkc6VOPK25bF3Qw55WTnkfbud/RuyObgpG7KzqbUrm7q52TQoyCbpQDZNSnYylwTaJ56BJaVD83Ro\n0wZ3qQ/XIZ2Sn6WReHozTo2ipH4k+sH+keriR6qL6lFVwm8JZJVb3wScF0SZVkBEJXxX4ijaX0Rh\nXiEH8ws5WHCQwr372b8rnwO78ynMyedgbgFFufkU782neF8+bl8+FBRAfj5xeXuplZdDnfwc6u3P\nof7BPTQsyqGx24NRl7i4JOJqJ2P1m0GjVKxJKq5ZKq7DabjWqbiTU3HtU+G0ZjR47ik6jBjhdZWI\nSIypKuEH2wdTsTla6fsWNOsHzmHOAeX/LalkW+n2itvAEVdxO444V0ytkkLiSw5S2xVSu6SQWpQu\nJ1BIAgeBWhi1MRLAErC4Olh8YumrdiIkJGIJ9aFuIlY3EVcvERITISUF2raBlCRcajIlzZNwrZJx\n6cmUpDWmQYMEGgRZUSIiXqmqD/98YIRzrk9gfRhQUv7CrZm9BvidcxMD66uACyp26ZjZWuDk0H8F\nEZGots451zYUB6qqhb8QaGdmGcAWYCBwXYUyU4C7gYmBXxB7Kuu/D1XAIiJybI6Y8J1zRWZ2N/AR\npcMyRzvnMs3sjsD+Uc656WbWL9CCzweGVHvUIiJy1MJ245WIiHgrLLdhmlkfM1tlZmvM7Lfh+Ewv\nmdl6M1tmZovNbH5gWxMzm2lm35jZx2aWVK78sEDdrDKzS7yL/PiZ2Ztmlm1my8ttO+rvbmadzWx5\nYN+fw/09QuEwdTHCzDYFzo3FZta33L5oros0M/vMzL42sxVm9r+B7TF3bhyhLqr/3HDOVeuL0q6g\ntUAGUBtYApxW3Z/r5Qv4DmhSYdufgAcDy78Fngksnx6ok9qBOloLxHn9HY7ju/cEOgHLj/G7//BX\n53zg3MDydKCP198tRHUxHBhaSdlor4vmQMfAcgNKb+g8LRbPjSPURbWfG+Fo4ZfdvOWcOwj8cPNW\ntKs4VLXsBrXAvz8PLF8OTHDOHXSlN7itpbTOaiTn3BdAToXNR/PdzzOzE4GGzrn5gXJjy72nxjhM\nXcBPzw2I/rrY5pxbEljOo/TmzZbE4LlxhLqAaj43wpHwK7sxq+VhykYLB3xiZgvN7LbAtvJ3H2cD\nqYHlFpTWyQ+isX6O9rtX3L6Z6KqTe8xsqZmNLteFETN1ERj11wmYR4yfG+Xq4svApmo9N8KR8GPx\nqnB351wnSieUu8vMepbf6Ur//jpSvURtnQXx3aPdq8BJQEdgKzDS23DCy8waAP8A7nXO7Su/L9bO\njUBdTKK0LvIIw7kRjoS/GSj/nLw0Dv2tFHWcc1sD/+4A3qe0iybbzJoDBP4U2x4oXrF+WgW2RZOj\n+e6bAttbVdgeFXXinNvuAoA3+LH7LurrwsxqU5rsxznnPghsjslzo1xdjP+hLsJxboQj4ZfdvGVm\nCZTevDUlDJ/rCTOrb2YNA8uJwCXAckq/802BYjcBP5zwU4BrzSzBzE4C2lF6ISaaHNV3d85tA/aa\n2XlmZsCgcu+p0QJJ7QdXUHpuQJTXRSD20cBK59wL5XbF3LlxuLoIy7kRpqvSfSm9Er0WGObFlfFw\nvSj9k2xJ4LXih+8LNAE+Ab4BPgaSyr3noUDdrAIu9fo7HOf3n0DpXdmFlF67GXIs3x3oHDjh1wIv\nev29QlQXt1B6YW0ZsDTww5kaI3XRAygJ/FwsDrz6xOK5cZi66BuOc0M3XomIxAg9/05EJEYo4YuI\nxAglfBGRGKGELyISI5TwRURihBK+iEiMUMIXEYkRSvgiIjHi/wFBw9+1fR87WgAAAABJRU5ErkJg\ngg==\n",
       "text": [
        "<matplotlib.figure.Figure at 0x9b5fb70>"
       ]
      }
     ],
     "prompt_number": 12
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "A maximum error of 0 across a small input set is promising, however I got in touch with a friend to check, and he promtly came back with a proof!\n",
      "\n",
      "---\n",
      "\n",
      "All credit to **Jonah Schreiber** for the below proof:\n",
      "\n",
      "$$\\sum_{x=1}^{n}{x^2}=\\frac{n^3}{3}+\\frac{n^2}{2}+\\frac{n}{6}$$\n",
      "\n",
      "\n",
      "\n",
      "**Base**\n",
      "\n",
      "Here, we show that the formula is correct for $n=1$. On the left-hand side, we have $1$, and on the right-hand side, we have $\\frac{1^3}{3}+\\frac{1^2}{2}+\\frac{1}{6}=1$, so the base case is true.\n",
      "\n",
      "\n",
      "**Assumption**\n",
      "\n",
      "Assume that \n",
      "\n",
      "$$\\sum_{x=1}^{n}{x^2}=\\frac{n^3}{3}+\\frac{n^2}{2}+\\frac{n}{6}$$\n",
      "\n",
      "is true.\n",
      "\n",
      "**Induction**\n",
      "\n",
      "\n",
      "Show then that it is true for $n+1$, that is,\n",
      "\n",
      "$$\\sum_{x=1}^{n+1}{x^2}=\\frac{(n+1)^3}{3}+\\frac{(n+1)^2}{2}+\\frac{n+1}{6}$$\n",
      "\n",
      "Let us break out the last term on the left-hand side, and expand the right-hand side:\n",
      "\n",
      "$$\\sum_{x=1}^{n}{x^2}+(n+1)^2=\\frac{n^3+3n^2+3n+1}{3}+\\frac{n^2+2n+1}{2}+\\frac{n+1}{6}$$\n",
      "\n",
      "We already know the sum on the left-hand side, which we insert.\n",
      "\n",
      "$$\\frac{n^3}{3}+\\frac{n^2}{2}+\\frac{n}{6}+n^2+2n+1=\\frac{n^3+3n^2+3n+1}{3}+\\frac{n^2+2n+1}{2}+\\frac{n+1}{6}$$\n",
      "\n",
      "Collecting terms, we get\n",
      "\n",
      "$$\\frac{n^3}{3}+\\frac{3n^2}{2}+\\frac{13n}{6}+1=\\frac{n^3}{3}+\\frac{3n^2}{2}+\\frac{13n}{6}+1$$ \n",
      "\n",
      "The two sides are equal, so the formula is correct. \n",
      "\n",
      "\n",
      "Thanks again to Jonah Schreiber for the above proof.\n",
      "\n",
      "---\n",
      "\n",
      "\n",
      "See http://www.trans4mind.com/personal_development/mathematics/series/sumNaturalSquares.htm for several derivations of this formula.\n",
      "\n",
      "\n",
      "---\n",
      "\n",
      "And so, finally, \n",
      "\n",
      "**Method 2: Arithmetic **\n",
      "\n",
      "Complexity: O(1)"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def squareDiff2(x):\n",
      "    sumSquares = round(1./6 * x + 1./2 * pow(x, 2.) + 1./3 * pow(x, 3.))\n",
      "    squareSum = pow(x*(x+1)/2., 2)\n",
      "    return squareSum - sumSquares\n",
      "\n",
      "squareDiff2(100)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 13,
       "text": [
        "25164150.0"
       ]
      }
     ],
     "prompt_number": 13
    }
   ],
   "metadata": {}
  }
 ]
}