euler64.ipynb

   1 {
   2  "cells": [
   3   {
   4    "cell_type": "markdown",
   5    "metadata": {},
   6    "source": [
   7     "$\\sqrt{23} = 4 + \\sqrt{23} - 4 = \\frac{1}{\\frac{1}{\\sqrt{23}-4}}$\n",
   8     "\n",
   9     "$\\frac{1}{\\sqrt{23}-4} = \\frac{\\sqrt{23}+4}{(\\sqrt{23}-4)(\\sqrt{23}+4)} = \\frac{\\sqrt{23}+4}{23 - 16}$\n",
  10     "\n",
  11     "$$\n",
  12     "\\begin{align}\n",
  13     "\\frac{1}{\\sqrt{23}-4} & = \\frac{\\sqrt{23}+4}{(\\sqrt{23}-4)(\\sqrt{23}+4)} \\\\\n",
  14     " & =\\frac{\\sqrt{23}+4}{23 - 16} \\\\\n",
  15     " & =\\frac{\\sqrt{23}+4}{7} , \\left \\lfloor \\frac{\\sqrt{23} + 4}{7} \\right \\rfloor = 1\\\\\n",
  16     " & =1 + \\frac{\\sqrt{23} + 4 -7}{7} \\\\\n",
  17     " & =1 + \\frac{\\sqrt{23} -3}{7} \\\\\n",
  18     " & =1 + \\frac{\\sqrt{23} -3}{7} \n",
  19     "\\end{align}\n",
  20     "$$\n",
  21     "\n",
  22     "\n",
  23     "$$\n",
  24     "\\begin{align}\n",
  25     "1 + \\frac{\\sqrt{23} -3}{7} & = 1 + \\frac{1}{\\frac{7}{\\sqrt{23} -3}} \\\\\n",
  26     "\\frac{7}{\\sqrt{23} -3} & =\\frac{7(\\sqrt{23}+3)}{(\\sqrt{23} -3)(\\sqrt{23}+3)}\\\\\n",
  27     " & =\\frac{7(\\sqrt{23}+3)}{23 - 9} \\\\\n",
  28     " & =\\frac{7(\\sqrt{23}+3)}{14}\\\\\n",
  29     " & =\\frac{\\sqrt{23} + 3}{2}, \\left \\lfloor \\frac{\\sqrt{23} + 3}{2} \\right \\rfloor = 3\\\\\n",
  30     " & = 3 + \\frac{\\sqrt{23} + 3}{2} - \\frac{6}{2}\\\\\n",
  31     " & = 3 + \\frac{\\sqrt{23} - 3}{2}\\\\\n",
  32     "\\end{align}\n",
  33     "$$\n",
  34     "\n",
  35     "$$\n",
  36     "\\begin{align}\n",
  37     "\\frac{k}{\\sqrt{n} - a} \n",
  38     " &= \\frac{k \\left( \\sqrt{n} + a \\right)}{\\left( \\sqrt{n} - a \\right) \\left( \\sqrt{n} + a \\right)} \\\\\n",
  39     " & = \\frac{k \\left( \\sqrt{n} + a \\right)}{n - a^2} \\\\\n",
  40     " & =\\left \\lfloor \\frac{k \\left( \\sqrt{n} + a \\right) }{n - a^2} \\right \\rfloor + \n",
  41     " \\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",
  42     " & =\\left \\lfloor \\frac{k \\left( \\sqrt{n} + a \\right) }{n - a^2} \\right \\rfloor + \n",
  43     " \\frac{\\sqrt{n} + a}{\\frac{n - a^2}{k}} - \\left \\lfloor \\frac{k \\left( \\sqrt{n} + a \\right) }{n - a^2} \\right \\rfloor \\\\\n",
  44     " & =\\left \\lfloor \\frac{k \\left( \\sqrt{n} + a \\right) }{n - a^2} \\right \\rfloor + \n",
  45     " \\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",
  46     " & = \\mathrm{lead} + \\frac{\\sqrt{n} + \\mathrm{trail}}{\\mathrm{denom}}\n",
  47     "\\end{align}\n",
  48     "$$"
  49    ]
  50   },
  51   {
  52    "cell_type": "code",
  53    "execution_count": 1,
  54    "metadata": {},
  55    "outputs": [
  56     {
  57      "data": {
  58       "text/plain": [
  59        ":continued"
  60       ]
  61      },
  62      "execution_count": 1,
  63      "metadata": {},
  64      "output_type": "execute_result"
  65     }
  66    ],
  67    "source": [
  68     "def continued(n, k, a)\n",
  69     "  lead = ((k * (Math.sqrt(n) + a)) / (n - a ** 2)).floor\n",
  70     "  denom = (n - a ** 2) / k\n",
  71     "  trail = a - lead * denom\n",
  72     "  [lead, denom, trail]\n",
  73     "end"
  74    ]
  75   },
  76   {
  77    "cell_type": "code",
  78    "execution_count": 2,
  79    "metadata": {},
  80    "outputs": [
  81     {
  82      "data": {
  83       "text/plain": [
  84        "[1, 7, -3]"
  85       ]
  86      },
  87      "execution_count": 2,
  88      "metadata": {},
  89      "output_type": "execute_result"
  90     }
  91    ],
  92    "source": [
  93     "continued(23, 1, Math.sqrt(23).floor)"
  94    ]
  95   },
  96   {
  97    "cell_type": "code",
  98    "execution_count": 3,
  99    "metadata": {},
 100    "outputs": [
 101     {
 102      "data": {
 103       "text/plain": [
 104        "[1, 7, -3]"
 105       ]
 106      },
 107      "execution_count": 3,
 108      "metadata": {},
 109      "output_type": "execute_result"
 110     }
 111    ],
 112    "source": [
 113     "continued(23, 1, 4)"
 114    ]
 115   },
 116   {
 117    "cell_type": "code",
 118    "execution_count": 4,
 119    "metadata": {},
 120    "outputs": [
 121     {
 122      "data": {
 123       "text/plain": [
 124        "[3, 2, -3]"
 125       ]
 126      },
 127      "execution_count": 4,
 128      "metadata": {},
 129      "output_type": "execute_result"
 130     }
 131    ],
 132    "source": [
 133     "continued(23, 7, 3)"
 134    ]
 135   },
 136   {
 137    "cell_type": "code",
 138    "execution_count": 5,
 139    "metadata": {},
 140    "outputs": [
 141     {
 142      "data": {
 143       "text/plain": [
 144        "[1, 7, -4]"
 145       ]
 146      },
 147      "execution_count": 5,
 148      "metadata": {},
 149      "output_type": "execute_result"
 150     }
 151    ],
 152    "source": [
 153     "continued(23, 2, 3)"
 154    ]
 155   },
 156   {
 157    "cell_type": "code",
 158    "execution_count": 6,
 159    "metadata": {},
 160    "outputs": [
 161     {
 162      "data": {
 163       "text/plain": [
 164        "[8, 1, -4]"
 165       ]
 166      },
 167      "execution_count": 6,
 168      "metadata": {},
 169      "output_type": "execute_result"
 170     }
 171    ],
 172    "source": [
 173     "continued(23, 7, 4)"
 174    ]
 175   },
 176   {
 177    "cell_type": "code",
 178    "execution_count": 7,
 179    "metadata": {},
 180    "outputs": [
 181     {
 182      "data": {
 183       "text/plain": [
 184        "[1, 7, -3]"
 185       ]
 186      },
 187      "execution_count": 7,
 188      "metadata": {},
 189      "output_type": "execute_result"
 190     }
 191    ],
 192    "source": [
 193     "continued(23, 1, 4)"
 194    ]
 195   },
 196   {
 197    "cell_type": "code",
 198    "execution_count": 8,
 199    "metadata": {},
 200    "outputs": [
 201     {
 202      "data": {
 203       "text/plain": [
 204        "[3, 2, -3]"
 205       ]
 206      },
 207      "execution_count": 8,
 208      "metadata": {},
 209      "output_type": "execute_result"
 210     }
 211    ],
 212    "source": [
 213     "continued(23, 7, 3)"
 214    ]
 215   },
 216   {
 217    "cell_type": "code",
 218    "execution_count": 9,
 219    "metadata": {},
 220    "outputs": [
 221     {
 222      "data": {
 223       "text/plain": [
 224        ":continue_start"
 225       ]
 226      },
 227      "execution_count": 9,
 228      "metadata": {},
 229      "output_type": "execute_result"
 230     }
 231    ],
 232    "source": [
 233     "def continue_start(n)\n",
 234     "  continued(n, 1, Math.sqrt(n).floor)\n",
 235     "end"
 236    ]
 237   },
 238   {
 239    "cell_type": "code",
 240    "execution_count": 10,
 241    "metadata": {},
 242    "outputs": [
 243     {
 244      "data": {
 245       "text/plain": [
 246        "[1, 7, -3]"
 247       ]
 248      },
 249      "execution_count": 10,
 250      "metadata": {},
 251      "output_type": "execute_result"
 252     }
 253    ],
 254    "source": [
 255     "continue_start(23)"
 256    ]
 257   },
 258   {
 259    "cell_type": "code",
 260    "execution_count": 11,
 261    "metadata": {},
 262    "outputs": [
 263     {
 264      "data": {
 265       "text/plain": [
 266        ":continue_until_repeat"
 267       ]
 268      },
 269      "execution_count": 11,
 270      "metadata": {},
 271      "output_type": "execute_result"
 272     }
 273    ],
 274    "source": [
 275     "def continue_until_repeat(n)\n",
 276     "  a_n = [Math.sqrt(n).floor]\n",
 277     "  states = []\n",
 278     "  l, d, t = continue_start(n)\n",
 279     "  while !states.include?([d, t])\n",
 280     "    a_n << l\n",
 281     "    states << [d, t]\n",
 282     "    l, d, t = continued(n, d, -1 * t)\n",
 283     "  end\n",
 284     "  [a_n, states, states.length - states.index([d, t])]\n",
 285     "end"
 286    ]
 287   },
 288   {
 289    "cell_type": "code",
 290    "execution_count": 12,
 291    "metadata": {},
 292    "outputs": [
 293     {
 294      "data": {
 295       "text/plain": [
 296        "[[4, 1, 3, 1, 8], [[7, -3], [2, -3], [7, -4], [1, -4]], 4]"
 297       ]
 298      },
 299      "execution_count": 12,
 300      "metadata": {},
 301      "output_type": "execute_result"
 302     }
 303    ],
 304    "source": [
 305     "continue_until_repeat 23"
 306    ]
 307   },
 308   {
 309    "cell_type": "code",
 310    "execution_count": 13,
 311    "metadata": {},
 312    "outputs": [
 313     {
 314      "data": {
 315       "text/plain": [
 316        "[[3, 1, 1, 1, 1, 6], [[4, -1], [3, -2], [3, -1], [4, -3], [1, -3]], 5]"
 317       ]
 318      },
 319      "execution_count": 13,
 320      "metadata": {},
 321      "output_type": "execute_result"
 322     }
 323    ],
 324    "source": [
 325     "continue_until_repeat 13"
 326    ]
 327   },
 328   {
 329    "cell_type": "code",
 330    "execution_count": 14,
 331    "metadata": {},
 332    "outputs": [
 333     {
 334      "data": {
 335       "text/plain": [
 336        "4"
 337       ]
 338      },
 339      "execution_count": 14,
 340      "metadata": {},
 341      "output_type": "execute_result"
 342     }
 343    ],
 344    "source": [
 345     "Math.sqrt(8).floor ** 2"
 346    ]
 347   },
 348   {
 349    "cell_type": "code",
 350    "execution_count": 15,
 351    "metadata": {},
 352    "outputs": [
 353     {
 354      "data": {
 355       "text/plain": [
 356        ":repeat_period_length"
 357       ]
 358      },
 359      "execution_count": 15,
 360      "metadata": {},
 361      "output_type": "execute_result"
 362     }
 363    ],
 364    "source": [
 365     "def repeat_period_length(n)\n",
 366     "  a_n, states, period_length = continue_until_repeat(n)\n",
 367     "  period_length\n",
 368     "end"
 369    ]
 370   },
 371   {
 372    "cell_type": "code",
 373    "execution_count": 19,
 374    "metadata": {},
 375    "outputs": [
 376     {
 377      "data": {
 378       "text/plain": [
 379        "5"
 380       ]
 381      },
 382      "execution_count": 19,
 383      "metadata": {},
 384      "output_type": "execute_result"
 385     }
 386    ],
 387    "source": [
 388     "repeat_period_length 13"
 389    ]
 390   },
 391   {
 392    "cell_type": "code",
 393    "execution_count": 20,
 394    "metadata": {},
 395    "outputs": [
 396     {
 397      "data": {
 398       "text/plain": [
 399        "4"
 400       ]
 401      },
 402      "execution_count": 20,
 403      "metadata": {},
 404      "output_type": "execute_result"
 405     }
 406    ],
 407    "source": [
 408     "odd_counts = 0\n",
 409     "(1..13).each do |i|\n",
 410     "  if (Math.sqrt(i).floor ** 2) != i\n",
 411     "    # puts \"#{i} -> #{repeat_period_length i}\"\n",
 412     "    odd_counts += 1 if repeat_period_length(i) % 2 == 1\n",
 413     "  end\n",
 414     "end\n",
 415     "odd_counts"
 416    ]
 417   },
 418   {
 419    "cell_type": "code",
 420    "execution_count": 21,
 421    "metadata": {},
 422    "outputs": [
 423     {
 424      "data": {
 425       "text/plain": [
 426        "1322"
 427       ]
 428      },
 429      "execution_count": 21,
 430      "metadata": {},
 431      "output_type": "execute_result"
 432     }
 433    ],
 434    "source": [
 435     "odd_counts = 0\n",
 436     "(1..(10 ** 4)).each do |i|\n",
 437     "  if (Math.sqrt(i).floor ** 2) != i\n",
 438     "    # puts \"#{i} -> #{repeat_period_length i}\"\n",
 439     "    odd_counts += 1 if repeat_period_length(i) % 2 == 1\n",
 440     "  end\n",
 441     "end\n",
 442     "odd_counts"
 443    ]
 444   },
 445   {
 446    "cell_type": "code",
 447    "execution_count": null,
 448    "metadata": {
 449     "collapsed": true
 450    },
 451    "outputs": [],
 452    "source": []
 453   }
 454  ],
 455  "metadata": {
 456   "kernelspec": {
 457    "display_name": "Ruby 2.4.0",
 458    "language": "ruby",
 459    "name": "ruby"
 460   },
 461   "language_info": {
 462    "file_extension": ".rb",
 463    "mimetype": "application/x-ruby",
 464    "name": "ruby",
 465    "version": "2.4.0"
 466   }
 467  },
 468  "nbformat": 4,
 469  "nbformat_minor": 2
 470 }