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

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?

• mathworld.wolfram.com/TotientSummatoryFunction.html – saulspatz Mar 15 at 23:30
• So basically you want to compute $\sum_{i\leq n} \varphi(i)$? – tomasz Mar 15 at 23:50
• Yes but how do you compute it? – Jaemin Kim Mar 16 at 0:17
• "let's say 2019" That's oddly specific. Where is this problem from, exactly? And are you supposed to calculate it by hand? – Arthur Mar 16 at 0:50
• 2019 since it's a big number and like, its the year 2019. I was just curious if this could be computed for numbers above 1000, and if so, numbers above 2000. – Jaemin Kim Mar 16 at 1:38

## 1 Answer

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.