0
$\begingroup$

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?

$\endgroup$
7
  • 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

0
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

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