Relating Floor Function to Totient Function

I will prove in general that $\displaystyle \sum_{k \geq 1} \phi(k) \left \lfloor \dfrac{n}{k} \right \rfloor = \dfrac{n(n+1)}{2}.$

Note that $\left \lfloor \dfrac{n}{k} \right \rfloor$ is the expression for the number of multiples of $k$ less than or equal to $n$ . Thus, we can write $\left \lfloor \dfrac{n}{k} \right \rfloor$ as $\left \lfloor \dfrac{n}{k} \right \rfloor = \displaystyle \sum_{\substack{m \leq n\\ k \mid m}} 1.$

Thus, substituting this back into the original expression gives us \begin{aligned} \displaystyle \sum_{k \geq 1} \phi(k) \left \lfloor \dfrac{n}{k} \right \rfloor &= \displaystyle \sum_{k \geq 1} \phi(k) \displaystyle \sum_{\substack{m \leq n\\ k \mid m}} 1\\ &= \displaystyle \sum_{k \geq 1} \displaystyle \sum_{\substack{m \leq n\\ k \mid m}} \phi(k). \end{aligned}

If we instead consider this summation in $k$ , rather than in $m$ , we get \begin{aligned} \displaystyle \sum_{k \geq 1} \displaystyle \sum_{\substack{m \leq n\\ k \mid m}} \phi(k) &= \displaystyle \sum_{k \geq 1} \displaystyle \sum_{\substack{k \mid m\\ m \leq n}} \phi(k)\\ &= \displaystyle \sum_{m=1}^{n} \displaystyle \sum_{k \mid m} \phi(k). \end{aligned}

Now we can use the famous identity $\displaystyle \sum_{d \mid n} \phi(d) = n.$

to get $\begin{aligned} \displaystyle \sum_{m=1}^{n} \displaystyle \sum_{k \mid m} \phi(k) &= \displaystyle \sum_{m=1}^{n} m\\ &= \dfrac{n(n+1)}{2}. \end{aligned}$

Thus, proven.

Substituting $n=63$ gives us the answer of $2016$ .

Its easy to prove that if $F(n)=\sum_{d|n}^{}f(d)$

Then $\sum_{n=1}^{N}F(n)=\sum_{k=1}^{N}f(k)\left\lfloor N/k\right\rfloor$

If we consider $f(n) = \phi(n)$ We get $F(n) = \sum_{d|n}\phi(n) =n$

So $\sum_{k=1}^{N}\phi(k)\left\lfloor N/k\right\rfloor =\sum_{n=1}^{N}F(n)=\frac{n(n+1)}{2}$