064-Solution.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# All square roots are periodic when written as continued fractions and can be written in the form:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![](images/64-1.PNG)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# For example, let us consider √23:\n",
    "\n",
    "![](images/64-2.PNG)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# If we continue we would get the following expansion:\n",
    "\n",
    "![](images/64-3.PNG)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# The process can be summarised as follows:\n",
    "\n",
    "![](images/64-4.PNG)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# It can be seen that the sequence is repeating. \n",
    "\n",
    "# For conciseness, we use the notation √23 = [4;(1,3,1,8)], to indicate that the block (1,3,1,8) repeats indefinitely."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# The first ten continued fraction representations of (irrational) square roots are:\n",
    "\n",
    "![](images/64-5.PNG)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Exactly four continued fractions, for N ≤ 13, have an odd period.\n",
    "\n",
    "# How many continued fractions for N ≤ 10000 have an odd period?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "______"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# From the [Wikipedia page for the continued fraction expansion](https://en.wikipedia.org/wiki/Methods_of_computing_square_roots#Continued_fraction_expansion)\n",
    "\n",
    "![](images/64-6.PNG)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## The page also gives an example of the algorithm\n",
    "\n",
    "![](images/64-7.PNG)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 72,
   "metadata": {},
   "outputs": [],
   "source": [
    "def continued_fraction(S):\n",
    "    m = 0\n",
    "    d = 1\n",
    "    a_0 = 0\n",
    "    while (a_0+1)**2<S:\n",
    "        a_0 += 1\n",
    "    \n",
    "    a = a_0\n",
    "    list_a = []\n",
    "    \n",
    "    i = 0\n",
    "    while len(list_a)<1000:\n",
    "        m = d*a-m\n",
    "        d = (S - m**2)/d\n",
    "        a = int((a_0+m)/d)\n",
    "        list_a.append(a)\n",
    "    \n",
    "    return a_0, list_a"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# From [Corollary 3.3](https://web.williams.edu/Mathematics/sjmiller/public_html/mathlab/public_html/jr02fall/Periodicity/alexajp.pdf):\n",
    "\n",
    "![](images/64-8.PNG)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 73,
   "metadata": {},
   "outputs": [],
   "source": [
    "def find_pattern(a_0, list_a):\n",
    "    return list_a.index(2*a_0)+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 74,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1322"
      ]
     },
     "execution_count": 74,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "count = 0\n",
    "\n",
    "for N in range(1,10001):\n",
    "    sqrt = N**0.5\n",
    "    if sqrt != sqrt//1:\n",
    "        a_0, list_a = continued_fraction(N)\n",
    "        period = find_pattern(a_0,list_a)\n",
    "        if period % 2 == 1:\n",
    "            count += 1\n",
    "count"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Answer: 1322"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}