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

4

If you define $S(n)$ as your sum:

$$S(n)=\sum_{m=1}^n \frac{m}{(m,n)}$$

then we will show that $2S(n)-1$ is multiplicative.

You can rewrite the sum as:

$$S(n)=\sum_{d\mid n} \sum_{m=1}_{(m,n)=d}^n \frac{m}{d}$$

Setting $k=m/d$, we get:

$$S(n)=\sum_{d\mid n} \sum_{k=1}_{(k,n/d)=1}^{n/d} k = \sum_{d\mid n}\sum_{k=1}_{(k,d)=1}^d k$$

So let $$f(d) = \sum_{k=1}_{(k,d)=1}^d k$$

It is not hard to show that this $f(1)=1$ and $f(d)=\frac{1}{2}\phi(d)d$ when $d>1$.

So we get:

$$S(n)=\frac{1}{2}+\frac{1}{2}\sum_{d\mid n} \phi(d)d$$

Now $g(n)=\sum_{d|n} d\phi(d)$ is multiplicative, since $n\phi(n)$ is, so $g(n)$ is determined by $$g(p^a) = 1+\sum_{i=1}^a p^i\phi(p^i) = \\1+\sum_{i=1}^a p^{2i-1}(p-1) = \\1 + p(p-1)\sum_{i=1}^a p^{2i-2} = \\1+p(p-1)\frac{p^{2a}-1}{p^2-1}=\\ \frac{p^{2a+1}+1}{p+1}$$

And in general, if $n=\prod p_i^{a_i}$ then $$g(n)=\prod \frac{p_i^{2a_i+1}+1}{p_i+1}$$

And your original sum is:

$$S(n)=\frac{1+g(n)}2$$

So, for example, $$g(12)=g(2^2)g(3^1)= \frac{2^5+1}{2+1}\frac{3^3+1}{3} = 11\cdot 7 = 77$$ So when $n=12$, your sum is $S(12)=\frac{77+1}{2}=39$.

For $n=143$, $$g(143)=g(11)g(13)=\frac{11^3+1}{11+1}\frac{13^3+1}{13+1} = 111\cdot 157 = 17427$$ and your sum is $S(143)=\frac{17427+1}{2}=8714$.

2

If $\ n=p\ $ is prime, we can say

$$\sum_{m=1}^p\frac{m}{gcd(m,n)}=1+\frac{2}{1}+...+\frac{p}{p}=1+2+...+(p-1)+1=\frac{(p-1)p}{2}+1$$

But in general, in spite of the fact that the number $\,22\,$ appears several times in the first few non-prime numbers, there doesn't seem to be an easy way out. For example:

$$\sum_{m=1}^{12}\frac{m}{gcd(m,n)}=1+\frac{2}{2}+\frac{3}{3}+\frac{4}{4}+\frac{5}{1}+\frac{6}{6}+\frac{7}{1}+\frac{8}{4}+\frac{9}{3}+\frac{10}{2}+\frac{11}{1}+\frac{12}{12}=39$$

1

We know $(m,n)=(n-m,n)$ where $1\le m \le n-1$

and $\frac n {(n,n)}=1$

So, $$\frac m {(m,n)}+\frac{n-m}{(n-m,n)}=\frac m {(m,n)}+\frac{n-m}{(m,n)}=\frac{n}{(n,m)}$$

If $n$ is odd, $m$ will be upto $\frac{n-1}2$

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

If $n$ is even, $m$ will be upto $\frac{n}2$. Here for $$m=\frac n 2, \frac{\frac n 2}{(\frac n 2, n)}=1$$

$ \sum_{m =1}^n {m\over\gcd(m,n)}=1+n \sum_{m =1}^{\frac{n-2}2}\frac 1{(m,n)}$

  • 0
    :i see a recursion here2012-10-09
  • 0
    @user43255, could you please elaborate a bit more?2012-10-09
  • 0
    : I mean,it is quite similar if we can express the simplified summation which you derived in a format similar to original expression,I think than the problem is solved2012-10-09
  • 0
    Nice use of symmetry.2012-10-09
  • 0
    @AndréNicolas, thanks. But unfortunately, it didn't lead me much further.2012-10-10
  • 0
    Well, it gives easy way to compute at powers of $p$, and elsewhere. (I have not written down anything, just thought about it while driving.)2012-10-10
1

For every divisor $d|n$ there will be some $m$ such that $\gcd(m,n)=d$, namely precisely those of the form $m=kd$ with $\gcd(k,\frac nd)=1$ and $1\le k\le \frac nd$. Note that with $$\tag1f(n):=\sum_{1\le k\le n\atop \gcd(k,n)=1}k$$ we have $$F(n)=\sum_{d|n}f(d)$$ as your function in question. As $\gcd(k,n)=\gcd(n-k,n)$, the summands in $(1)$ can be paired off into $\frac{\phi(n)}2$ summands $k+(n-k)=n$. One checks the special cases $n=1$ and $n=2$ separately to see that $$f(n)=\begin{cases}\frac{n\phi(n)}2&n>1\\1&n=1\end{cases}$$ holds. The function $\tilde f(n)=n\phi(n)$ would be a multiplicative function, hence so would $\tilde F(n)=\sum_{d|n}d\phi(d)$. Thus to compute $\tilde F(n)$ it is sufficient to know the values at prime powers. We have for $p$ prime and $k\ge 1$ $$p^k\phi(p^k)=\left(1-\frac1p\right)p^{2k},$$ hence $$\tilde F(p^k)=1+\left(1-\frac1p\right)\sum_{r=1}^kp^{2r}=1+\left(1-\frac1p\right)\cdot\frac{p^{2k+2}-p^2}{p^2-1}=1+p\cdot \frac{p^{2k}-1}{p+1}.$$ Thus finally we have $$\tag2F(n)=\frac12 (\tilde F(n)+1) = \frac12+\frac12\prod_{p|n}\left(1+p\cdot \frac{p^{2k}-1}{p+1}\right).$$

Remark: From the expression $p\cdot \frac{p^{2k}-1}{p+1}$ it is not surprising that cyclotomic polynomials play a role for $F(p^k)$.

0

Continuing DonAntonio's answer let's examine the case where $n=pq $ whith $p>q$ primes.

In this case we have (using inclusion $-$ exclusion): $$ \displaystyle{\sum_{m=1}^{pq}\frac{m}{\gcd(m,pq)}= \sum_{i=1}^{pq}i-(q\sum_{i=1}^{p}i+ p\sum_{i=1}^{q}i-pq)+\sum_{i=1}^{p-1}i+\sum_{i=1}^{q-1}i+1=\\ \frac{pq(pq-1)}{2}-\frac{(p+q)(p-1)(q-1)}{2}+1} \ . $$

For example, for $n=22$ we have that $\displaystyle{\sum_{m=1}^{n}\frac{m}{\gcd(m,n)}=167 \ }$ and for $n=13\cdot 29=377$ we have that $\displaystyle{\sum_{m=1}^{n}\frac{m}{\gcd(m,n)}=63821 \ .}$

To go little further we have with the same method the following:

$$ \text{for} \ n=p \ , \displaystyle{\sum_{m=1}^{n}\frac{m}{\gcd(m,n)}=\frac{p(p-1)}{2}+1=\frac{p\phi_1(p)}{2}+1} ,\\ \text{for} \ n=p^2 \ , \displaystyle{\sum_{m=1}^{n}\frac{m}{\gcd(m,n)}=\frac{p(p-1)(p^2+1)}{2}+1=\frac{p\phi_1(p)\phi_4(p)}{2}+1} ,\\ \text{for} \ n=p^3 \ , \displaystyle{\sum_{m=1}^{n}\frac{m}{\gcd(m,n)}=\frac{p(p-1)(p^2+p+1)(p^2-p+1)}{2}+1=\frac{p\phi_1(p)\phi_3(p)\phi_6(p)}{2}+1} ,\\ \text{for} \ n=p^4 \ , \displaystyle{\sum_{m=1}^{n}\frac{m}{\gcd(m,n)}=\frac{p(p-1)(p^2+1)(p^4+1)}{2}+1=\frac{p\phi_1(p)\phi_4(p)\phi_8(p)}{2}+1} ,\\ \text{for} \ n=p^5 \ , \displaystyle{\sum_{m=1}^{n}\frac{m}{\gcd(m,n)}=\frac{p\phi_1(p)\phi_5(p)\phi_{10}(p)}{2}+1} ,\\ \text{for} \ n=p^6 \ , \displaystyle{\sum_{m=1}^{n}\frac{m}{\gcd(m,n)}=\frac{p\phi_1(p)\phi_3(p)\phi_4(p)\phi_6(p)\phi_{12}(p)}{2}+1} $$

where $p>2$ and $\phi_n$ is the $n^{th}$ cyclotomic polynomial.

  • 0
    I get 8714 (both with my formula and explicitly) for $n=143$.2012-10-09
  • 0
    @Hagen von Eitzen: Of course you are right. I get the same with my formula. I corrected my mistake. Thanks.2012-10-09