Problem 1974

Our solution will be based upon the following key observation, for which we provide two different proofs.

Lemma 1. Let $p$ be a prime. If $p^s$ divides $n$, then $2^{s-1}$ divides $a_n - a_{n-1}$, where $a_0 = 0$.

*First proof of Lemma 1.* We argue by induction on $s$ and then $n$. First, the base case $s=1$ is vacuous. Now assume the claim holds for some $s-1$, and suppose that there existed some smallest $n$ such that $p^s$ divides $n$ but $2^{s-1}$ does not divide $a_n - a_{n-1}$. Consider the auxiliary sequence defined by $b_n = a_n - a_{n-1}$. By the given, the sequence $b_n$ satisfies
$$b_n = \sum_{i=2}^{n} \left( a_{\lfloor \frac{n}{i} \rfloor} - a_{\lfloor \frac{n-1}{i} \rfloor} \right) = \sum_{\substack{i|n \\ i>1}} b_{n/i} = \sum_{\substack{i|n \\ i<n}} b_i. \qquad (1)$$
Applying (1), we see that
$$b_{n/p} = \sum_{\substack{i|n/p \\ i<n/p}} b_i,$$
so we may write
$$b_n = b_{n/p} + \sum_{\substack{i|n/p \\ i<n/p}} b_i + \sum_{\substack{i|n \\ i \nmid n/p \\ i<n}} b_i = 2b_{n/p} + \sum_{\substack{i|n \\ i \nmid n/p \\ i<n}} b_i. \qquad (2)$$
Notice that $p^{s-1} \mid n/p$, so by the inductive hypothesis, we see that $2^{s-1} \mid 2b_{n/p}$. Further, for any $i < n$ dividing $n$ but not $n/p$, we have that $p^s \mid i$, hence $2^{s-1} \mid b_i$ because $i < n$ and $n$ was chosen to be the smallest multiple of $p^s$ for which $2^{s-1} \nmid b_n$. Therefore, (2) shows that $2^{s-1} \mid b_n$, a contradiction. This completes the induction, showing that if $p^s \mid n$, then $2^{s-1} \mid a_n - a_{n-1}$. $\square$

*Second proof of Lemma 1.* Let us interpret the sequence $a_n$ combinatorially as follows. Call a finite increasing sequence of integers $k_1 < k_2 < \dots < k_r$ good if $k_1 = 1$ and $k_j \mid k_{j+1}$ for each $1 \le j < r$. Let $c_n$ be the number of good sequences whose last term is at most $n$. Then, we claim that $a_n = c_n$.

Indeed, for any $1 < k \le n$, good sequences with second term $k$ and last term at most $n$ are in bijection with good sequences with last term at most $\lfloor n/k \rfloor$; here, the bijection is provided by dividing each term after the first by $k$. Counting also the sequence consisting of the single term 1, we obtain the recurrence
$$c_n = c_{\lfloor n/2 \rfloor} + c_{\lfloor n/3 \rfloor} + \dots + c_{\lfloor n/n \rfloor} + 1.$$
Observe further that $c_1 = a_1 = 1$, meaning that the sequence $\{c_n\}$ satisfies the same recurrence and initial conditions as $\{a_n\}$. Therefore, we obtain $a_n = c_n$.

Now, note that $a_n - a_{n-1}$ is the number of good sequences whose last term is exactly $n$. It suffices therefore to show that if $p^s$ is the highest power of $p$ dividing $n$, then the number of good sequences ending in $n$ is divisible by $2^{s-1}$. Let the $p$-skeleton of a good sequence $k_1, \dots, k_r$ be the sub-sequence consisting of all the terms $k_j$ such that $k_j/k_{j-1}$ is not a power of $p$ (including the initial 1). It suffices for us to show that the number of good sequences ending in $n$ with a given $p$-skeleton is divisible by $2^{s-1}$.

Take any $p$-skeleton, which we may write in the form
$$p^{t_1} k'_1, p^{t_2} k'_2, \dots, p^{t_m} k'_m$$
for some $t_1, \dots, t_m$ and $k'_1, \dots, k'_m$ satisfying $t_1 = 0$, $k'_1 = 1$, $p \nmid k'_j$, $k'_1 \mid k'_2 \mid \dots \mid k'_m$, and $t_1 \le t_2 \le \dots \le t_m$. Now, to form a good sequence ending in $n$ that has this $p$-skeleton, between any two consecutive terms $p^{t_j} k'_j, p^{t_{j+1}} k'_{j+1}$ of the $p$-skeleton we can insert any subset of the set
$$\{p^{t_{j+1}} k'_j, p^{t_{j+2}} k'_j, \dots, p^{t_{j+1}} k'_j\}.$$
Also, if the last term $p^{t_{r'}} k'_{r'}$ is not equal to $n$, we can insert any subset containing $n$ of
$$\{p^{t_{r'}+1} k'_{r'}, p^{t_{r'}+2} k'_{r'}, \dots, p^{s-1} k'_{r'}\}$$
after it. Hence, for each $t = 1, \dots, s-1$, there is exactly one number of the form $p^t k$ with $p \nmid k$ that we can choose to include or not in our good sequence. For $t = s$, we can choose to include the number if $n$ is not in the skeleton; otherwise including it is obligatory. So the number of good sequences ending in $n$ that have the given $p$-skeleton is either $2^{s-1}$ or $2^s$, depending whether or not $n$ is part of the skeleton; in any case, it is divisible by $2^{s-1}$. It follows that the total number of good sequences ending in $n$ is divisible by $2^{s-1}$, establishing the lemma. $\square$

We now consider the problem proper. For any positive integer $m$, choose distinct primes $p_1, p_2, \dots, p_m$. By the Chinese Remainder Theorem, there exists some $k$ such that $k + i$ is divisible by $p_i^s$ for $1 \le i \le m$. By Lemma 1, this implies that $a_{k+i} - a_{k+i-1}$ is divisible by $2^{s-1}$ for $1 \le i \le m$, meaning that $a_k, a_{k+1}, \dots, a_{k+m}$ are all congruent modulo $2^{s-1}$. For any $N$, if we take $m > N + 2^{s-1} - 1$, there exist positive integers $k$ and $n \in \{k+N, \dots, k+N+2^{s-1}-1\}$ such that $a_n \equiv n \pmod{2^{s-1}}$. In particular, this $n$ satisfies $n > N$. Therefore, for any positive integer $s$, the set of $n$ such that $a_n \equiv n \pmod{2^{s-1}}$ is unbounded, hence infinite. Taking $s = 2011$ gives the desired result.