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
    Mar 15 '19 at 23:30
  • $\begingroup$ So basically you want to compute $\sum_{i\leq n} \varphi(i)$? $\endgroup$
    – tomasz
    Mar 15 '19 at 23:50
  • $\begingroup$ Yes but how do you compute it? $\endgroup$
    – Jaemin Kim
    Mar 16 '19 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
    Mar 16 '19 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
    Mar 16 '19 at 1:38

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.