prob_100_done.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from math import sqrt\n",
    "from time import time"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "N = 10**7\n",
    "x,y = 3,2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "4 3 9.274482727050781e-05\n",
      "21 15 0.0001552104949951172\n",
      "120 85 0.00023365020751953125\n",
      "697 493 0.0006749629974365234\n",
      "4060 2871 0.003317594528198242\n",
      "23661 16731 0.01949167251586914\n",
      "137904 97513 0.10926342010498047\n",
      "803761 568345 0.6073250770568848\n",
      "4684660 3312555 3.4901630878448486\n"
     ]
    }
   ],
   "source": [
    "t0 = time()\n",
    "while x <N:\n",
    "    lhs = 2*y*(y-1)\n",
    "    rhs = x*(x-1)\n",
    "    if lhs > rhs:\n",
    "        x+=1\n",
    "    elif lhs < rhs:\n",
    "        y+=1\n",
    "    else:\n",
    "        print(x,y,time()-t0)\n",
    "        x+=1\n",
    "        y+=1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "697 493 0.0004787445068359375\n",
      "4060 2871 0.003490447998046875\n",
      "23661 16731 0.0186002254486084\n",
      "137904 97513 0.10523796081542969\n",
      "803761 568345 0.5947792530059814\n",
      "4684660 3312555 3.438605546951294\n"
     ]
    }
   ],
   "source": [
    "N = 10**7\n",
    "x,y = 300,2\n",
    "\n",
    "t0 = time()\n",
    "while x <N:\n",
    "    lhs = 2*y*(y-1)\n",
    "    rhs = x*(x-1)\n",
    "    if lhs > rhs:\n",
    "        x+=1\n",
    "    elif lhs < rhs:\n",
    "        y+=1\n",
    "    else:\n",
    "        print(x,y,time()-t0)\n",
    "        x+=1\n",
    "        y+=1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# from https://www.alpertron.com.ar/QUAD.HTM\n",
    "# x_{n+1} = 3 * x_n + 2 * y_n -2\n",
    "# y_{n+1} = 4 * x_n + 3 * y_n -3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "21 15 36\n",
      "120 85 205\n",
      "697 493 1190\n",
      "4060 2871 6931\n",
      "23661 16731 40392\n",
      "137904 97513 235417\n",
      "803761 568345 1372106\n",
      "4684660 3312555 7997215\n",
      "27304197 19306983 46611180\n",
      "159140520 112529341 271669861\n",
      "927538921 655869061 1583407982\n",
      "5406093004 3822685023 9228778027\n",
      "31509019101 22280241075 53789260176\n",
      "183648021600 129858761425 313506783025\n",
      "1070379110497 756872327473 1827251437970\n",
      "756872327473\n"
     ]
    }
   ],
   "source": [
    "x_0, y_0 = 4,3\n",
    "L_0 = x_0 + y_0\n",
    "\n",
    "L_max = 10**12\n",
    "\n",
    "while L_0 < L_max:\n",
    "    x_1 = 3*x_0 + 4*y_0 -3\n",
    "    y_1 = 2*x_0 + 3*y_0 -2\n",
    "    x_0, y_0 = x_1, y_1\n",
    "    L_0 = x_0+y_0\n",
    "    print(x_0,y_0,L_0)\n",
    "\n",
    "print(y_0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# 756872327473 correct solution"
   ]
  }
 ],
 "metadata": {
  "anaconda-cloud": {},
  "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.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}