P64_odd_period_square_roots.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "P64_odd_period_square_roots",
      "provenance": []
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    }
  },
  "cells": [
    {
      "cell_type": "code",
      "metadata": {
        "id": "YZIf2tLlDRJn",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "from math import sqrt, isclose\n",
        "\n",
        "def continued_frac(n):\n",
        "  a0 = int(sqrt(n))\n",
        "  if a0*a0 == n:\n",
        "    return 0\n",
        "  period = 0\n",
        "  d = 1\n",
        "  m = 0\n",
        "  a = a0\n",
        "  while True:\n",
        "      m = d*a - m\n",
        "      d = (n - m * m) // d\n",
        "      a = (a0 + m) // d;\n",
        "      period += 1\n",
        "      if a == 2*a0:\n",
        "        return period\n",
        " "
      ],
      "execution_count": 2,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "9ArSwy2hvWnt",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 34
        },
        "outputId": "a97b5cf4-89c6-4693-c683-e4bdd2231355"
      },
      "source": [
        "print(continued_frac(31))"
      ],
      "execution_count": 3,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "8\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "bg_Hp649yaCc",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 68
        },
        "outputId": "b93571f2-d401-4980-d345-bd0ba4d6f923"
      },
      "source": [
        "%%time\n",
        "N = 10000\n",
        "counter = 0\n",
        "y = set(range(N+1))\n",
        "temp = set([i*i for i in range(int(sqrt(N))+1)])\n",
        "y = y - temp\n",
        "\n",
        "for num in y:\n",
        "  #print(num)\n",
        "  if continued_frac(num)%2 !=0:\n",
        "    counter += 1\n",
        "print(counter)"
      ],
      "execution_count": 4,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "1322\n",
            "CPU times: user 68.9 ms, sys: 1.16 ms, total: 70.1 ms\n",
            "Wall time: 69.6 ms\n"
          ],
          "name": "stdout"
        }
      ]
    }
  ]
}