# WARNING: The text below provides a guidance for a Project Euler problem.

• If you pride yourself in tackling problems entirely on your own, you are encouraged to exit this post right now.

• If you are simply looking for a hint for the problem, please visit the »Project Euler’s official forum«. You may find some hints here, but if you don’t want your problem spoiled, scroll cautiously.

• If you are looking for a readily available copy/paste answer, you will not find it here. All of the code snippets in the post have been stripped of some crucial lines (these are clearly marked). It is my aim that anyone able to replicate the answer based on such snippets will have to understand the solution conceptually. At that point, by virtue of learning something new, I believe he deserves it anyway.

• Guidance for future problems will not be published before 100 people have solved the problem and there are at least two more recent problems.



### Gcd sum

The problem requires us to compute the double sum $G(n) := \sum_{j=1}^n \sum_{i=1}^j gcd(i, j)$. We need to find $G(n)$ for a large value $n=10^{11}$, so we better find a sublinear algorithm. We will start by trying to rewrite the sum into a more enlightening form.

Notice that we may rewrite the internal sum by equating the condition $gcd(i, n) = e$ with $e \mid n;\ e \mid i;\ gcd(\frac i e, \frac n e) = 1$ for any $1 \leq i \leq n$:

Where $\phi$ is the Euler’s totient function (Given $n$, counts the number of coprime integers $1 \leq i \leq n$ to $n$). The sum $\sum_{i=1}^n gcd(i, n)$ is by the way also known as the »Pillai’s arithmetical function«. From here, we obtain $G$ being:

As for any positive numbers $a, b$ such that $1 \leq ab \leq n$, the term $a \phi\left(b\right)$ will appear exactly once in the summation (corresponding $a = e;\ b = \frac j e$), we may conveniently rewrite this sum as:

where we define $\Phi(n)$ to be the summatory function of the euler totients up to $n$:

As the next step in finding a sublinear algorithm we need to realize that there is only $O(n^{0.5})$ possible values $x = \left\lfloor \frac n a \right\rfloor$. Moreover, for any given value $x$, $x = \left\lfloor \frac n a \right\rfloor$ holds precisely with $a$’s for which $% $. Let $S(n) := \sum_{i=1}^n i = \frac{n(n+1)}{2}$ be the sum of the first $n$ natural numbers. We continue the derivation of $G$:

What are now the possible values of $x$? Well, defining $u := \lfloor \sqrt n \rfloor$ for clarity, any $x > u$ will appear in the summation exactly once, at $x = \lfloor \frac n {a} \rfloor$ for some $a \leq u$. Any $x \leq u$ will appear in the summation $\left(S\left(\left\lfloor \frac n {x} \right\rfloor\right) - S\left(\left\lfloor \frac n {x+1} \right\rfloor\right) \right)$ times. We thus divide our sum into two:

Now, provided that we can compute $\Phi$, all is good - we only have $O(n^{0.5})$ summands. Cracking the problem now turns into the following goal:

Find a sublinear way to compute $\Phi$.

For this we will actually use a similar trick as we did in the first time (»Dirichlet hyperbola method«). Recall from elementary number theory (or Wikipedia) that we can write $n = \sum_{d\mid n} \phi(d)$. We may trickily obtain a sum similar to (1):

Analogously, for any positive numbers $a, b$ such that $1 \leq ab \leq n$, the term $\phi\left(b\right)$ will appear exactly once in the summation (corresponding $a = d;\ b = \frac j d$) and we conveniently rewrite:

Exposing again the fact that there are only $O(n^{0.5})$ possible values of $\left \lfloor \frac n a \right \rfloor$, in the exactly same way as we did to obtain (2), we find:

And finally:

Using the recurrence (3) to compute $\Phi$ will take $O(n^{\frac 3 4})$ time; with precomputing some number of the first values of $\Phi$ this can be made faster. The following Julia code gives answer in about 80 seconds.