I didn't know there was a formula II

Let $S(k)$ be the sum, then, using the identity $\text{lcm}(a,b)\gcd(a,b)=ab$ we get $\displaystyle S = \sum_{i=1}^{k} \dfrac{ik}{\gcd(i,k)} = k \sum_{i=1}^{k} \dfrac{i}{\gcd(i,k)}$ .

We know that if $d \mid k$ and $\gcd\left(q, \dfrac{k}{d}\right)=1$ where $1 \leq q \leq \dfrac{k}{d}$ , then $\gcd(dq, k)=d$ and $1 \leq dq \leq k$ . With this result, we know that for some $i=dq$ we will have $\dfrac{i}{\gcd(i,k)}=\dfrac{dq}{\gcd(dq,k)}=\dfrac{dq}{d}=q$ , so our sum becomes $\displaystyle S=k \sum_{d \mid k} \sum_{\gcd\left(q,\frac{k}{d}\right)=1} q=k \sum_{d \mid k} \sum_{\gcd\left(q,d\right)=1} q$ .

Now let's find the sum inside, we will call it $T$ . Basically we are adding all the coprimes $q$ with $d$ less than $d$ . We know that there are $\phi(d)$ such values, let them be $q_1, q_2, \ldots, q_{\phi(d)}$ , so the sum is $T=q_1 + q_2 + \cdots + q_{\phi(d)}$ . We also know that $\gcd(q,d)=\gcd(d-q,d)$ , so the sum is also $T=d-q_1 + d-q_2 + \cdots + d-q_{\phi(d)}$ . We add that two expressions to obtain $2T=\underbrace{d + d + \cdots + d}_{\phi(d)\text{ times}}$ , so $T=\dfrac{1}{2}d\phi(d)$ . But when $d=1$ , we have $T=1$ and not $T=\dfrac{1}{2}$ , so we must add $\dfrac{1}{2}$ :

$\displaystyle S=k\left(\dfrac{1}{2}+\sum_{d \mid k} \dfrac{1}{2} d \phi(d)\right)=\dfrac{k}{2}\left(1+\sum_{d \mid k} d \phi(d)\right)$ . Since $d$ and $\phi(d)$ are multiplicative functions, $\displaystyle \sum_{d \mid k} d \phi(d)$ is also multiplicative. Finally: $\begin{aligned} \sum_{d \mid p^a} d \phi(d) &= \sum_{i=0}^{a} p^i \phi(p^i)\\ &= 1 + \sum_{i=1}^{a} p^i p^i \left(1 - \dfrac{1}{p}\right)\\ &= 1 + \left(1 - \dfrac{1}{p}\right)\sum_{i=1}^{a} p^{2i}\\ &= 1 + \dfrac{p-1}{p} \cdot \dfrac{p^{2(a+1)}-p^2}{p^2-1} \\ &= 1 + \dfrac{p^{2a+1}-p}{p+1} \\ &= \dfrac{p^{2a+1}+1}{p+1}\\ \implies S(k) &= \dfrac{k}{2}\left(1 + \prod_{i=1}^{n} \dfrac{{p_i}^{2a_i+1}+1}{p_i+1}\right) \end{aligned}$

Relevant wiki: Dirichlet Convolution

For this solution, I will do an extensive analysis of the given arithmetic function. I will heavily use theorems from the theory of Dirichlet multiplication so I encourage the reader to learn that before reading my solution. Needless to say, I consider this problem to be very advanced.

First, I will rewrite this problem in terms of the greatest common divisor, which I will just write as $(a,b)$ . This is just a choice I made given that I know a special theorem that will be of great help later that has to do with the gcd. I am sure an equivalent could be found for the lcm but I leave that to the reader: We know that $lcm(i,k) = \frac{ik}{(i,k)}$ so our sum is $k \sum_{i=1}^k \frac{i}{(i,k)}$ . Now, first ask the question "what values can (i,k) take?". The answer is the divisors of $k$ so this is equal to $k \sum_{d | k} \sum_{n \leq k, (n,k) = d} \frac{n}{d}$ .

