Euler 071 - Ordered fractions.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Euler Problem 71\n",
    "================\n",
    "\n",
    "Consider the fraction, n/d, where n and d are positive integers. If n < d and HCF(n,d)=1, it is called a reduced proper fraction.\n",
    "\n",
    "If we list the set of reduced proper fractions for d ≤ 8 in ascending order of size, we get:\n",
    "\n",
    "1/8, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2, 4/7, 3/5, 5/8, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 7/8\n",
    "\n",
    "It can be seen that 2/5 is the fraction immediately to the left of 3/7.\n",
    "\n",
    "By listing the set of reduced proper fractions for d ≤ 1,000,000 in ascending order of size, find the numerator of the fraction immediately to the left of 3/7.\n",
    "\n",
    "**Solution:** We seek the fraction a/b < 3/7 with denominator at most 1,000,000 that minimizes\n",
    "$\\frac37 - \\frac{a}{b} = \\frac{3b-7a}{7b}$.\n",
    "\n",
    "The minimum value occurs when the numerator is 1 and the denominator is as large as possible.\n",
    "\n",
    "The integer solutions to $3b - 7a = 1$ are given by $b = 5 + 7k$ and $a = 2 + 3k$. The largest value of $b$ occurs when $k = 142856$, so $a = 2 + 3(142856) = 428570$."
   ]
  }
 ],
 "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.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}