frog-jumping.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#  The Frog Problem\n",
    "\n",
    "https://www.youtube.com/watch?v=ZLTyX4zL2Fc&t=188s\n",
    "\n",
    "This is my solution to Matt Parker's (@standupmaths) problem, or the problem given to Timandra Harkness about a frog that is crossing the river.  There are nine lily pads between the frog and the opposite bank, so the frog needs at most ten hops to cross the river.  The frog only moves forwards, and at any time she selects the lily pad to jump to, or the opposite bank directly, equally at random.  The she jumps there.  Once there, she selects the next lily pad, or the opposite bank, at random and jumps again.  \n",
    "\n",
    "On average, how many jumps are needed to cross the river?  Is there an explicit formula?  How does this vary for different numbers of lily pads? "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## My solution\n",
    "\n",
    "Let $J_n$ denote the expected number of hops needed for $n$ lily pads between the two river banks.  So we have that $J_0 = 1$, as the frog has no choice but to jump directly across.  We can calculate that \n",
    "$$J_1 = \\frac{1}{2}\\cdot 1 + \\frac{1}{2}(1 + J_0) = \\frac{3}{2}.$$\n",
    "(Either the frog jumps directly, and is done, or jumps the the lily pad in the middle fo the banks, and then we are back to the initial case.)  \n",
    "\n",
    "Similarly, we have\n",
    "$$J_2 = \\frac{1}{3}\\cdot 1 + \\frac{1}{3}(1+J_1) + \\frac{1}{3}(1+J_0).$$\n",
    "\n",
    "In general, for $n \\geq 1$, we can write that \n",
    "$$J_n = \\frac{1}{n+1}\\cdot 1 + \\frac{1}{n+1}(1+J_{n-1}) + \\frac{1}{n+1}(1+J_{n-2}) + \\cdots + \\frac{1}{n+1}(1+J_0),$$\n",
    "since the frog selects a lily pad (or opposite bank) equally at random, and this reduces to a smaller problem.  \n",
    "\n",
    "We can simplify this expression to \n",
    "$$J_n = 1 + \\frac{1}{n+1}\\sum_{k=0}^{n-1}J_k.$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import matplotlib.pyplot as plt\n",
    "import math\n",
    "import numpy as np\n",
    "from sklearn.linear_model import LinearRegression"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1,\n",
       " 1.5,\n",
       " 1.8333333333333333,\n",
       " 2.083333333333333,\n",
       " 2.283333333333333,\n",
       " 2.4499999999999997,\n",
       " 2.5928571428571425,\n",
       " 2.7178571428571425,\n",
       " 2.8289682539682532,\n",
       " 2.9289682539682538,\n",
       " 3.0198773448773446,\n",
       " 3.1032106782106776,\n",
       " 3.1801337551337547,\n",
       " 3.251562326562326,\n",
       " 3.318228993228993,\n",
       " 3.380728993228993,\n",
       " 3.4395525226407573,\n",
       " 3.495108078196313,\n",
       " 3.5477396571436812,\n",
       " 3.5977396571436815,\n",
       " 3.645358704762729,\n",
       " 3.6908132502172744,\n",
       " 3.7342915110868398,\n",
       " 3.7759581777535063,\n",
       " 3.8159581777535068,\n",
       " 3.854419716215045,\n",
       " 3.891456753252082,\n",
       " 3.927171038966368,\n",
       " 3.9616537975870574,\n",
       " 3.994987130920391,\n",
       " 4.02724519543652,\n",
       " 4.05849519543652,\n",
       " 4.08879822573955,\n",
       " 4.118209990445433,\n",
       " 4.146781419016861,\n",
       " 4.17455919679464,\n",
       " 4.201586223821667,\n",
       " 4.227902013295351,\n",
       " 4.253543038936376,\n",
       " 4.278543038936377,\n",
       " 4.302933282838815,\n",
       " 4.326742806648339,\n",
       " 4.349998620601827,\n",
       " 4.3727258933290996,\n",
       " 4.394948115551322,\n",
       " 4.416687245986104,\n",
       " 4.437963841730785,\n",
       " 4.458797175064118,\n",
       " 4.479205338329424,\n",
       " 4.499205338329425,\n",
       " 4.51881318146668,\n",
       " 4.538043950697449,\n",
       " 4.55691187522575,\n",
       " 4.575430393744268,\n",
       " 4.593612211926087,\n",
       " 4.61146935478323,\n",
       " 4.629013214432352,\n",
       " 4.646254593742697,\n",
       " 4.66320374628507,\n",
       " 4.679870412951736,\n",
       " 4.696263855574688,\n",
       " 4.712392887832753,\n",
       " 4.728265903705768,\n",
       " 4.743890903705768,\n",
       " 4.759275519090384,\n",
       " 4.774427034241898,\n",
       " 4.789352407376226,\n",
       " 4.804058289729168,\n",
       " 4.818551043352356,\n",
       " 4.83283675763807,\n",
       " 4.846921264680324,\n",
       " 4.860810153569211,\n",
       " 4.874508783706198,\n",
       " 4.888022297219711,\n",
       " 4.901355630553045,\n",
       " 4.9145135252898875,\n",
       " 4.927500538276901,\n",
       " 4.9403210510974125,\n",
       " 4.952979278945513,\n",
       " 4.965479278945514,\n",
       " 4.977824957957859,\n",
       " 4.990020079909079,\n",
       " 5.002068272680163,\n",
       " 5.013973034584925,\n",
       " 5.025737740467278,\n",
       " 5.037365647444022,\n",
       " 5.048859900317585,\n",
       " 5.060223536681222,\n",
       " 5.071459491737401,\n",
       " 5.082570602848513,\n",
       " 5.093559613837524,\n",
       " 5.104429179054915,\n",
       " 5.1151818672269584,\n",
       " 5.125820165099299,\n",
       " 5.136346480888772,\n",
       " 5.146763147555439,\n",
       " 5.157072425905954,\n",
       " 5.167276507538607,\n",
       " 5.177377517639617,\n",
       " 5.187377517639617,\n",
       " 5.197278507738627]"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "jumps = [1,1.5]\n",
    "\n",
    "lilypads = 100\n",
    "\n",
    "for n in range(2, lilypads+1):\n",
    "    jumps.append(1 + 1/(n+1)*sum(jumps))\n",
    "\n",
    "jumps"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2.9289682539682538"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#  The problem in the video has nine lilypads, so we want the appropriate value here.\n",
    "jumps[9]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "What does the graph of this function look like?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAW4AAAD8CAYAAABXe05zAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDMuMC4zLCBodHRwOi8vbWF0cGxvdGxpYi5vcmcvnQurowAAHORJREFUeJzt3Xl8VXeB9/HPLwnZd7JvhIQAYSlLAxRoaS21dq9al7EdrbUWnfE1tlrH0afjM6M+zuPMa57p6LzUsVrb2moX22qdWhfaSjdKS1gKhEASwpI9Nws3+3bv7/njXhArkAC5OXf5vl+vvJKbHML3cODLye/8zvkZay0iIhI6opwOICIi50bFLSISYlTcIiIhRsUtIhJiVNwiIiFGxS0iEmJU3CIiIUbFLSISYlTcIiIhJiYQ3zQrK8uWlpYG4luLiISlHTt2dFlrs6eybUCKu7S0lOrq6kB8axGRsGSMOTrVbTVUIiISYlTcIiIhRsUtIhJiVNwiIiFGxS0iEmJU3CIiIUbFLSISYgIyj1tEJBJYa2nvG+FQ5yCNXQMMjXn47OXlAf99VdwiIpMYGfdwuGuQQ66BkyV9yDVAo2uQoTHPye1yUuL4zIYyjDEBzaPiFhHxOz40RkPnwMm3Q64BGlwDNPcOc2JddWOgIC2B8pxkVpVmUpadTHlWEuU5yeSkxAW8tEHFLSIRxlqLq3+Uen8513f2U9/hK+mugbGT28XGRFGWlcSyonQ+uKKI8pxk5mUnMzcriYTYaAf3QMUtImHKWktH3yj1nf3UdQzQ4C/o+s4B3MPjJ7dLiY9hXk4yVy7MYV5Osu8tO4XCjASiowJ/9nw+VNwiEvK6Bkapa++nrqOfgx0D1Hf4Pu4bmTi5TXriLObnpHDDRflU5CRTkZvCvBkc3phOKm4RCRn9I+PUdQxw8ERJ+993D/5piONEQd+4rID5uSlU5CYzPzeF2UmxIVfQZzKl4jbGHAH6AQ8wYa2tCmQoEYls4x4vh7sGOdDez4G2Pg6293OgvZ+W48Mnt0mKjWZ+XgpXVeZSkZvMwrxU5uclk50cemfQ5+pczrjfY63tClgSEYlIXQOjHGjrp7atj9r2Pg609dPQOcCYxwtATJShLDuJlXMyuHVNCQtyU1iQl0JhegJRQToGHWgaKhGRGTHh8dLYNUhtWx/72/qo9Ze1q3/05Da5qXEszEvlsoosKvNTWZCXQnl2MrExusn7VFMtbgv8wRhjgR9aax8IYCYRCXGDoxMcaO+jprWP/a2+oj7Q3s/YhO8sOjY6ink5yWyoyKYyP4VF+akszE8lMynW4eShYarFvd5a22qMyQE2G2MOWGtfPXUDY8wmYBNASUnJNMcUkWDVMzhGTaubfS191LS62d/ax+HuwZM3rKQnzmJRfiq3r51DZX4qlfmpzMtJZla0zqLPl7En/nSn+guM+WdgwFr772fapqqqymrNSZHw09k/wr4WX0nvbXFT0+Km1T1y8uuF6QksLkhlcUEaiwpSWVyQSn5afNhfLJwOxpgdU534MekZtzEmCYiy1vb7P74a+MYFZhSRINfZP8LeZjd7W9zsa/G97+jzjUcbA3OzkqgqzWRJoa+oFxekkp6ooY6ZMJWhklzgl/7/MWOAn1trfxfQVCIyo44PjbGn2c2e5uP+927a+3xn0sZAeXYy68qzWFKYxtJC39l0cpzmNjhl0j95a20jsGwGsojIDBge81DT6mZ303He8Zf10e6hk18vy0piTVkmS/0lvbgwTSUdZHQ0RMKY12tpcA2w+9hxdjUd552m4xzs6Mfj9V3bKkiL56KidD66qpjlReksKUojNX6Ww6llMipukTDSMzjG7qZedh07zq5jvqLuH/U9ryMlPoZlRen8zeXlLCtOZ1lxGjkp8Q4nlvOh4hYJUR6v5WB7PzuO9bLraC87j/VyxD/kER1lWJiXws0rClhenMHy4nTKspIi9k7DcKPiFgkRfSPj7Dp2nB1He9lxtIfdx44z6F99JSs5jpUl6Xx0VQkrStK5qCiNxFj98w5XOrIiQarl+DDVR3rYfqSH6iO9HOzox1qIMrAwL5UPriyiqjSDlSUZFGUkaK50BFFxiwSBExcR3z7sK+rth3tO3tiSFBvNyjkZXLMkj6o5mSwvSdcsjwinoy/iAI/Xsr+1j7cOd58s694h36os2SlxrC7NZFNpBlWlmSzMSyFGt4fLKVTcIjNgwuOlprWPbY3dbGvspvpI78nZHnNmJ3JVZS6r5mayZm4mJZmJGvaQs1JxiwTAiTPqNxu7ePNQN9uP9DLgL+qy7CRuWFbAJWWZrJ6bSX5agsNpJdSouEWmgbWWhs4B3mjoYush31n1ifUOy7KTuHl5AZeUzWZNWabmTssFU3GLnKc29zCv13fxRkMXbxzqPrkgQElmItctzWdt+WwuKZtNbqqKWqaXiltkigZGJ9h2qJvX6l281tBFo2sQgKzkWNaVZ7F+3mzWlWdRnJnocFIJdypukTPwei17W9y8Vu/i1boudh7rZcJriZ8VxZq5s7l1dQmXVmSxIDdFFxNlRqm4RU7RNTDKq3UuXqlz8Vp9Fz2DYwAsKUzlrg1lXFaRxcVzMoiLiXY4qUQyFbdENI/X8k7zcbYc6GRLnYs9zW7AN/xxxfxsNszP5tKKLLKS4xxOKvInKm6JOO7hcV6tc/HygU5eqXPRMzhGlIEVJRl86er5XD4/h8UFqXogkwQtFbdEhMNdg7y4v4OXDnSw/UgvHq8lI3EWl8/P5j0Lc7h8fraW3ZKQoeKWsOT1WnY19fKH/R28uL+DQ/4ZIAtyU/jMhjI2VuawvDiDaJ1VSwhScUvYGJ3wsLWhmz/sb2fz/k66BkaJiTJcUjabj18yh42VuZqqJ2FBxS0hbWB0gi0HO/ndvna2HHQxMDpBclwMly/I5upFuVyxIIe0BC3FJeFFxS0hxz08zku1Hbywt51X612MTXjJSo7lxmX5XL04j3XlszVdT8KailtCQt/IOJtrOvjN3jZeq3cx7rHkpcZz6+oSrl2SR1VppsarJWKouCVoDY5O8GJtB//zThuv1rkY83gpSIvn9rWlXLs0nxXF6ZqyJxFJxS1BZXTCwysHXTz3Tisv1XYwMu4lLzWej6+dw/UX+cpat5dLpFNxi+O8XsvbR3r41a4WXtjbRt/IBJlJsXz44mJuXFZA1ZwMnVmLnELFLY5p6OznmZ0tPLerhVb3CEmx0bxvcR43LS9g/bwsZmm5LpHTUnHLjOoZHOPXu1t4dlcLe5rdREcZNlRk8Q/XLuTqRXkkxGo2iMhkVNwScBMeL6/Wu/hFdTMv1nYw7rEsyk/lazcs4qZlBWSn6AFOIudCxS0Bc6RrkKeqm3hmZzMdfaPMTorlE2tL+dDFRVTmpzodTyRkqbhlWo2Me/h9TTtPvN3Em43dRBl4z4IcvnFzMVcuzNG4tcg0UHHLtDjcNcjP3zrK0zua6R0apzgzgb9/3wI+dHGR1lwUmWYqbjlvEx4vL9Z28Oi2o7zR0E1MlOG9i3K5dU0J68uzNIVPJEBU3HLOugZGefytY/z87WO0uUcoTE/gS1fP5yNVxeTo7Fok4FTcMmV7m908tPUwz7/TxpjHy2UVWXz9psVsrMzVc0JEZpCKW87K47Vs3t/Og68fZvuRXhJjo/nY6mI+sa6U8uxkp+OJRCQVt5zW4OgET1U38ZM3DtPUM0xRRgL/eH0lH1lVTGq8nm8t4iQVt/yZzv4RHtl6hMe2HcM9PE7VnAzuu66S9y7K03CISJBQcQsAR7sHeeDVRn6xo5lxj5drFudx14YyVpZkOB1NRN5lysVtjIkGqoEWa+0NgYskM+lgez/f+2MDz+9pJSYqilsuLmLThjLmZiU5HU1EzuBczrjvBmoB3ascBvY2u/mvl+v5w/4OkmKjueuyMu68dK6m84mEgCkVtzGmCLge+BbwxYAmkoDa2+zmOy/V8WJtJ6nxMdy9sYI71peSnhjrdDQRmaKpnnH/J/BlICWAWSSAalrd3L/ZV9hpCbO4973zuX19qWaIiISgSYvbGHMD0Gmt3WGMueIs220CNgGUlJRMW0C5MA2dA9z/Yh2/2dNGSnwMX3zvfD6pwhYJaVM5414P3GSMuQ6IB1KNMY9Za//61I2stQ8ADwBUVVXZaU8q56TNPcx3XqznqeomEmZF83dXzuPTl5aRlqjCFgl1kxa3tfarwFcB/GfcX3p3aUvwcA+P8/0tDTz8xhGshU+um8vn3lPO7GQtViASLjSPO0yMTXh5bNtRvvtyPe7hcT6wopAvXDWf4sxEp6OJyDQ7p+K21m4BtgQkiZwXay2b93fwLy/UcqR7iEvnZfG/rqtkUYFmbYqEK51xh7CD7f184/ka3mjoZl5OMg/dsYor5mdjjG5NFwlnKu4Q5B4e5/7NdTy67Sgp8TF8/abF3LqmRMuCiUQIFXcIsdbyzM4Wvv3bWroHx7htTQlfunqBbp4RiTAq7hBR39HPfb/ax9uHe1hZks7Dd6xmSWGa07FExAEq7iA3Mu7hv16u54evNJIUF8O3P7iUj1QVaz1HkQim4g5ibzV289Vn99LYNcgHVxZy33WVmo8tIiruYDQwOsH/faGWn711jKKMBB69czWXVWQ7HUtEgoSKO8hsPdTFl5/eQ8vxYe68dC73Xj2fxFgdJhH5EzVCkBge8/Dt39byyJtHmZuVxNOfXcvFczKdjiUiQUjFHQT2Nru5+8ldNLoGuWN9KV9+30ISYqOdjiUiQUrF7SCP1/Lfrxzi/s11ZCXH8bNPr2H9vCynY4lIkFNxO6Szb4R7ntzN1kPdXL80n299YIlupBGRKVFxO+CVOhdffHI3g2MT/NstF/HhqiI9X0REpkzFPYM8Xst3Xqzjuy83sCA3hSduvYSKXK0GJyLnRsU9Q3oGx7j7iV28Vt/Fhy8u4pvvX0L8LF2AFJFzp+KeAXub3Xzm0Wq6Bsf411uW8tFVWpNTRM6fijvAntvdwpef3kNWchzPfHYdS4v0YCgRuTAq7gDxeC3/9vsD/PCVRlbPzeQHt63Uc0ZEZFqouANgaGyCu5/Yzeb9Hdy2poR/unExsTFa5EBEpoeKe5p19o1w5yPV1LS6+acbF3HH+rlORxKRMKPinkb1Hf188qHt9A6N8aNPVLGxMtfpSCIShlTc02TH0V4+9fB2YmOieOoza7U6jYgEjIp7Grx8oIO//dlO8lLjefTONRRnJjodSUTCmIr7Aj23u4UvPvUOlfkpPHzHarI0c0REAkzFfQGeqm7iH57Zw6rSTB68vYqU+FlORxKRCKDiPk+PbTvKP/5qH5dVZPHAx6v0/GwRmTEq7vPw6JtH+NpzNWxcmMP3blupZ46IyIxScZ+jJ7cf42vP1XBVZS7fv22lbqwRkRmn1jkHv9zVzFee3cvl87P53m0rVNoi4gg1zxT9bl8b9z71DuvKZ/PDj19MXIyGR0TEGSruKXjzUDeff3w3K0oy+NEnqjSmLSKOUnFPYn9rH5t+Ws2c2Yk8eHsVibG6LCAizlJxn0VTzxC3P/Q2yfExPPKp1VrMV0SCgor7DPpHxrnzke2Mjnv46adWU5Ce4HQkERFA0wFPa8Lj5e8e30Wja5Cffmq1FvQVkaCi4j6Nb71Qy5aDLv7lA0tZNy/L6TgiIn9GQyXv8sTbx3jojSN8av1cbl2jRX1FJPiouE+xp/k4//u5Gi6ryOK+6yudjiMiclqTFrcxJt4Y87Yx5h1jTI0x5uszEWym9Q6O8TeP7SQ7JY7v/tUKoqOM05FERE5rKmPco8CV1toBY8ws4HVjzG+ttdsCnG3GeL2We57cjat/lF98di0ZSZr2JyLBa9LittZaYMD/cpb/zQYy1Ez7/pYGXqlz8a0PLGFZcbrTcUREzmpKY9zGmGhjzG6gE9hsrX0rsLFmzq5jvdz/Yj03LSvg1tW6GCkiwW9KxW2t9VhrlwNFwGpjzJJ3b2OM2WSMqTbGVLtcrunOGRADoxPc8+Ru8lLj+eb7l2CMxrVFJPid06wSa+1xYAtwzWm+9oC1tspaW5WdnT1N8QLr67+uoalniPs/upy0BC07JiKhYSqzSrKNMen+jxOAq4ADgQ4WaC/sbeMXO5r53HvmsXpuptNxRESmbCqzSvKBR4wx0fiK/ilr7fOBjRVYvYNjfO1X+7ioKI3Pb6xwOo6IyDmZyqySPcCKGcgyY775/H7cw+M89uk1zIrWPUgiEloirrW2HOzk2V0t/O0V5VTmpzodR0TknEVUcQ+MTnDfL/cxLyeZz105z+k4IiLnJaKeDvj//nCQVvcwT392rdaMFJGQFTFn3HUd/fz0zaN8bHUJF8/RLBIRCV0RUdzWWr7xP/tJio3mS1cvcDqOiMgFiYji3ry/g9cbuvjCe+eTqQdIiUiIC/viHhn38H9+U0tFTjJ/fckcp+OIiFywsL84+ZM3DnOsZ4jH7tScbREJD2HdZO6hcX6w5RAbF+ZwaYXWjhSR8BDWxf2j1xrpH5ngXl2QFJEwErbF3TUwyk/eOMwNF+WzqEB3SIpI+Ajb4v7vLYcYGfdwz1XznY4iIjKtwrK4290jPLrtKB9cWcS8nGSn44iITKuwLO7vb2nA47XcrUe2ikgYCrvi7h4Y5cntTdyysojizESn44iITLuwK+5Htx1ldMLLXRvmOh1FRCQgwqq4R8Y9PPrmUTYuzGFeTorTcUREAiKsivvZnS10D45x14Yyp6OIiARM2BS312v58WuNLC1MY40W/xWRMBY2xf3SgU4auwa5a0MZxhin44iIBEzYFPdPXj9MYXoC1y3JczqKiEhAhUVxH+ka5M3Gbm5dU0KMngAoImEuLFruqeomogzcsrLI6SgiIgEX8sU94fHy9I5mrliQQ15avNNxREQCLuSL+5U6F539o3x0VbHTUUREZkTIF/eT25vISo7jyoU5TkcREZkRIV3cnf0jvHSgk1tWFmpZMhGJGCHdds/ubMHjtXy4SsMkIhI5Qry4m7l4ToaeuS0iESVki7uhc4C6jgFuvCjf6SgiIjMqZIv79zXtAFyzRMUtIpElZIv7t/vaWFGSrrnbIhJxQrK4m3qG2NfSxzWL9VwSEYk8IVncJ4ZJrtUwiYhEoJAs7t/ua2dRfiols7WmpIhEnpAr7o6+EXYc7eVaPb5VRCJUyBX3n2aTqLhFJDKFXHH/bl875dlJVORqMWARiUyTFrcxptgY80djTK0xpsYYc/dMBDud4TEP1Ud62ViZ61QEERHHxUxhmwngXmvtTmNMCrDDGLPZWrs/wNn+QvXRHsY8XtaVz57p31pEJGhMesZtrW2z1u70f9wP1AKFgQ52OlsPdRMTZVhVqlXcRSRyndMYtzGmFFgBvBWIMJPZeqib5cXpJMVN5QcFEZHwNOXiNsYkA88A91hr+07z9U3GmGpjTLXL5ZrOjAD0jYyzt/m4hklEJOJNqbiNMbPwlfbPrLXPnm4ba+0D1toqa21Vdnb2dGYE4O3GHrwW1pZnTfv3FhEJJVOZVWKAB4Faa+1/BD7S6W091E1cTBQrStKdiiAiEhSmcsa9Hvg4cKUxZrf/7boA5/oLWw91sao0k/hZ0TP9W4uIBJVJr/JZa18HzAxkOaOugVEOtPfz9+8rcDKGiEhQCIk7J7c1dgPowqSICCFS3FsPdZMcF8PSwjSno4iIOC4kintbYzer52YSEx0ScUVEAirom7B/ZJxG1yArijWbREQEQqC497f67vVZomESEREgBIq7xl/ciwtTHU4iIhIcgr6497W6yU6JIydFq7mLiEAIFHdNSx9LCnS2LSJyQlAX98i4hwbXAIsLNL4tInJCUBf3gfZ+PF7LEo1vi4icFNTFXdPqBtAZt4jIKYK6uPe19JGWMIuijASno4iIBI2gLu6aVjeLC1LxPVlWREQgiIt73OPlQHu/brwREXmXoC3uhs4Bxia8LNZUQBGRPxO0xX3yjkldmBQR+TNBW9z7WtwkxkYzNyvJ6SgiIkElaIu7ptVNZX4q0VG6MCkicqqgLe6D7f1U5qc4HUNEJOgEZXG7h8bpG5mgdLaGSURE3i0oi7updwiAooxEh5OIiASfoCzuYz2+4i7O1B2TIiLvFpTF3XSyuHXGLSLybsFZ3L1DpCXMIjV+ltNRRESCTnAWd8+whklERM4gOIu7d4hiXZgUETmtoCtur9fS3Dus8W0RkTMIuuJ2DYwyNuGlWM/gFhE5raAr7hMzSop0xi0iclrBV9z+m280xi0icnpBV9zHuocBtFyZiMgZBF1xN/UOkZsaR/ysaKejiIgEpeAr7h5NBRQROZugK25NBRQRObugKu5xj5c297CmAoqInEVQFXfr8WG8VlMBRUTOJqiKu6nHN6NEY9wiImcWXMXdq+dwi4hMZtLiNsb8xBjTaYzZF+gwTT1DxEQZ8tNU3CIiZzKVM+6HgWsCnAPwrXxTkJ6gld1FRM5i0uK21r4K9MxAFpp69RxuEZHJBNUYd7NuvhERmdS0FbcxZpMxptoYU+1yuc7513u8lsvnZ7OmLHO6IomIhCVjrZ18I2NKgeettUum8k2rqqpsdXX1hSUTEYkgxpgd1tqqqWwbVEMlIiIyualMB3wceBNYYIxpNsbcGfhYIiJyJjGTbWCt/dhMBBERkanRUImISIhRcYuIhBgVt4hIiFFxi4iEGBW3iEiImdINOOf8TY1xAUfP85dnAV3TGCcUaJ/DX6TtL2ifz9Uca232VDYMSHFfCGNM9VTvHgoX2ufwF2n7C9rnQNJQiYhIiFFxi4iEmGAs7gecDuAA7XP4i7T9Be1zwATdGLeIiJxdMJ5xi4jIWQRNcRtjrjHGHDTGNBhjvuJ0nkAwxhQbY/5ojKk1xtQYY+72fz7TGLPZGFPvf5/hdNbpZoyJNsbsMsY873891xjzln+fnzTGxDqdcToZY9KNMU8bYw74j/facD/Oxpgv+P9e7zPGPG6MiQ+343y6xdPPdFyNz3f9nbbHGLNyunIERXEbY6KB7wHXAouAjxljFjmbKiAmgHuttZXAJcDn/Pv5FeAla20F8JL/dbi5G6g95fW/Avf797kXCLfHBX8H+J21diGwDN++h+1xNsYUAp8HqvwLrkQDf0X4HeeH+cvF0890XK8FKvxvm4AfTFeIoChuYDXQYK1ttNaOAU8ANzucadpZa9ustTv9H/fj+8dciG9fH/Fv9gjwfmcSBoYxpgi4Hvix/7UBrgSe9m8SVvtsjEkFNgAPAlhrx6y1xwnz44zvMdEJxpgYIBFoI8yO8xkWTz/Tcb0Z+Kn12QakG2PypyNHsBR3IdB0yutm/+fCln85uBXAW0CutbYNfOUO5DiXLCD+E/gy4PW/ng0ct9ZO+F+H2/EuA1zAQ/7hoR8bY5II4+NsrW0B/h04hq+w3cAOwvs4n3Cm4xqwXguW4jan+VzYTncxxiQDzwD3WGv7nM4TSMaYG4BOa+2OUz99mk3D6XjHACuBH1hrVwCDhNGwyOn4x3VvBuYCBUASvqGCdwun4zyZgP09D5bibgaKT3ldBLQ6lCWgjDGz8JX2z6y1z/o/3XHiRyj/+06n8gXAeuAmY8wRfENgV+I7A0/3/0gN4Xe8m4Fma+1b/tdP4yvycD7OVwGHrbUua+048CywjvA+ziec6bgGrNeCpbi3AxX+K9Cx+C5q/NrhTNPOP7b7IFBrrf2PU770a+B2/8e3A8/NdLZAsdZ+1VpbZK0txXdcX7bW3gb8EfiQf7Nw2+d2oMkYs8D/qY3AfsL4OOMbIrnEGJPo/3t+Yp/D9jif4kzH9dfAJ/yzSy4B3CeGVC6YtTYo3oDrgDrgEHCf03kCtI+X4vtRaQ+w2/92Hb4x35eAev/7TKezBmj/rwCe939cBrwNNAC/AOKczjfN+7ocqPYf618BGeF+nIGvAweAfcCjQFy4HWfgcXxj+OP4zqjvPNNxxTdU8j1/p+3FN+NmWnLozkkRkRATLEMlIiIyRSpuEZEQo+IWEQkxKm4RkRCj4hYRCTEqbhGREKPiFhEJMSpuEZEQ8/8B9uH9+l8UAqkAAAAASUVORK5CYII=\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "plt.plot(range(lilypads+1),jumps);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This graph looks generally logarithmic in nature."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAW4AAAD8CAYAAABXe05zAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDMuMC4zLCBodHRwOi8vbWF0cGxvdGxpYi5vcmcvnQurowAAHJxJREFUeJzt3Xd8nFed7/HPUZfVrWY1W65yr3JJTCq+pJLQdkMgbIgBZ2FfS2ApF9h79wLLBfZ1ucAuy2bJJZtCSIEklPWShPQQiIvcm+QiyZZkj3oZdWnm3D9m7BiwLdnW6Hmeme/79ZqXZsaPpN/zOtLXR+c55znGWouIiHhHnNMFiIjIxVFwi4h4jIJbRMRjFNwiIh6j4BYR8RgFt4iIxyi4RUQ8RsEtIuIxCm4REY9JiMQXzcvLs+Xl5ZH40iIiUWnHjh1t1tr88RwbkeAuLy+nqqoqEl9aRCQqGWOOj/dYDZWIiHiMgltExGMU3CIiHqPgFhHxGAW3iIjHKLhFRDxGwS0i4jERmcctIhILRgJBGjsHqG/v40R7PwMjAf76mtkR/74KbhGRCxgeDdLY2U99ex/1beGP7f3Ut/XR1DVAIPj2vr35Gcnce/UsjDERrUnBLSIxLxC0NHUOUNfeR11rL/Xt/dS29Z0znDOSE5iRN4WlpVnctqyYGblTmJmXxvTcKeSnJ0c8tEHBLSIxwlpLW+8wdW191LX1UtvWR21rH3VtoWGO4UDwzLHpyQmUh8P59uXFlOemUZ43hfLcNKamJU1KOF+IgltEosrgSIDj7f3UtvZyrLWX2tY+jrX1Udvai39w9MxxSfFxzMidwqy8NN45v4BZ+WnMzEunPG/yes6XSsEtIp7U0TfMsdZejrb0cqwlFNLHWvto7OznrJENpmWmMCs/jduXFzM7P52ZeWnMykunJCeV+Dj3hvOFKLhFxLWCQcvJ7gGOtoQDOhzUR1t66ewfOXNcSmIcM/PSWVqaxXtWlDA7P+1MSKclR1/MRd8ZiYjnBIKWxs5+jjT3cqSllyMt/jMB3T8cOHNczpRE5hSkc+PiaczOT2dOQTqz89MpyU4lzqO950uh4BaRSRMMWho6+znc3MvhZj9Hmv0cCQf00OjbFwcLM5OZV5jBHavLmFOQzpxwSOemJztYvXsouEVkwllrae4ZoqbZT42vhxpfqBd9pLmXgZG3e9BFWSnMLczgilm5zC1MZ25hBnMK0slMSXSwevdTcIvIZekZHOGwz0+1z0/N6Uezn+6Bt8eg8zOSqSjM4M4105kXDui5hQroS6XgFpFxCQQt9e19HDrVQ/UpP9W+Hqp9fho7B84ck5GcQMW0DG5ZWkRFYQYV0zKYV5jB1LQkByuPPgpuEfkz/sERqn1+Dp7s4dCp0KPa5z8zDh0fZ5iVl8aK6TncuWY686dlML8ok+KsFFfPf44WCm6RGGatxdczyIGmHg6e6uHgydDHEx39Z47JmZLIgqJMPrx2BguKMlhQlMmcgnRSEuMdrDy2KbhFYkQwaDne0c/+pm4OnOzhwMnQx46+4TPHzMxLY3FJJnesLmNhUSYLijIpzHT3KsJYpOAWiUKBoKWurZd9Td3sb+phX1M3B0/20DsUWvKdGG+YV5jBhgUFLCrOYmFxKKTTo3CxSjRSK4l4XDBoqWvvY19jN3sbu9nf1M3+k91nFq6kJMaxoCiT960sYVFxJouKs5hXmEFSgvZR8SoFt4iHWGs52T3InoYu9jR2sbchFNT+cE86OSGOhcWZ/MWqUpaUZrOkJIvZ+WkkxCuko4mCW8TFuvtH2NPYdSaodzd009Y7BISGOxYUZXL7imKWlmSztCyLOfnpCukYoOAWcYmRQJAan59dJzrZdaKL3Q1d1Lb1AWAMzM5P5+p5eSwvy2ZZaTbzizJITtDMjlik4BZxSKt/iJ0nOtl5opNdx7vY29TF4EhonnReehLLy3J4/6pSlpdls6Q0S6sM5QwFt8gkCAQth5v9VB3vZOfxTnYc7zwzVzox3rCoOIs710xn5fQclpdlU5qTqil4cl4KbpEIGBgOsKuhk6r6TqqOd7LreOeZC4j5Gcmsmp7DXetCQb24JEuLWeSiKLhFJkBn3zDb6zvCj072N3UzGrQYAxWFGdy2vJjK8hwqZ0xVb1ou27iC2xhTD/iBADBqra2MZFEibtfiH2RbXQdbazvYVtdBTbMfCO1juKwsi09cPYvV5Tmsmj6VrCkam5aJdTE97uustW0Rq0TExVp6Bnmrtp2tdR1sqW2ntjU02yMtKZ6VM3J497Ii1szMZWmphj0k8jRUInIO7b1DbKnt4A/H2njrrKDOSE5gzcypfHB1GWtn5rKoOFPzpmXSjTe4LfBbY4wFfmStfSCCNYlMut6hUbbVtfPmkXb+cKyNal9o6CM9OYHV5Tl8cHUZV8zKY2Fxpmd3BpfoMd7gXm+tPWmMKQBeNMZUW2vfOPsAY8wmYBPA9OnTJ7hMkYk1Egiyp6GL3x1p4/dH29jd0MVo0JKUEEfljBy+cEMFV8zOZUlJFonqUYvLGGvtxX2CMV8Feq213znfMZWVlbaqquoySxOZWMfb+3jjSBtvHG7lrWPt9A6NYgwsLcli/Zw83jEnj5UzcjRGLY4wxuwY78SPMXvcxpg0IM5a6w8/fxfw9cusUSTi+oZGeetYO68fbuWNI60cbw8teCnJTuXdy4q5am4eV87OJXuKttUSbxnPUEkh8IvwvNME4HFr7fMRrUrkElhrOdbax2s1Lbxa08L2uk6GA0FSE+O5cnYuG9fP5Kq5eczMS9M8avG0MYPbWlsLLJuEWkQu2uBIgC217bxSHQrrho7QxrVzC9K5+8oZXFtRQGV5jm7GJFFF0wHFc1r9Q7xS3cxLh1p480gbAyMBUhLjWD87j3uvns21FfmU5kxxukyRiFFwi+uFhkB6+e3BZl482Mzuhi6sheKsFN6/qoR3Lijkilm5uqgoMUPBLa4UDFp2N3bxwgEfLx5oPnNf6iUlWXx2wzw2LChkQVGGxqolJim4xTVGA0G21Xfw/H4fLxzw0dwzREKc4YrZudyzvpwNCwspykp1ukwRxym4xVEjgSBvHWvnuf2neOFAMx19w6QkxnHtvAJuXDyN6+YXkJWqmzSJnE3BLZNuNBBkS20Hm/ee5PkDPrr6R0hLiuf6BYXcvHga11TkMyVJP5oi56PfDpkUwaBl54lOfr3nJL/Zd4q23mHSkuJ554JCbllaxDXz8nVxUWScFNwSUdW+Hn656yT/ueckTV0DJCfEsWFBIbcuLeK6+QUKa5FLoOCWCdfcM8ivdjfx7M4mqn1+4uMMV83N4/M3zOO/LZxGerJ+7EQuh36DZEIMjgR44YCPp3c08vujbQQtLCvL5mu3LeKWpUXkpSc7XaJI1FBwyyWz1rKroYufVzWyec9J/EOjlGSn8jfXzeG9K0qYlZ/udIkiUUnBLRetvXeIZ3c28bOqBo609JKaGM9NS6bxgVWlrJuZS5w2GhCJKAW3jEswaHmrtp3Ht53gtwd8jAQsK6Zn8+33LeHWZcUatxaZRPptkwvq6Bvm6R0NPL71BPXt/WSlJnLXuhncuWY68woznC5PJCYpuOWcdjd08egf6tm87xTDo0FWl+dw34a53LS4SFP4RBym4JYzhkYDbN5zikfeqmdvYzdpSfHcUVnGXetmUDFNvWsRt1BwCy3+QR7bcoLHtx6nrXeYOQXp/OPti3jvylKNXYu4kH4rY1iNz8+Pf1fLr3afZDgQ5Pr5Bdyzvpx3zMnT7VJFXEzBHWOsDc0O+dHrtbx+uJWUxDjuWF3GPevLNe9axCMU3DEiELS8cMDHv79+jL2N3eSlJ/P5d83jw2tnkJOmXc5FvETBHeVGAkF+uauJ+18/Rm1rH+W5U/jme5fwvpUlmh0i4lEK7ig1NBrg6R2N/Nurx2jqGmBhUSY//NBKblw8jXitbBTxNAV3lBkaDfCzqkbuf/UoJ7sHWV6WzTfes5hrK/J1wVEkSii4o8RIIMgzOxr5wStHaeoaYNWMHL79/qVcNVczRESijYLb44JBy+Z9p/jub2uob+9nWVk233rfEgW2SBRTcHuUtZY3jrTxT89Vc/BUD/OnZfDjv6rknQsKFNgiUU7B7UEHTnbzrd9U8+bRNsqmpvL9O5Zz27Ji3U5VJEYouD2kuWeQ//NCDc/sbCQrNZF/uHUhd62bQVJCnNOlicgkUnB7wOBIgAffrOOHrx5lNGDZdNUsPnXdHLJSE50uTUQcoOB2MWstLx1q4eubD9DQMcANiwr5ys0LmJGb5nRpIuIgBbdLHW/v42v/eZBXqluYV5jO4x9fy5Vz8pwuS0RcQMHtMsOjQX70+jF+8OpRkuLj+B+3LODuK8tJjNc4toiEKLhdZFtdB1/5xT6OtvRyy9Ii/uHWhRRmpjhdloi4jILbBXqHRvn2c4d4bMsJSnNSeeie1VxXUeB0WSLiUuMObmNMPFAFNFlrb41cSbHl9cOtfOXZfZzsHuDj75jJ371rHlOS9P+piJzfxSTEfcAhIDNCtcSUvqFRvvFfh3hi2wnmFKTzzCevZOX0HKfLEhEPGFdwG2NKgVuA/w38XUQrigHb6zv43M/20NDZz73XzOKzG+bp3tgiMm7j7XF/H/gicN6tvo0xm4BNANOnT7/8yqLQSCDIv7x8hH999SilOan87N4rWF0+1emyRMRjxgxuY8ytQIu1docx5trzHWetfQB4AKCystJOWIVRoqGjn08/uYtdJ7r4i1Wl/K/bFmkHdRG5JONJjvXAbcaYm4EUINMY85i19q7IlhY9ntt3ii8+vRcM/ODOFbx7WbHTJYmIh40Z3NbaLwNfBgj3uD+v0B6f4dEg33ruEA/9vp7lZdn84M4VlE2d4nRZIuJx+ls9Qk51D/Cpn+5k14kuNq6fyZdumq+7+InIhLio4LbWvga8FpFKosj2+g4++dgOBkeC3P/hldy0pMjpkkQkiqjHPYGstfx06wm++usDlE2dwpObVjGn4LwTcURELomCe4KMBoJ8ffNBHn3rONdV5PP9D67Q/bJFJCIU3BPAPzjC3z6xi9dqWvnEVTP50k0LiNc2YiISIQruy3Sya4CND2/nSEsv33zvEj60VouPRCSyFNyX4WiLn488uI3ewVEevmc1V83Nd7okEYkBCu5LtON4Jx97ZDsJcXE8ee86FhVnOV2SiMQIBfcleONwK5t+UkVhZgo/2biW6blaVCMik0fBfZFePtTMJx/byeyCdB7duIb8jGSnSxKRGKPgvgjP7TvF3z6xi4XFmTy6cQ3ZU5KcLklEYpCCe5z+a+8pPv3kLpaVZvHwxjVkpmiOtog4Q8E9Di8dbOa+J3exoiybhzeu0e1YRcRRuuvRGN480sanfrqTRcWZPHTPaoW2iDhOwX0BO4538IlHq5iVn8YjG9eQoeEREXEBBfd5HG3xs/HhKoqyUnjs42t1IVJEXEPBfQ4tPYPc/R/bSYyP45GNa8hL15Q/EXEPBfef8A+O8NGHttPZP8xDH12tHWtExHV0pe0sgaDlvid3U9Ps58G7K1lSqmXsIuI+6nGf5Tu/reGV6ha+etsirq0ocLocEZFzUnCH/Wp3E/e/dowPrZ3OR9bNcLocEZHzUnAD+xq7+eLTe1lTPpWvvnuR0+WIiFxQzAd398AIn3p8B7lpSfzbXSu1E7uIuF5MX5y01vKlZ/ZyqmuQp+69QtP+RMQTYrp7+ZMtx3luv48v3FDBqhk5TpcjIjIuMRvc+5u6+cbmQ1xXkc8nrprldDkiIuMWk8E9OBLgs0/tJictkf/7l8uJ047sIuIhMTnG/b2XDnOkpZdHNq5hapruQSIi3hJzPe4dxzv5f2/UcueaMq6Zp13ZRcR7Yiq4B4YDfOHneyjKSuXvb1nodDkiIpckpoZKvvfSYWrb+nj842u1IYKIeFbM9LhrfH4efLOOO9eUceWcPKfLERG5ZDER3NZa/uev9pOZksAXb5jvdDkiIpclJoL7F7ua2FbXwX+/cT45mkUiIh4X9cHdPTDCN39ziOVl2fxlZZnT5YiIXLaov0L3zy8dob1vmIfvWaOFNiISFcbscRtjUowx24wxe4wxB4wxX5uMwiZCQ0c/P9lSzx2VZSwu0W42IhIdxtPjHgKut9b2GmMSgTeNMc9Za7dEuLbL9r0XDxNnDJ/ZMM/pUkREJsyYPW4b0ht+mRh+2IhWNQGqfT38YncTH11fzrSsFKfLERGZMOO6OGmMiTfG7AZagBettVvPccwmY0yVMaaqtbV1ouu8aN95oYb05AQ+ec1sp0sREZlQ4wpua23AWrscKAXWGGMWn+OYB6y1ldbayvx8Z+8BUlXfwUuHWvjra2aTPUXT/0QkulzUdEBrbRfwGnBjRKqZIN998TD5GclsXD/T6VJERCbceGaV5BtjssPPU4ENQHWkC7tUexu7+MOxdjZdNYvUpHinyxERmXDjmVVSBDxijIknFPQ/s9ZujmxZl+5Hr9eSkZLAB9dosY2IRKcxg9tauxdYMQm1XLb6tj6e23+Ke6+ZTUZKotPliIhERFQtef/xm7UkxMVxz5XlTpciIhIxURPcbb1D/LyqkfetLKEgU/O2RSR6RU1wP/qHeoYDQT5xtXZsF5HoFhXBPRII8vi2E1xfUcDs/HSnyxERiaioCO5Xqlto6x3mQ2unO12KiEjERUVwP7W9gcLMZO3aLiIxwfPB7ese5LWaFj6wqpSEeM+fjojImDyfdE/vaCBo0e42IhIzPB3cwaDlqaoGrpydy4zcNKfLERGZFJ4O7rdq22noGOCO1epti0js8HRwP7W9gazURG5YNM3pUkREJo1ng3twJMBLh5q5ZWkRKYm6C6CIxA7PBvfvjrTRPxzgpsXqbYtIbPFscD+/30dmSgLrZuU6XYqIyKTyZHCPBIK8XN3MhgWFJGrutojEGE+m3ra6Drr6R7hBwyQiEoM8GdwvHPCRkhjH1XO1xF1EYo/ngjsYtLxwwMe18wq0p6SIxCTPBfeexi6ae4a4YXGh06WIiDjCc8H9/AEfCXGG6+cruEUkNnkuuF8+1MIVs3PJStVmwCISmzwV3C3+QY629PKOOXlOlyIi4hhPBfe2ug4A1mrRjYjEME8F99baDtKS4llcnOl0KSIijvFWcNe1U1k+VTvdiEhM80wCtvcOcbi5l7WzpjpdioiIozwT3GfGt2dqfFtEYptngntrXQepifEsLc1yuhQREUd5Jri31LZTWZ6juwGKSMzzRAp29g1T7fOzdqbGt0VEPBHc2+o1f1tE5DRPBPfW2g6SE+I0vi0igleCu66dVTNySE7QbVxFRMYMbmNMmTHmVWPMIWPMAWPMfZNR2GnDo0FqfH6WlWVP5rcVEXGthHEcMwp8zlq70xiTAewwxrxorT0Y4doAqGvrYzRomT8tYzK+nYiI643Z47bWnrLW7gw/9wOHgJJIF3Zata8HgHmFCm4REbjIMW5jTDmwAtgaiWLOpcbnJyHOMDs/fbK+pYiIq407uI0x6cAzwGestT3n+PdNxpgqY0xVa2vrhBVY4/MzKz+NpARPXEcVEYm4caWhMSaRUGj/1Fr77LmOsdY+YK2ttNZW5udP3O7r1T4/FdN0G1cRkdPGM6vEAA8Ch6y13418SW/zD47Q1DWgC5MiImcZT497PfAR4HpjzO7w4+YI1wXA4eZeQBcmRUTONuZ0QGvtm4CZhFr+TI3PD6Aet4jIWVx9xa/G10NaUjwl2alOlyIi4hquDu5qn5950zKIi3Okwy8i4kquDW5rLTXNfg2TiIj8CdcGd4t/iK7+ESp0YVJE5I+4NrhPX5icpx63iMgfcX1wz9fiGxGRP+La4K72+cnPSGZqWpLTpYiIuIprg7umuUcXJkVEzsG1wV3f1q87AoqInIMrg7t3aJTeoVGmZaU4XYqIiOu4MribewYBKMxMdrgSERH3cXlwq8ctIvKnFNwiIh7j0uAeAhTcIiLn4tLgHiQtKZ705PFsQi8iEltcGdwtPUMUakaJiMg5uTK4fT2DFGYouEVEzsWVwd3cM6ipgCIi5+G64LbWaqhEROQCXBfcXf0jDAeCGioRETkP1wW3T3O4RUQuyHXBreXuIiIX5rrgbtHiGxGRC3JdcJ/ucReoxy0ick6uC25fzyA5UxJJToh3uhQREVdyXXA39wxpmERE5AJcF9wt/kEFt4jIBbguuLVqUkTkwlwV3KOBIK1+DZWIiFyIq4K7vW+YoNVUQBGRC3FVcGvnGxGRsbkquH3dWjUpIjIWVwV3s1+rJkVExuKq4G7pGSTOQF66etwiIuczZnAbY/7DGNNijNkf6WKaewbJz0gmPs5E+luJiHjWeHrcDwM3RrgOAHxaNSkiMqYxg9ta+wbQMQm10NKjVZMiImNx1Ri3Vk2KiIxtwoLbGLPJGFNljKlqbW296M8PBi3XVhSwakbORJUkIhKVjLV27IOMKQc2W2sXj+eLVlZW2qqqqsurTEQkhhhjdlhrK8dzrKuGSkREZGzjmQ74BPAWUGGMaTTGfCzyZYmIyPkkjHWAtfbOyShERETGR0MlIiIeo+AWEfEYBbeIiMcouEVEPEbBLSLiMeNagHPRX9SYVuD4JX56HtA2geV4gc45+sXa+YLO+WLNsNbmj+fAiAT35TDGVI139VC00DlHv1g7X9A5R5KGSkREPEbBLSLiMW4M7gecLsABOufoF2vnCzrniHHdGLeIiFyYG3vcIiJyAa4JbmPMjcaYGmPMUWPMl5yuJxKMMWXGmFeNMYeMMQeMMfeF359qjHnRGHMk/DHqdpMwxsQbY3YZYzaHX880xmwNn/NTxpgkp2ucSMaYbGPM08aY6nB7XxHt7WyM+Wz453q/MeYJY0xKtLXzuTZPP1+7mpB/CWfaXmPMyomqwxXBbYyJB34I3AQsBO40xix0tqqIGAU+Z61dAKwD/iZ8nl8CXrbWzgVeDr+ONvcBh856/U/A98Ln3AlE2+2C/xl43lo7H1hG6Nyjtp2NMSXAp4HK8IYr8cAHib52fpg/3zz9fO16EzA3/NgE3D9RRbgiuIE1wFFrba21dhh4Erjd4ZomnLX2lLV2Z/i5n9Avcwmhc30kfNgjwHucqTAyjDGlwC3Aj8OvDXA98HT4kKg6Z2NMJnA18CCAtXbYWttFlLczodtEpxpjEoApwCmirJ3Ps3n6+dr1duBRG7IFyDbGFE1EHW4J7hKg4azXjeH3olZ4O7gVwFag0Fp7CkLhDhQ4V1lEfB/4IhAMv84Fuqy1o+HX0dbes4BW4KHw8NCPjTFpRHE7W2ubgO8AJwgFdjewg+hu59PO164RyzW3BLc5x3tRO93FGJMOPAN8xlrb43Q9kWSMuRVosdbuOPvtcxwaTe2dAKwE7rfWrgD6iKJhkXMJj+veDswEioE0QkMFfyqa2nksEfs5d0twNwJlZ70uBU46VEtEGWMSCYX2T621z4bfbj79J1T4Y4tT9UXAeuA2Y0w9oSGw6wn1wLPDf1JD9LV3I9Bord0afv00oSCP5nbeANRZa1uttSPAs8CVRHc7n3a+do1YrrkluLcDc8NXoJMIXdT4tcM1Tbjw2O6DwCFr7XfP+qdfA3eHn98N/Gqya4sUa+2XrbWl1tpyQu36irX2w8CrwAfCh0XbOfuABmNMRfitdwIHieJ2JjREss4YMyX8c376nKO2nc9yvnb9NfBX4dkl64Du00Mql81a64oHcDNwGDgG/L3T9UToHN9B6E+lvcDu8ONmQmO+LwNHwh+nOl1rhM7/WmBz+PksYBtwFPg5kOx0fRN8rsuBqnBb/xLIifZ2Br4GVAP7gZ8AydHWzsAThMbwRwj1qD92vnYlNFTyw3Cm7SM042ZC6tDKSRERj3HLUImIiIyTgltExGMU3CIiHqPgFhHxGAW3iIjHKLhFRDxGwS0i4jEKbhERj/n/18gNiNx7g+QAAAAASUVORK5CYII=\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "plt.plot(range(lilypads+1), [1+math.log(1+i) for i in range(lilypads+1)]);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Fitting a curve\n",
    "\n",
    "Since this looks logarithmic in nature, let's try to fit a curve using linear regression with an engineered feature, i.e. let's fit \n",
    "$$\\log(1 + \\rm{lilypads})$$ \n",
    "versus the number of jumps."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "r = np.linspace(0,lilypads,lilypads+1)\n",
    "\n",
    "X = np.log(r+1).reshape(-1,1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "linreg = LinearRegression()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "LinearRegression(copy_X=True, fit_intercept=True, n_jobs=None, normalize=False)"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "linreg.fit(X,jumps)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([0.95617569])"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "linreg.coef_"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.7614930210085502"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "linreg.intercept_"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.9987889695997566"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "linreg.score(X,jumps)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Given the above it seems that $J_n \\sim \\ln(n+1)$, meaning the ratio of these two numbers seems to go to 1 as $n \\rightarrow \\infty$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "name": ""
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}