Now, if $(n,k) = d$ that implies that $d$ divides $n$ so we may use the substitution $n = qd$ . If we do this then we must change the bound $n \leq k$ to $q \leq \frac{k}{d}$ . And, more importantly, $(n,k) = d \iff (g, \frac{k}{d}) = 1$ . So rewriting, our sum is equal to: $k \sum_{d | k} \sum_{q \leq \frac{k}{d} , (q, \frac{k}{d} ) = 1} q$ . Now, for a moment I will just focus on $\sum_{q \leq \frac{k}{d} , (q, \frac{k}{d} ) = 1} q$ :

Here is the big theorem I will apply: It can be proven (this can found in an exercise from Apostol's Analytic Number Theory textbook) that $\sum_{ n \leq x , (n,k) = 1} f(n) = \sum_{d | k} \mu(d) \sum_{q \leq \frac{x}{d}} f(qd)$ . This is very beautiful, and the sole reason why I rewrote my sum in terms of $(a,b) = 1$ .

If we now apply this theorem to $\sum_{q \leq \frac{k}{d} \\ (q, \frac{k}{d} ) = 1} q$ we get $\sum_{e | \frac{k}{d} } \mu(e) \sum_{l \leq \frac{k}{de}} el = \sum_{e | \frac{k}{d}} e \mu(e) \sum_{l = 1}^{\frac{k}{de}} l$ . And now we apply the elementary theorem, $\sum_{k=1}^n k = \frac{n(n+1)}{2}$ .

Let $u = \frac{k}{de}$ to get $\sum_{e | \frac{k}{d}} e \mu(e) \frac{u(u+1)}{2} = \frac{1}{2} \sum_{e | \frac{k}{d}} e \mu(e) u^2 + \frac{1}{2} \sum_{e | \frac{k}{d}} e \mu(e)u$ . Simplifying this we get $\frac{1}{2} \frac{k}{d} \sum_{e | \frac{k}{d}} \mu(e) \frac{k}{de} + \frac{1}{2} \sum_{e | \frac{k}{d}} \mu(e) \frac{k}{d}$ . And applying our identities for Dirichlet multiplication we can spot that this is equal to $\frac{k}{2d} \phi ( \frac{k}{d}) + \frac{k}{2d} I(\frac{k}{d})$ where $I$ is the identity function for Dirichlet multiplication.

Going back to our entire expression, the complete sum we are working on is equal to $k \sum_{d | k} \frac{k \phi( \frac{k}{d})}{2d} + \frac{k I(\frac{k}{d})}{2d}$ . To simplify this, first remember that $I(n)$ is equal to 0 unless $n=1$ , when it will equal 1. So in our sum, it will be zero except for when $d = k$ so that part of the sum will reduce to $\frac{k I(1)}{2k} = \frac{1}{2}$ so the sum is equal to $k \sum_{d | k} \left( \frac{k \phi( \frac{k}{d})}{2d} \right)+ \frac{k}{2} = \frac{k}{2} \left( \sum_{d | k} \left( \frac{k \phi( \frac{k}{d})}{d}\right) + 1 \right)$ .

For a final simplification, simply notice that $\sum_{d | k} \frac{k \phi( \frac{k}{d})}{d} = k \sum_{d | k} \frac{ \phi( \frac{k}{d})}{d} = k \left[ \frac{1}{n} * \phi(n) \right] = k \sum_{d | k} \phi(d) \frac{d}{k} = \sum_{d | k} d \phi(d)$ . Now, this function may not be the most famous one but it is the Dirichlet product of two multiplicative functions, which implies it itself is multiplicative. This means that we can find a product expansion of this function by evaluating it at prime powers. I will omit this part of the work given that this is a trivial application of the geometric series formula. If you do the work of evaluating it at prime powers you will obtain the product expansion of this function: $\prod_{i = 1}^{w(k)} \frac{p_i^{2a_i + 1} + 1}{p_i+1}$ . Substituting this into our last expression for the complete sum we obtain:

$\frac{k}{2} \left(1 + \prod_{i = 1}^{w(k)} \frac{p_i^{2a_i + 1} + 1}{p_i+1} \right)$