For a positive integer $n$, let $g(n) = \left[ \displaystyle \frac{2024}{n} \right]$. Find the value of $$\sum_{n = 1}^{2024}\left(1 - (-1)^{g(n)}\right)\phi(n).$$
Problem
Source: KMO 2024 P6
Tags: number theory
09.11.2024 12:54
I used induction to show that the sum is \( 2 \cdot (1012)^2 \). I wonder if there are other approaches, such as double counting.
09.11.2024 13:19
My solution in the contest We will calculate the following function, where $[\bullet]$ is iverson bracket. $$F(N) := 2\sum_{n = 1}^{N}\left [2 \nmid \left \lfloor \dfrac{N}{n} \right \rfloor \right] \cdot \phi(n)$$Denote $G(N)$ as follows. $$G(N) := \sum_{n = 1, \,\, 2 \nmid n}^{N}\left [2 \nmid \left \lfloor \dfrac{N}{n} \right \rfloor \right] \cdot \phi(n)$$We will calculate $G(N)$, and then calculate $F(N)$. If $2 \mid \left \lfloor\dfrac{N}{n} \right \rfloor$ and $2 \nmid \left \lfloor\dfrac{N+1}{n} \right \rfloor$ or $2 \nmid \left \lfloor\dfrac{N}{n} \right \rfloor$ and $2 \mid \left \lfloor\dfrac{N+1}{n} \right \rfloor$, we have $\left \lfloor\dfrac{N}{n} \right \rfloor \neq \left \lfloor \dfrac{N+1}{n} \right \rfloor$ which implies $n \mid N+1$. Therefore, we can easily see that $$G(N) = G(N-1) + (-1)^{N-1}\sum_{n \mid N+1, \,\, 2 \nmid n}{\phi(n)}$$This implies that from $\sum_{d \mid \ell}\phi(d) = \ell$, $$G(N) = \sum_{k = 1}^{N}(-1)^{k-1} \cdot \dfrac{k}{2^{\nu_2(k)}}$$ Now, since if $2^v \mid\mid k$, let $k = 2^v t$ for odd $t$, then $\left [2 \nmid \left \lfloor \dfrac{N}{k} \right \rfloor \right] = \left [2 \nmid \left \lfloor \dfrac{\lfloor N/2^v \rfloor }{t} \right \rfloor \right] $. Hence, since $\phi(k) = 2^{v-1}\phi(t)$, we can calculate $F(N)$ as follows. $$F(N) = G(N) + \sum_{v \ge 0}G\left( \left \lfloor \dfrac{N}{2^v} \right \rfloor \right)$$By substituting $G$, we get the following form. $$\begin{aligned} F(N) &= G(N) + \sum_{v \ge 0}2^v\sum_{k = 1}^{\lfloor N / 2^v \rfloor}(-1)^{k-1} \cdot \dfrac{k}{2^{\nu_2(k)}} \\ &= G(N) + \sum_{k = 1}^{N}{k \cdot \left(1 - \left \lfloor \log_2 \dfrac{N}{k} \right \rfloor \right)}\end{aligned}$$Now, we only need to calculate the above value. As $G$ can be represented in the following form, $$G(N) = \sum_{k = 1}^{N}[2 \nmid k] \cdot k \left(1 - \left \lfloor \log_2 \dfrac{N}{k} \right \rfloor \right) = F(N) - G(N) - \sum_{k = 1}^{N}[2 \mid k]\cdot k \left(1 - \left \lfloor \log_2 \dfrac{N}{k} \right \rfloor \right)$$Here, now we can put this again in $F(N)$, which implies that $$F(N) = 2\sum_{k = 1}^{N}{k \cdot \left(1 - \left \lfloor \log_2 \dfrac{N}{k} \right \rfloor \right)} - \sum_{k = 1}^{\lfloor N/2 \rfloor}{2k \left(1 - \left \lfloor \log_2 \dfrac{N}{2k} \right \rfloor \right)} = 2\sum_{k = 1}^{N}{k \cdot \left(1 - \left \lfloor \log_2 \dfrac{N}{k} \right \rfloor \right)} - 2\sum_{k = 1}^{\lfloor N/2 \rfloor}{k \left(2 - \left \lfloor \log_2 \dfrac{N}{k} \right \rfloor \right)}$$Therefore, we can finally get the desired $F$, $$F(N) = N(N+1) - 2 \cdot \left \lfloor \dfrac{N}{2} \right \rfloor \left( \left \lfloor \dfrac{N}{2} \right \rfloor + 1\right) -2 \sum_{k = \lfloor N/2 \rfloor+1}^{N}{k \cdot \left \lfloor \log_2 \dfrac{N}{k} \right \rfloor} = N^2- 2 \left \lfloor \dfrac{N}{2} \right \rfloor ^2 + [2 \nmid N]$$
09.11.2024 13:19
Here is a nice solution. Lemma: $\sum_{n = 1}^{m}\left[\frac{m}{n}\right]\phi(n) = \frac{m(m + 1)}{2}$ Proof: $\sum_{n = 1}^{m}\left[\frac{m}{n}\right]\phi(n) = \sum_{n = 1}^{m}\phi(n)\sum_{n \mid k}1 = \sum_{k = 1}^{m}\sum_{n \mid k}\phi(n) = \sum_{k = 1}^{m}k = \frac{m(m + 1)}{2}. \ \square$ The rest is just all calculation. \begin{align*} \sum_{n = 1}^{2024}\left(1 - (-1)^{g(n)}\right)\phi(n) &= \sum_{n = 1}^{2024}2\left(g(n) - 2\left[\frac{g(n)}{2}\right]\right)\phi(n) \\ &= 2\sum_{n = 1}^{2024}\left(\left[\frac{2024}{n}\right] - 2\left[\frac{1012}{n}\right]\right)\phi(n) \\ &= 2\sum_{n = 1}^{2024}\left[\frac{2024}{n}\right]\phi(n) - 4\sum_{n = 1}^{2024}\left[\frac{1012}{n}\right]\phi(n) \\ &= 2\cdot \frac{2024\cdot 2025}{2}- 4 \cdot \frac{1012 \cdot 1013}{2} = \frac{2024^2}{2}. \ \blacksquare \end{align*}