Euler 066 - Diophantine equation.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Euler Problem 66\n",
    "\n",
    "\n",
    "\n",
    "Consider quadratic Diophantine equations of the form:\n",
    "\n",
    "$x^2 - Dy^2 = 1$\n",
    "\n",
    "For example, when $D=13$, the minimal solution in x is $649^2 – 13\\times180^2 = 1$.\n",
    "\n",
    "It can be assumed that there are no solutions in positive integers when $D$ is square.\n",
    "\n",
    "By finding minimal solutions in $x$ for $D = \\{2, 3, 5, 6, 7\\}$, we obtain the following:\n",
    "\n",
    "    3^2 – 2×2^2 = 1\n",
    "    2^2 – 3×1^2 = 1\n",
    "    9^2 – 5×4^2 = 1\n",
    "    5^2 – 6×2^2 = 1\n",
    "    8^2 – 7×3^2 = 1\n",
    "\n",
    "Hence, by considering minimal solutions in $x$ for $D \\le 7$, the largest $x$ is obtained when $D=5$.\n",
    "\n",
    "Find the value of $D \\le 1000$ in minimal solutions of $x$ for which the largest value of $x$ is obtained.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "661\n"
     ]
    }
   ],
   "source": [
    "from fractions import Fraction\n",
    "\n",
    "# Reciprocal of (a + b*sqrt(d))\n",
    "def recip(a,b,d):\n",
    "    D = a*a-b*b*d\n",
    "    return (a/D, -b/D)\n",
    "\n",
    "# Integer part of (a + b*sqrt(d))\n",
    "def intpart(a,b,d):\n",
    "    return int(a+b*d**.5)\n",
    "\n",
    "def cfrac(d):\n",
    "    if d == int(d**.5+.5)**2:\n",
    "        return (0,0)\n",
    "    a = Fraction(0)\n",
    "    b = Fraction(1)\n",
    "    term = intpart(a,b,d)\n",
    "    a = a - term\n",
    "    p1,q1 = 1,0\n",
    "    p2,q2 = term,1\n",
    "    while p2*p2-d*q2*q2 != 1:\n",
    "        a,b = recip(a,b,d)\n",
    "        term = intpart(a,b,d)\n",
    "        p1,p2 = p2,p2*term+p1\n",
    "        q1,q2 = q2,q2*term+q1\n",
    "        a = a - term\n",
    "    return (p2,q2)\n",
    "\n",
    "record = 0\n",
    "best_n = 0\n",
    "for n in range(1001):\n",
    "    c = cfrac(n)\n",
    "    if c[0] > record:\n",
    "        record = c[0]\n",
    "        best_n = n\n",
    "print(best_n)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "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
}