9
$\begingroup$

$$ \sum_{m =1}^n {m\over\gcd(m,n)}$$

For example, for 1 it is

$${1\over\gcd(1,1)} =1;$$

for 5 it is $${1\over \gcd(1,5)}+{2\over \gcd(2,5)}+{3\over \gcd(3,5)}+{4\over \gcd(4,5)}+{5\over \gcd(5,5)}=\\ \frac11+\frac21+\frac31+\frac41+1 = \\ 1+2+3+4+1= \\ 11$$

  • 0
    @MJD: thanks a lot for the excellent editing and formatting2012-10-09
  • 0
    I didn't get exactly the question, could you be a bit more explicit please?2012-10-09
  • 0
    @GiovanniDeGaetano That was my fault. I have tried to make the question more explicit: OP wants to compute the indicated sum.2012-10-09
  • 0
    @GiovanniDeGaetano:sir if you need any clarifications for the question ,please comment. Also,I think answer could involve use of the totient function.2012-10-09
  • 0
    [OEIS](http://oeis.org/A057661) does not give any simple closed form, which it surely would if one were known. It does point out that the sum is equal to $1 + \frac12\sum_{d\vert n} d\cdot\varphi(d)$, where $\varphi$ is the Euler totient function.2012-10-09
  • 0
    @MJD:I checked there before posting,but I am quite sure the answer is a term which doesn't involve any summation and can be probably be calculated by maximum 100 operations even for N=100000002012-10-09
  • 0
    @user43255 You could calculate it quickly if you already knew the prime factorization of $n$; other than that, I don't see any reasonable approach. Why are you so sure?2012-10-09
  • 0
    Actually the prime factorization of n is known and also of all the numbers before n,however still iterating for all m for evaluation the expression ,doesn't seem likely at all.2012-10-09
  • 0
    See my answer. It depends on the prime factorization of $n$. For $n=10000000=2^7\cdot 5^7$ the value is $$\frac{1+\frac{2^{15}+1}{3}\frac{7^{15}+1}{8}}{2}$$2012-10-10

5 Answers 5