064-odd-period-square-roots.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Odd period square roots\n",
    "## Problem 64 \n",
    "\n",
    "<div class=\"problem_content\" role=\"problem\">\n",
    "<p>All square roots are periodic when written as continued fractions and can be written in the form:</p>\n",
    "<div style=\"margin-left:20px;\">\n",
    "<table border=\"0\" cellpadding=\"0\" cellspacing=\"0\"><tr><td>&#8730;<var>N</var> = <var>a</var><sub>0</sub> +</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><var>a</var><sub>1</sub> +</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><var>a</var><sub>2</sub> +</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><var>a</var><sub>3</sub> + ...</td>\n",
    "</tr></table></div>\n",
    "<p>For example, let us consider &#8730;23:</p>\n",
    "<div style=\"margin-left:20px;\">\n",
    "<table border=\"0\" cellpadding=\"0\" cellspacing=\"0\"><tr><td>&#8730;23 = 4 + &#8730;23 &#8212; 4 = 4 +&#160;</td>\n",
    "<td style=\"border-bottom:1px solid #000;\"><div style=\"text-align:center;\">1</div></td>\n",
    "<td>&#160;= 4 +&#160;</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><div style=\"text-align:center;\">1<br/><span style=\"border-top:1px solid #000;\">&#8730;23&#8212;4</span></div></td>\n",
    "<td>&#160;</td>\n",
    "<td>1 +&#160;</td>\n",
    "<td><div style=\"text-align:center;\"><span style=\"border-bottom:1px solid #000;\">&#8730;23 &#8211; 3</span><br/>7</div></td>\n",
    "</tr></table></div>\n",
    "<p>If we continue we would get the following expansion:</p>\n",
    "<div style=\"margin-left:20px;\">\n",
    "<table border=\"0\" cellpadding=\"0\" cellspacing=\"0\"><tr><td>&#8730;23 = 4 +</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>1 +</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>3 +</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>1 +</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>8 + ...</td>\n",
    "</tr></table></div>\n",
    "<p>The process can be summarised as follows:</p>\n",
    "<div style=\"margin-left:20px;\">\n",
    "<table border=\"0\" cellpadding=\"0\" cellspacing=\"0\"><tr><td><var>a</var><sub>0</sub> = 4,</td>\n",
    "<td>&#160;</td>\n",
    "<td><div style=\"text-align:center;\">1<br/><span style=\"border-top:1px solid #000;\">&#8730;23&#8212;4</span></div></td>\n",
    "<td>&#160;=&#160;</td>\n",
    "<td><div style=\"text-align:center;\"><span style=\"border-bottom:1px solid #000;\">&#8730;23+4</span><br/>7</div></td>\n",
    "<td>&#160;=&#160;1 +&#160;</td>\n",
    "<td><div style=\"text-align:center;\"><span style=\"border-bottom:1px solid #000;\">&#8730;23&#8212;3</span><br/>7</div></td>\n",
    "</tr><tr><td><var>a</var><sub>1</sub> = 1,</td>\n",
    "<td>&#160;</td>\n",
    "<td><div style=\"text-align:center;\">7<br/><span style=\"border-top:1px solid #000;\">&#8730;23&#8212;3</span></div></td>\n",
    "<td>&#160;=&#160;</td>\n",
    "<td><div style=\"text-align:center;\"><span style=\"border-bottom:1px solid #000;\">7(&#8730;23+3)</span><br/>14</div></td>\n",
    "<td>&#160;=&#160;3 +&#160;</td>\n",
    "<td><div style=\"text-align:center;\"><span style=\"border-bottom:1px solid #000;\">&#8730;23&#8212;3</span><br/>2</div></td>\n",
    "</tr><tr><td><var>a</var><sub>2</sub> = 3,</td>\n",
    "<td>&#160;</td>\n",
    "<td><div style=\"text-align:center;\">2<br/><span style=\"border-top:1px solid #000;\">&#8730;23&#8212;3</span></div></td>\n",
    "<td>&#160;=&#160;</td>\n",
    "<td><div style=\"text-align:center;\"><span style=\"border-bottom:1px solid #000;\">2(&#8730;23+3)</span><br/>14</div></td>\n",
    "<td>&#160;=&#160;1 +&#160;</td>\n",
    "<td><div style=\"text-align:center;\"><span style=\"border-bottom:1px solid #000;\">&#8730;23&#8212;4</span><br/>7</div></td>\n",
    "</tr><tr><td><var>a</var><sub>3</sub> = 1,</td>\n",
    "<td>&#160;</td>\n",
    "<td><div style=\"text-align:center;\">7<br/><span style=\"border-top:1px solid #000;\">&#8730;23&#8212;4</span></div></td>\n",
    "<td>&#160;=&#160;</td>\n",
    "<td><div style=\"text-align:center;\"><span style=\"border-bottom:1px solid #000;\">7(&#8730;23+4)</span><br/>7</div></td>\n",
    "<td>&#160;=&#160;8 +&#160;</td>\n",
    "<td>&#8730;23&#8212;4</td>\n",
    "</tr><tr><td><var>a</var><sub>4</sub> = 8,</td>\n",
    "<td>&#160;</td>\n",
    "<td><div style=\"text-align:center;\">1<br/><span style=\"border-top:1px solid #000;\">&#8730;23&#8212;4</span></div></td>\n",
    "<td>&#160;=&#160;</td>\n",
    "<td><div style=\"text-align:center;\"><span style=\"border-bottom:1px solid #000;\">&#8730;23+4</span><br/>7</div></td>\n",
    "<td>&#160;=&#160;1 +&#160;</td>\n",
    "<td><div style=\"text-align:center;\"><span style=\"border-bottom:1px solid #000;\">&#8730;23&#8212;3</span><br/>7</div></td>\n",
    "</tr><tr><td><var>a</var><sub>5</sub> = 1,</td>\n",
    "<td>&#160;</td>\n",
    "<td><div style=\"text-align:center;\">7<br/><span style=\"border-top:1px solid #000;\">&#8730;23&#8212;3</span></div></td>\n",
    "<td>&#160;=&#160;</td>\n",
    "<td><div style=\"text-align:center;\"><span style=\"border-bottom:1px solid #000;\">7(&#8730;23+3)</span><br/>14</div></td>\n",
    "<td>&#160;=&#160;3 +&#160;</td>\n",
    "<td><div style=\"text-align:center;\"><span style=\"border-bottom:1px solid #000;\">&#8730;23&#8212;3</span><br/>2</div></td>\n",
    "</tr><tr><td><var>a</var><sub>6</sub> = 3,</td>\n",
    "<td>&#160;</td>\n",
    "<td><div style=\"text-align:center;\">2<br/><span style=\"border-top:1px solid #000;\">&#8730;23&#8212;3</span></div></td>\n",
    "<td>&#160;=&#160;</td>\n",
    "<td><div style=\"text-align:center;\"><span style=\"border-bottom:1px solid #000;\">2(&#8730;23+3)</span><br/>14</div></td>\n",
    "<td>&#160;=&#160;1 +&#160;</td>\n",
    "<td><div style=\"text-align:center;\"><span style=\"border-bottom:1px solid #000;\">&#8730;23&#8212;4</span><br/>7</div></td>\n",
    "</tr><tr><td><var>a</var><sub>7</sub> = 1,</td>\n",
    "<td>&#160;</td>\n",
    "<td><div style=\"text-align:center;\">7<br/><span style=\"border-top:1px solid #000;\">&#8730;23&#8212;4</span></div></td>\n",
    "<td>&#160;=&#160;</td>\n",
    "<td><div style=\"text-align:center;\"><span style=\"border-bottom:1px solid #000;\">7(&#8730;23+4)</span><br/>7</div></td>\n",
    "<td>&#160;=&#160;8 +&#160;</td>\n",
    "<td>&#8730;23&#8212;4</td>\n",
    "</tr></table></div>\n",
    "<p>It can be seen that the sequence is repeating. For conciseness, we use the notation &#8730;23 = [4;(1,3,1,8)], to indicate that the block (1,3,1,8) repeats indefinitely.</p>\n",
    "<p>The first ten continued fraction representations of (irrational) square roots are:</p>\n",
    "<p style=\"margin-left:20px;\">&#8730;2=[1;(2)], period=1<br/>\n",
    "&#8730;3=[1;(1,2)], period=2<br/>\n",
    "&#8730;5=[2;(4)], period=1<br/>\n",
    "&#8730;6=[2;(2,4)], period=2<br/>\n",
    "&#8730;7=[2;(1,1,1,4)], period=4<br/>\n",
    "&#8730;8=[2;(1,4)], period=2<br/>\n",
    "&#8730;10=[3;(6)], period=1<br/>\n",
    "&#8730;11=[3;(3,6)], period=2<br/>\n",
    "&#8730;12= [3;(2,6)], period=2<br/>\n",
    "&#8730;13=[3;(1,1,1,1,6)], period=5</p>\n",
    "<p>Exactly four continued fractions, for <var>N</var> &#8804; 13, have an odd period.</p>\n",
    "<p>How many continued fractions for <var>N</var> &#8804; 10000 have an odd period?</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
}