Problem:
$$S=\text{lcm}(m,n) + \text{lcm}(m+1,n) +\ldots+ \text{lcm}(n,n)$$
There is already a question on math.stackexchange for $[1,n]$ range . I am trying to generalise it further for $[m,n]$ range.
My thoughts:
- $\operatorname{lcm}(m, n) + \operatorname{lcm} (n-m, n) = \frac{ mn } { \gcd(m, n)} + \frac{ (n-m)n} { \gcd(n-m, n)} = \frac{ n\times n} { \gcd(m,n) }$. should hold here too
We can write the required series as, $S = \sum_{i=m}^{n} \frac{i.n}{gcd(i,n)}=n\sum_{i=m}^{n} \frac{i}{gcd(i,n)}$
$ A332049(n) = \sum_{i=1}^{n-1} \frac{i}{gcd(i,n)}$
$\implies A332049(n) + 1 = \sum_{i=1}^{m-1} \frac{i}{gcd(i,n)} + \sum_{i=m}^{n} \frac{i}{gcd(i,n)} $
$\implies A332049(n) + 1 = \sum_{i=1}^{m-1} \frac{i}{gcd(i,n)} + S/n $
$\implies A332049(n) + 1 - \sum_{i=1}^{m-1} \frac{i}{gcd(i,n)} = S/n $
A332049 above refers to this oeis series
As evident we didn't benefit much from this substitution. As splitting additively into two didn't help, My hunch is we might need to split the series into two or more multiplicatively/recursively. And also I feel sum or difference of totients might come into play rather than mere totients for this. I am smelling possibility of principle of inclusion exclusion.
Another way I am thinking is,
for all $d$ in divisors of $n$
$S=$
$ \sum_{d|n}(n/d)[ (\varphi(n/d) - \sum_{i=1}^{m-1}|(gcd(i,n)=d)| ]$
I don't know how to evaluate the second part efficiently
Summarise:
Be it
$\sum_{i=1}^{m-1} \frac{i}{gcd(i,n)} $
or
$\sum_{i=1}^{m-1}|(gcd(i,n)=d)| $
whicheverso closed form you can suggest would do the job.