{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$\\sqrt{23} = 4 + \\sqrt{23} - 4 = \\frac{1}{\\frac{1}{\\sqrt{23}-4}}$\n",
    "\n",
    "$\\frac{1}{\\sqrt{23}-4} = \\frac{\\sqrt{23}+4}{(\\sqrt{23}-4)(\\sqrt{23}+4)} = \\frac{\\sqrt{23}+4}{23 - 16}$\n",
    "\n",
    "$$\n",
    "\\begin{align}\n",
    "\\frac{1}{\\sqrt{23}-4} & = \\frac{\\sqrt{23}+4}{(\\sqrt{23}-4)(\\sqrt{23}+4)} \\\\\n",
    " & =\\frac{\\sqrt{23}+4}{23 - 16} \\\\\n",
    " & =\\frac{\\sqrt{23}+4}{7} , \\left \\lfloor \\frac{\\sqrt{23} + 4}{7} \\right \\rfloor = 1\\\\\n",
    " & =1 + \\frac{\\sqrt{23} + 4 -7}{7} \\\\\n",
    " & =1 + \\frac{\\sqrt{23} -3}{7} \\\\\n",
    " & =1 + \\frac{\\sqrt{23} -3}{7} \n",
    "\\end{align}\n",
    "$$\n",
    "\n",
    "\n",
    "$$\n",
    "\\begin{align}\n",
    "1 + \\frac{\\sqrt{23} -3}{7} & = 1 + \\frac{1}{\\frac{7}{\\sqrt{23} -3}} \\\\\n",
    "\\frac{7}{\\sqrt{23} -3} & =\\frac{7(\\sqrt{23}+3)}{(\\sqrt{23} -3)(\\sqrt{23}+3)}\\\\\n",
    " & =\\frac{7(\\sqrt{23}+3)}{23 - 9} \\\\\n",
    " & =\\frac{7(\\sqrt{23}+3)}{14}\\\\\n",
    " & =\\frac{\\sqrt{23} + 3}{2}, \\left \\lfloor \\frac{\\sqrt{23} + 3}{2} \\right \\rfloor = 3\\\\\n",
    " & = 3 + \\frac{\\sqrt{23} + 3}{2} - \\frac{6}{2}\\\\\n",
    " & = 3 + \\frac{\\sqrt{23} - 3}{2}\\\\\n",
    "\\end{align}\n",
    "$$\n",
    "\n",
    "$$\n",
    "\\begin{align}\n",
    "\\frac{k}{\\sqrt{n} - a} \n",
    " &= \\frac{k \\left( \\sqrt{n} + a \\right)}{\\left( \\sqrt{n} - a \\right) \\left( \\sqrt{n} + a \\right)} \\\\\n",
    " & = \\frac{k \\left( \\sqrt{n} + a \\right)}{n - a^2} \\\\\n",
    " & =\\left \\lfloor \\frac{k \\left( \\sqrt{n} + a \\right) }{n - a^2} \\right \\rfloor + \n",
    " \\frac{k \\left( \\sqrt{n} + a \\right)}{n - a^2} - \\left \\lfloor \\frac{k \\left( \\sqrt{n} + a \\right) }{n - a^2} \\right \\rfloor \\\\\n",
    " & =\\left \\lfloor \\frac{k \\left( \\sqrt{n} + a \\right) }{n - a^2} \\right \\rfloor + \n",
    " \\frac{\\sqrt{n} + a}{\\frac{n - a^2}{k}} - \\left \\lfloor \\frac{k \\left( \\sqrt{n} + a \\right) }{n - a^2} \\right \\rfloor \\\\\n",
    " & =\\left \\lfloor \\frac{k \\left( \\sqrt{n} + a \\right) }{n - a^2} \\right \\rfloor + \n",
    " \\frac{\\sqrt{n} + a - \\left \\lfloor \\frac{k \\left( \\sqrt{n} + a \\right) }{n - a^2} \\right \\rfloor \\left( \\frac{n - a^2}{k} \\right)}{\\frac{n - a^2}{k}}\\\\\n",
    " & = \\mathrm{lead} + \\frac{\\sqrt{n} + \\mathrm{trail}}{\\mathrm{denom}}\n",
    "\\end{align}\n",
    "$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       ":continued"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def continued(n, k, a)\n",
    "  lead = ((k * (Math.sqrt(n) + a)) / (n - a ** 2)).floor\n",
    "  denom = (n - a ** 2) / k\n",
    "  trail = a - lead * denom\n",
    "  [lead, denom, trail]\n",
    "end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 7, -3]"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "continued(23, 1, Math.sqrt(23).floor)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 7, -3]"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "continued(23, 1, 4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[3, 2, -3]"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "continued(23, 7, 3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 7, -4]"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "continued(23, 2, 3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[8, 1, -4]"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "continued(23, 7, 4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 7, -3]"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "continued(23, 1, 4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[3, 2, -3]"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "continued(23, 7, 3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       ":continue_start"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def continue_start(n)\n",
    "  continued(n, 1, Math.sqrt(n).floor)\n",
    "end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 7, -3]"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "continue_start(23)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       ":continue_until_repeat"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def continue_until_repeat(n)\n",
    "  a_n = [Math.sqrt(n).floor]\n",
    "  states = []\n",
    "  l, d, t = continue_start(n)\n",
    "  while !states.include?([d, t])\n",
    "    a_n << l\n",
    "    states << [d, t]\n",
    "    l, d, t = continued(n, d, -1 * t)\n",
    "  end\n",
    "  [a_n, states, states.length - states.index([d, t])]\n",
    "end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[4, 1, 3, 1, 8], [[7, -3], [2, -3], [7, -4], [1, -4]], 4]"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "continue_until_repeat 23"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[3, 1, 1, 1, 1, 6], [[4, -1], [3, -2], [3, -1], [4, -3], [1, -3]], 5]"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "continue_until_repeat 13"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Math.sqrt(8).floor ** 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       ":repeat_period_length"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def repeat_period_length(n)\n",
    "  a_n, states, period_length = continue_until_repeat(n)\n",
    "  period_length\n",
    "end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "5"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "repeat_period_length 13"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "odd_counts = 0\n",
    "(1..13).each do |i|\n",
    "  if (Math.sqrt(i).floor ** 2) != i\n",
    "    # puts \"#{i} -> #{repeat_period_length i}\"\n",
    "    odd_counts += 1 if repeat_period_length(i) % 2 == 1\n",
    "  end\n",
    "end\n",
    "odd_counts"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1322"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "odd_counts = 0\n",
    "(1..(10 ** 4)).each do |i|\n",
    "  if (Math.sqrt(i).floor ** 2) != i\n",
    "    # puts \"#{i} -> #{repeat_period_length i}\"\n",
    "    odd_counts += 1 if repeat_period_length(i) % 2 == 1\n",
    "  end\n",
    "end\n",
    "odd_counts"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Ruby 2.4.0",
   "language": "ruby",
   "name": "ruby"
  },
  "language_info": {
   "file_extension": ".rb",
   "mimetype": "application/x-ruby",
   "name": "ruby",
   "version": "2.4.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}