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.


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.$$


Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.