{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "e7323b89",
   "metadata": {},
   "source": [
    "# [Ordered Fractions](https://projecteuler.net/problem=71)\n",
    "\n",
    "This problem can be solved by hand.\n",
    "\n",
    "The concept the problem is describing is called a [Farey sequence](https://en.wikipedia.org/wiki/Farey_sequence). The example given in the problem is $F_8$, and we are tasked with finding the numerator of the left neighbor of $\\frac{3}{7}$ in $F_{1000000}$.\n",
    "\n",
    "It turns out there is a very simple method for determining this. Whenever you have two neighbors $\\frac{a}{b}$ and $\\frac{c}{d}$ in a Farey sequence, the next term that will appear between them in a subsequent Farey sequence is simply $\\frac{a+c}{b+d}$, called the [mediant](https://w.wiki/EoNc) of the two neighbors. For example, since we're given that the left neighbor of $\\frac{3}{7}$ in $F_8$ is $\\frac{2}{5}$, the next fraction to appear between the two will be\n",
    "$$\\frac{2+3}{5+7} = \\frac{5}{12}$$\n",
    "Naturally, this fraction will first appear in $F_{12}$, meaning $\\frac{5}{12}$ is the left neighbor of $\\frac{3}{7}$ in that Farey sequence. We could then, in turn, find the mediant of $\\frac{5}{12}$ and $\\frac{3}{7}$ to find the next left neighbor of $\\frac{3}{7}$ ($\\frac{8}{19}$, appearing in $F_{19}$).\n",
    "\n",
    "We can repeat this process until we find a mediant with a denominator greater than 1000000. At that point, we know that mediant will *not* be in $F_{1000000}$, so whatever left neighbor we just used to calculate it must be the left neighbor of $\\frac{3}{7}$ in $F_{1000000}$.\n",
    "\n",
    "To compute this by hand, observe that the $n$th mediant computed in this manner is simply\n",
    "$$\\frac{2 + 3n}{5 + 7n}$$\n",
    "Therefore, we just need to find the largest $n$ such that $5 + 7n \\leq 1000000$, which is $n=142856$. This gives us a numerator of 428570.\n",
    "\n",
    "## Relevant sequences\n",
    "* Numerators of Farey sequences: [A007305](https://oeis.org/A007305)\n",
    "\n",
    "#### Copyright (C) 2025 filifa\n",
    "\n",
    "This work is licensed under the [Creative Commons Attribution-ShareAlike 4.0 International license](https://creativecommons.org/licenses/by-sa/4.0/) and the [BSD Zero Clause license](https://spdx.org/licenses/0BSD.html)."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "SageMath 9.5",
   "language": "sage",
   "name": "sagemath"
  },
  "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.11.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}