Evaluate $$\sum_{n=1}^{64}(-1)^n \left\lfloor \dfrac{64}{n} \right\rfloor \varphi(n).$$

We have $$S = \sum_{n=1}^{64}(-1)^n \left\lfloor \dfrac{64}{n} \right\rfloor \varphi(n) = \sum_{n=1}^{32}\left\lfloor\dfrac{64}{2n}\right\rfloor \varphi(2n)-\sum_{n=1}^{32}\left\lfloor\dfrac{64}{2n-1}\right\rfloor \varphi(2n-1),$$ but this didn't seem to help. Can we relate this sum to the fact that $\displaystyle \sum_{k=1}^n\left\lfloor\dfrac{n}{k}\right\rfloor \varphi(k) = \dfrac{n(n+1)}{2}$? Also, $64$ is a power of $2$ so we may need to use that fact.


1 Answer 1


The identity you mention is indeed very relevant; also relevant is its proof, which rewrites the sum as $$\sum_{d=1}^n \left\lfloor \frac nd\right\rfloor \phi(d) = \sum_{k=1}^n \sum_{d \mid k} \phi(d)$$ and then uses the fact that $$\sum_{d \mid k} \phi(d) = k. \tag{1}$$ In this problem, we can similarly rewrite $$\sum_{d=1}^{64} (-1)^d \left\lfloor \frac{64}d\right\rfloor \phi(d) = \sum_{k=1}^{64} \sum_{d \mid k} (-1)^d \phi(d) \tag{2}$$ and now it remains to understand the behavior of the sum $$\sum_{d \mid k} (-1)^d \phi(d).$$

Factoring $k$ as $2^a \cdot b$, where $b$ is odd, we can group divisors of $k$ together as divisors of $b$ multiplied by a power of $2$ ranging from $2^0$ to $2^a$. This tells us $$\sum_{d \mid k} (-1)^d \phi(d) = \sum_{d \mid b} \sum_{i=0}^a (-1)^{2^i \cdot d} \phi(2^i \cdot d) = \sum_{d \mid b} \left(-\phi(d) + \sum_{i=1}^a 2^{i-1} \phi(d)\right) = (2^a-2)\sum_{d \mid b} \phi(d)$$ and knowing the identity $(1)$, we can write this as $(2^a-2)b = k - 2b$.

Substituting this into $(2)$, we get $$\sum_{d=1}^{64} (-1)^d \left\lfloor \frac{64}d\right\rfloor \phi(d) = \sum_{k=1}^{64} (k - 2 \operatorname{odd}(k)) = \frac{64 \cdot 65}{2} - 2 \sum_{k=1}^{64} \operatorname{odd}(k)$$ where by $\operatorname{odd}(k)$ I denote the largest odd divisor of $k$.

Because the sum of the first $n$ odd numbers is $n^2$, we have $$\sum_{k=1}^{2n} \operatorname{odd}(k) = n^2 + \sum_{k=1}^n \operatorname{odd}(k)$$ by taking the odd and the even terms separately. By applying this rule repeatedly, we get a final answer of $$\frac{64 \cdot 65}{2} - 2\left(32^2+16^2+8^2+4^2+2^2+1^2+1^2\right) = -652.$$


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .