"Like [problem 71](https://projecteuler.net/problem=71), we're looking at [Farey sequences](https://en.wikipedia.org/wiki/Farey_sequence). This time we're interested in the cardinality of $F_{1000000}$.\n",
"\n",
"To begin, first note that $F_1 = \\{0, 1\\}$, so $|F_1| = 2$ (this problem isn't counting 0 and 1 in its totals - we'll handle that at the end). Then consider that for any Farey sequence $F_n$, the next sequence $F_{n+1}$ will contain all the terms from $F_n$, along with all irreducible fractions $\\frac{k}{n+1}$, (since any *reducible* fraction would already be in $F_n$).\n",
"How many new fractions does this get us? Well, the fraction only reduces if $k$ and $n+1$ have a common factor - in other words, if $k$ and $n+1$ are coprime, the fraction will not reduce. How many number less than $n+1$ are coprime to $n+1$? The [totient function](https://en.wikipedia.org/wiki/Euler%27s_totient_function) will tell us! So the number of irreducible fractions with denominator $n+1$ is simply $\\phi(n+1)$. This gives us\n",
"The [sum of totients](https://en.wikipedia.org/wiki/Totient_summatory_function) is denoted $\\Phi(n)$.\n",
"As mentioned before, we'll actually subtract two from this total, since the problem isn't counting 0 or 1. So this problem boils down to computing $\\Phi(1000000) - 1$.\n",
"\n",
"## Using SageMath\n",
"\n",
"Since SageMath implements a decently fast totient function, we could opt for the most straightforward approach."
"If you try to implement the totient function yourself, you might find it difficult to make this approach fast enough. An alternative is to \"sieve\" the values of totient - see [problem 70](https://projecteuler.net/problem=70). However, there's a few more *very* interesting methods to compute totient sums.\n",
"You might think a fast totient function is key to solving this problem quickly, but it turns out there's a crazy recursive formula for $\\Phi(n)$ that does not require implementing the totient function at all! Since it's a little hard to believe it works, here's a derivation of it.\n",
"\n",
"We start with the following identity, proven by Gauss:\n",
"$$\\sum_{d|k}\\phi(d) = k$$\n",
"\n",
"Then, we can apply the formula for [triangular numbers](https://en.wikipedia.org/wiki/Triangular_number):\n",
"$$\\sum_{k=1}^n \\sum_{d|k}\\phi(d) = \\sum_{k=1}^n k = \\frac{n(n+1)}{2}$$\n",
"\n",
"Now we'll rewrite the bounds.\n",
"$$\\sum_{1 \\leq k \\leq n} \\sum_{xy=k}\\phi(x) = \\frac{n(n+1)}{2}$$\n",
"\n",
"This makes it easier to see that we can condense the two nested summations into one.\n",
"Not a super intuitive definition for $\\Phi(n)$, but pretty simple to implement, and surprisingly quick!"
]
},
{
"cell_type": "code",
"execution_count": 2,
"id": "858a64d2",
"metadata": {},
"outputs": [],
"source": [
"from functools import cache\n",
"\n",
"@cache\n",
"def totient_sum(n):\n",
" if n == 1:\n",
" return 1\n",
" \n",
" return n*(n+1)/2 - sum(totient_sum(n//d) for d in range(2, n + 1))"
]
},
{
"cell_type": "code",
"execution_count": 3,
"id": "3f21311a",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"303963552391"
]
},
"execution_count": 3,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"totient_sum(1000000) - 1"
]
},
{
"cell_type": "markdown",
"id": "6f1085a3",
"metadata": {},
"source": [
"Both of the above strategies are simple and fast enough to get the job done on a modern computer, but it turns out we can go even deeper. But first, we need to become familiar with some important formulas.\n",
"\n",
"## Dirichlet convolution\n",
"\n",
"The [Dirichlet convolution](https://en.wikipedia.org/wiki/Dirichlet_convolution) of two [arithmetic functions](https://en.wikipedia.org/wiki/Arithmetic_function) $f$ and $g$ is\n",
"$$(f * g)(n) = \\sum_{xy=n} f(x) g(y)$$\n",
"\n",
"Several important mathematical functions have some representation as a Dirichlet convolution - see the above page for a list. An important one for our purposes is $\\phi = \\mathrm{Id} * \\mu$, where $\\mathrm{Id(n) = n}$ is the [identity function](https://en.wikipedia.org/wiki/Identity_function) and $\\mu$ is the [Möbius function](https://en.wikipedia.org/wiki/M%C3%B6bius_function) - if you've never heard of the latter, don't worry about it yet.\n",
"\n",
"## Dirichlet's hyperbola method\n",
"By applying the above Dirichlet convolution to\n",
"$$\\Phi(n) = \\sum_{k=1}^n \\phi(n)$$\n",
"we can derive an equivalent summation:\n",
"$$\\Phi(n) = \\sum_{k=1}^n \\sum_{xy=k} x \\mu(y)$$\n",
"\n",
"We're going to transform this summation by applying \n",
"[Dirichlet's hyperbola method](https://en.wikipedia.org/wiki/Dirichlet_hyperbola_method). Let $1 < a < n$, and let $b = n / a$. Then\n",
"$$\\Phi(n) = \\sum_{x=1}^a \\sum_{y=1}^{n/x} x \\mu(y) + \\sum_{y=1}^b \\sum_{x=1}^{n/y} x \\mu(y) - \\sum_{x=1}^a \\sum_{y=1}^b x \\mu(y)$$\n",
"\n",
"Then with some algebra, we can transform this into\n",
"$$\\Phi(n) = \\sum_{x=1}^a x M\\left(\\left\\lfloor \\frac{n}{x}\\right\\rfloor\\right) + \\sum_{y=1}^b \\mu(y) \\frac{\\left\\lfloor \\frac{n}{y} \\right\\rfloor \\left(\\left\\lfloor \\frac{n}{y}\\right\\rfloor + 1\\right)}{2} - M(\\lfloor b \\rfloor) \\frac{\\lfloor a \\rfloor(\\lfloor a\\rfloor +1)}{2}$$\n",
"where $M(n)$ is the [Mertens function](https://en.wikipedia.org/wiki/Mertens_function), which is just the partial sums of the Möbius function:\n",
"$$M(n) = \\sum_{k=1}^n \\mu(k)$$\n",
"\n",
"By using this formula for $\\Phi(n)$, instead of calculating $n$ different totients, our sums only run to $a$ and $b$.\n",
"\n",
"However, for this formula to be effective, we also need an efficient way to calculate $M(n)$. Fortunately, we can just apply the hyperbola method again, with the convolution $\\epsilon = \\mu * 1$, where $\\epsilon$ is the [unit identity](https://en.wikipedia.org/wiki/Unit_function). Once again, we choose $1 < a < n$ and let $b = n/a$.\n",
"Now we have a recursive implementation of $M(n)$. All that's left is to calculate the values of $\\mu(n)$ that we need. By taking advantage of $\\mu$ being [multiplicative](https://en.wikipedia.org/wiki/Multiplicative_function), we can compute values using a similar strategy to the sieve of Eratosthenes - see [problem 10](https://projecteuler.net/problem=10)."
"* Partial sums of totient function: [A002088](https://oeis.org/A002088)\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)."
