Sum of the number of relatively prime integers up to $x$, $x-1$, $\ldots$, $1$

Question

If there is a number $x$, and we want to find the sum of the number of relatively prime integers up to $x$, $x-1$, $\dots$ until $1$, is there a formula for this or any way to solve it? Like if the number is $6$, you add up $0$ (for numbers relatively prime to $1$), $1$ (for numbers relatively prime to $2$), $2$ (for $3$), $2$ (for $4$), $4$ (for $5$), and $2$ (for $6$) for a total of $11$ numbers. I tried using Euler's Totient Function, but with a high number, that would require far too many computations. Is there any way to compute this for a high number, let's say $2019$, without taking a lot of time?

Answer 1

There is a well-known expression for the Euler function using the Möbius function: $$ \varphi(n) = n\sum_{d\mid n}\frac{\mu(d)}d. $$ Consequently, \begin{align} \sum_{n=1}^N \varphi(n) &= \sum_{n=1}^N n \sum_{d\mid n} \frac{\mu(d)}d \\ &= \sum_{d=1}^N \frac{\mu(d)}d \sum_{k\le N/d} kd \\ &= \frac12\,\sum_{d=1}^N \mu(d) \left\lfloor \frac Nd\right \rfloor \left(\left\lfloor \frac Nd\right \rfloor +1\right). \end{align} This expression is standartly used to give an asymptotic for the sum in the LHS, but it also can be used to efficiently calculate this sum.