065-convergents-of-e.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Convergents of e\n",
    "## Problem 65 \n",
    "\n",
    "<div class=\"problem_content\" role=\"problem\">\n",
    "<p>The square root of 2 can be written as an infinite continued fraction.</p>\n",
    "<div style=\"margin-left:20px;\">\n",
    "<table border=\"0\" cellpadding=\"0\" cellspacing=\"0\"><tr><td>&#8730;2 = 1 +</td>\n",
    "<td colspan=\"4\" style=\"border-bottom:1px solid #000;\"><div style=\"text-align:center;\">1</div></td>\n",
    "</tr><tr><td>&#160;</td>\n",
    "<td>2 +</td>\n",
    "<td colspan=\"3\" style=\"border-bottom:1px solid #000;\"><div style=\"text-align:center;\">1</div></td>\n",
    "</tr><tr><td>&#160;</td>\n",
    "<td>&#160;</td>\n",
    "<td>2 +</td>\n",
    "<td colspan=\"2\" style=\"border-bottom:1px solid #000;\"><div style=\"text-align:center;\">1</div></td>\n",
    "</tr><tr><td>&#160;</td>\n",
    "<td>&#160;</td>\n",
    "<td>&#160;</td>\n",
    "<td>2 +</td>\n",
    "<td style=\"border-bottom:1px solid #000;\"><div style=\"text-align:center;\">1</div></td>\n",
    "</tr><tr><td>&#160;</td>\n",
    "<td>&#160;</td>\n",
    "<td>&#160;</td>\n",
    "<td>&#160;</td>\n",
    "<td>2 + ...</td>\n",
    "</tr></table></div>\n",
    "<p>The infinite continued fraction can be written, &#8730;2 = [1;(2)], (2) indicates that 2 repeats <i>ad infinitum</i>. In a similar way, &#8730;23 = [4;(1,3,1,8)].</p>\n",
    "<p>It turns out that the sequence of partial values of continued fractions for square roots provide the best rational approximations. Let us consider the convergents for &#8730;2.</p>\n",
    "<div style=\"margin-left:20px;\">\n",
    "<table border=\"0\" cellpadding=\"0\" cellspacing=\"0\"><tr><td>1 +</td>\n",
    "<td style=\"border-bottom:1px solid #000;\"><div style=\"text-align:center;\">1</div></td>\n",
    "<td>= 3/2</td>\n",
    "</tr><tr><td>&#160;</td>\n",
    "<td><div style=\"text-align:center;\">2</div></td>\n",
    "<td>&#160;</td>\n",
    "</tr></table><table border=\"0\" cellpadding=\"0\" cellspacing=\"0\"><tr><td>1 +</td>\n",
    "<td colspan=\"2\" style=\"border-bottom:1px solid #000;\"><div style=\"text-align:center;\">1</div></td>\n",
    "<td>= 7/5</td>\n",
    "</tr><tr><td>&#160;</td>\n",
    "<td>2 +</td>\n",
    "<td style=\"border-bottom:1px solid #000;\"><div style=\"text-align:center;\">1</div></td>\n",
    "</tr><tr><td>&#160;</td>\n",
    "<td>&#160;</td>\n",
    "<td><div style=\"text-align:center;\">2</div></td>\n",
    "<td>&#160;</td>\n",
    "</tr></table><table border=\"0\" cellpadding=\"0\" cellspacing=\"0\"><tr><td>1 +</td>\n",
    "<td colspan=\"3\" style=\"border-bottom:1px solid #000;\"><div style=\"text-align:center;\">1</div></td>\n",
    "<td>= 17/12</td>\n",
    "</tr><tr><td>&#160;</td>\n",
    "<td>2 +</td>\n",
    "<td colspan=\"2\" style=\"border-bottom:1px solid #000;\"><div style=\"text-align:center;\">1</div></td>\n",
    "<td>&#160;</td>\n",
    "</tr><tr><td>&#160;</td>\n",
    "<td>&#160;</td>\n",
    "<td>2 +</td>\n",
    "<td style=\"border-bottom:1px solid #000;\"><div style=\"text-align:center;\">1</div></td>\n",
    "<td>&#160;</td>\n",
    "</tr><tr><td>&#160;</td>\n",
    "<td>&#160;</td>\n",
    "<td>&#160;</td>\n",
    "<td><div style=\"text-align:center;\">2</div></td>\n",
    "<td>&#160;</td>\n",
    "</tr></table><table border=\"0\" cellpadding=\"0\" cellspacing=\"0\"><tr><td>1 +</td>\n",
    "<td colspan=\"4\" style=\"border-bottom:1px solid #000;\"><div style=\"text-align:center;\">1</div></td>\n",
    "<td>= 41/29</td>\n",
    "</tr><tr><td>&#160;</td>\n",
    "<td>2 +</td>\n",
    "<td colspan=\"3\" style=\"border-bottom:1px solid #000;\"><div style=\"text-align:center;\">1</div></td>\n",
    "</tr><tr><td>&#160;</td>\n",
    "<td>&#160;</td>\n",
    "<td>2 +</td>\n",
    "<td colspan=\"2\" style=\"border-bottom:1px solid #000;\"><div style=\"text-align:center;\">1</div></td>\n",
    "<td>&#160;</td>\n",
    "</tr><tr><td>&#160;</td>\n",
    "<td>&#160;</td>\n",
    "<td>&#160;</td>\n",
    "<td>2 +</td>\n",
    "<td style=\"border-bottom:1px solid #000;\"><div style=\"text-align:center;\">1</div></td>\n",
    "<td>&#160;</td>\n",
    "</tr><tr><td>&#160;</td>\n",
    "<td>&#160;</td>\n",
    "<td>&#160;</td>\n",
    "<td>&#160;</td>\n",
    "<td><div style=\"text-align:center;\">2</div></td>\n",
    "<td>&#160;</td>\n",
    "</tr></table></div>\n",
    "<p>Hence the sequence of the first ten convergents for &#8730;2 are:</p>\n",
    "<div class=\"note\">1, 3/2, 7/5, 17/12, 41/29, 99/70, 239/169, 577/408, 1393/985, 3363/2378, ...</div>\n",
    "<p>What is most surprising is that the important mathematical constant,<br/><i>e</i> = [2; 1,2,1, 1,4,1, 1,6,1 , ... , 1,2<i>k</i>,1, ...].</p>\n",
    "<p>The first ten terms in the sequence of convergents for <i>e</i> are:</p>\n",
    "<div class=\"note\">2, 3, 8/3, 11/4, 19/7, 87/32, 106/39, 193/71, 1264/465, 1457/536, ...</div>\n",
    "<p>The sum of digits in the numerator of the 10<sup>th</sup> convergent is 1+4+5+7=17.</p>\n",
    "<p>Find the sum of digits in the numerator of the 100<sup>th</sup> convergent of the continued fraction for <i>e</i>.</p>\n",
    "</div>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def solve():\n",
    "    # Your code here\n",
    "    \n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Solution"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "solve()"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}