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?

  • 1
    $\begingroup$ mathworld.wolfram.com/TotientSummatoryFunction.html $\endgroup$
    – saulspatz
    Commented Mar 15, 2019 at 23:30
  • $\begingroup$ So basically you want to compute $\sum_{i\leq n} \varphi(i)$? $\endgroup$
    – tomasz
    Commented Mar 15, 2019 at 23:50
  • $\begingroup$ Yes but how do you compute it? $\endgroup$
    – Jaemin Kim
    Commented Mar 16, 2019 at 0:17
  • $\begingroup$ "let's say 2019" That's oddly specific. Where is this problem from, exactly? And are you supposed to calculate it by hand? $\endgroup$
    – Arthur
    Commented Mar 16, 2019 at 0:50
  • $\begingroup$ 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. $\endgroup$
    – Jaemin Kim
    Commented Mar 16, 2019 at 1:38

1 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.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .