Take the 2-minute tour ×  The problem is contained in the
headline: Is it possible to simplify the sum $\displaystyle
\sum\limits_{k=1}^n 2^{\text{gcd}(k,n)}$?  share|improve this
question $$\sum_{k=1}^n 2^{\gcd(k,n)} = \sum_{d \vert
n}\phi(n/d) 2^d$$ I do not know if this can be simplified
further. –  user17762 Jan 18 '13 at 0:31 The equation in
Marvis's comment is a special instance of a polynomial identity:
$\sum_{k=1}^n x^{\gcd(k,n)} = \sum_{d|n} \varphi(n/d)x^d$. At $x
= 1$ it is the equation $n = \sum_{d|n} \varphi(d)$. At $x = 2$
it is the equation Marvis wrote down. –  KCd Jan 18 '13 at 4:17
add comment  1 Answer  As Marvis said,
$$\sum_{k=1}^n2^{\text{gcd}(k,n)}=\sum_{d\mid
n}\varphi(n/d)2^d.$$ Here's a cool article I found on OEIS
detailing one way the expression occurs in combinatorics.
share|improve this answer add comment  Your Answer