Fast way to find the sum of LCM of the given range of numbers?

Question

I want to find the sum of LCM of a given range of integers. For example:

Input: $5$
Output:

\begin{align} \sum_{i=1}^5 \mathrm{LCM}(i,5) & = \mathrm{LCM}(1,5) +\mathrm{LCM}(2,5) +\mathrm{LCM}(3,5) + \mathrm{LCM}(4,5) + \mathrm{LCM}(5,5) \\ & = 5 + 10 + 15 + 20 + 5 \\ & = 55 \end{align}

The method I use right now is to find the $\mathrm{GCD}(a,b)$ using Euclidean method and them compute $\mathrm{LCM}(a,n)$ as $\frac{|ab|}{\mathrm{GCD}(a,b)}$. The problem with this method is that it's very slow for inputs in the range of $1 < n < 10^5$.

I got some details of using Euler's totient function to do the same but I don't understand it completely.The one property which I understood is a $\phi(p) = p-1$ where $p$ is prime and I couldn't understand how to use this to improve the speed of my problem.The current algorithm which I use runs at $O(n^2)$ and I need to do better than that.

Answer 1

You may speed it up a bit by making only 1 multiplication:

$$\sum_{i=1}^n\text{lcm}(i,n)=\sum_{i=1}^n\frac{i n}{\gcd(i,n)}=n\sum_{i=1}^n\frac{i}{\gcd(i,n)}$$

Since $i$ is divisible by $\gcd(i,n)$ that can be computed using only integer arithmetic. This has $O(n*log(n))$ complexity but is in constant factor faster than naive solution (2nd formula).

Answer 2

As far as i know the euklidian algorithm for gcd runs in $O(\log n)$, this would give you a total complexity of $O(n \log n)$, wich is a lot faster than your $O(n^2)$ algorithm. I programmed it in python and for $n=10^5$ it only needed a second.

About the Eulers totient: calculating $\phi(n)$ is as fast as factorizing $n$. if $n=\prod_{i \in I}p_i^{v_i}$ for $p_i$ prime numbers, then $\phi(n) = \prod_{i \in I}(p_i^{v_i-1} (p_i -1))$. It counts the numbers $k$ from $1$ to $n$ with $gcd(k,n)=1$ , but i am not sure if it can be used for a very efficient algorithm (faster than $O(n \log n)$ ).