Hello. Define $a_0 = 0$, and let $b_n = a_{n} - a_{n-1}$ for $n \geq 1$. Then, we have, for $n > 1$, \begin{align*} b_n &= a_n - a_{n - 1}\\ &= (a_{\lfloor n/2\rfloor}-a_{\lfloor (n-1)/2\rfloor})+(a_{\lfloor n/3\rfloor}-a_{\lfloor (n-1)/3\rfloor})+\ldots+(a_{\lfloor n/(n-1)\rfloor}-a_{\lfloor (n-1)/(n-1)\rfloor}) + a_{\lfloor n/n \rfloor} \end{align*} But for all $d \not| n$, $\lfloor n/d\rfloor = \lfloor (n-1)/d\rfloor$, so all the terms in the sum vanish except those of the form $a_{\lfloor n/d\rfloor}-a_{\lfloor (n-1)/d\rfloor}$ for $d| n$. We have $a_{\lfloor n/d\rfloor}-a_{\lfloor (n-1)/d\rfloor}=a_{n/d}-a_{n/d - 1} = b_{n/d}$, so we can write (for $n > 1$) \[b_n = \sum_{d | n, d \neq 1} b_{n/d} = \sum_{d | n, d \neq n} b_{d}.\] For all $n \geq 1$, then, we have \[b_n = f(n) + \sum_{d | n, d \neq n} b_{d}\] where $f(n) = 1$ for $n = 1$ and $f(n) = 0$ otherwise. This means that \[2b_n - f(n) = \sum_{d | n} b_{d}\] for all $n \geq 1$. Inverting this (using the Mobius inversion formula), we get $b_n = \sum_{d | n} \mu\left(\frac{n}{d}\right)(2b_{d} - f(d)) = 2\sum_{d | n}\left( \mu\left(\frac{n}{d}\right)b_{d}\right) - \mu(n)$. By induction, then, $p^{k+1} | n$ implies $2^k | b_n$ for prime $p$ and positive integer $k$. By the Chinese remainder theorem, we can find infinitely many runs of $2^{2010} - 1$ consecutive integers which are divisible by the 2011th power of some prime, which means that the corresponding $b_n$ are divisible by $2^{2010}$, which means that the corresponding $a_n$ are the same mod $2^{2010}$, which means that one of them is congruent to the $n$, which means we're done.

I was just wondering, what is the motivation for coming up with this lemma: numbertheorist17 wrote: Lemma 1. Suppose that $p^k|m$ for a prime $p$ and positive integer $k$. Then, $2^{k-1}|d_m$

MathPanda1 wrote: I was just wondering, what is the motivation for coming up with this lemma: numbertheorist17 wrote: Lemma 1. Suppose that $p^k|m$ for a prime $p$ and positive integer $k$. Then, $2^{k-1}|d_m$ The way I find this is by bashing out small values of $d_n$. You also see why we consider $d_n$ instead of the original sequence by bashing because when computing $a_n$ up to $8$ you will notice most of the $a_i$ don't change, and to find $a_{n+1}$ from $a_n$ is much easier than adding all previous terms $a_{\frac in}$ (and the change is given by difference of adjacent terms too).

Fantastic problem! For convenience, define $a_0=0$ and $b_i=a_{i}-a_{i-1}$ for all $i.$ Note that for all $n,k,$ we have that $\lfloor n/k\rfloor-\lfloor (n-1)/k\rfloor$ is $1$ if $k\mid n$ and $0$ otherwise. Therefore, by comparing the recursive definitions of $a_n$ and $a_{n-1},$ we can show that \[b_n=\sum_{\substack{d\mid n\\ d<n}}b_d\implies\sum_{d\mid n}b_{d}=\begin{cases}2b_n & n>1\\ 1 & n=1. \end{cases}\]Now, by Mobius Inversion, we obtain $$b_n=\mu(n)+\sum_{\substack{d\mid n\\d>1}}(2\mu(n/d)b_d)\implies b_n=-\mu(n)-2\sum_{\substack{d\mid n\\ 1<d<n}}(\mu(n/d)b_d).$$$\textbf{Claim: }$ If $p^{2^k}\mid n$ for prime $p,$ then $2^k\mid b_n.$ $\emph{Proof: }$ Induct on $k;$ for the base case, just note that $b_n\equiv \mu(n)\pmod{2},$ and $\mu(n)=0$ for $n$ divisible by a perfect square. Now assume the claim true for $k,$ and suppose $p^{2^{k+1}}\mid n.$ Then, for each divisor $d$ of $n,$ either $d$ or $n/d$ is divisible by $p^{2^k}.$ Therefore, either $b_d\equiv 0\pmod{2^k}$ (by the inductive hypothesis) or $\mu(n/d)=0.$ This means that the sum on the RHS dissapears modulo $2^{k+1},$ as desired. $\blacksquare$ Now let $p_i$ denote the $i$th prime. Choose $N$ such that $$p_1^{2^{2010}}\mid N+1,$$$$p_2^{2^{2010}}\mid N+2,$$$$\vdots$$$$p_{2^{2010}+1}^{2^{2010}}\mid N+2^{2010}+1.$$By our claim, $2^{2010}\mid b_{N+1},b_{N+2},\dots,b_{N+2^{2010+1}}.$ Thus, by Pigeonhole, at least one of $a_{N+1},a_{N+2},\dots,a_{N+2^{2010}+1}$ is divisible by $2^{2010}.$ Since there are infinitely many possible values of $N$ by the Chinese Remainder Theorem, we are done.

USA TST 2010/5 wrote: Define the sequence $a_1, a_2, a_3, \ldots$ by $a_1 = 1$ and, for $n > 1$, \[a_n = a_{\lfloor n/2 \rfloor} + a_{\lfloor n/3 \rfloor} + \ldots + a_{\lfloor n/n \rfloor} + 1.\]Prove that there are infinitely many $n$ such that $a_n \equiv n \pmod{2^{2010}}$. Let us define $a_0 = 0$ for convenience. Therefore, \begin{align*} a_{n} - a_{n - 1} &= \left( 1 + \sum_{i \ge 2} a_{\lfloor \frac{n}{i} \rfloor} \right) - \left( 1 + \sum_{i \ge 2} a_{\lfloor \frac{n - 1}{i} \rfloor} \right) \\ &= \sum_{i \ge 2} a_{\lfloor \frac{n}{i} \rfloor} - a_{\lfloor \frac{n - 1}{i} \rfloor} \\ &= \sum_{d \mid n, d < n} a_{d} - a_{d - 1} \end{align*}For convenience, define $a_k - a_{k - 1} = b_k$. Then, we have $b_{n} = \sum_{d \mid n, d< n} b_d$ for all $n > 1$. Before using the Mobius Inversion Formula, we will define a similar formula, which holds for all $n \in \mathbb{N}$, i.e. we define the function $e(n) = \begin{cases} 1 \ \text{if } n = 1 \\ 0 \ \text{otherwise} \end{cases}$. Therefore, it's easy to verify that for all $n \in \mathbb{N}$, we have \[ b_n - e(n) = \sum_{d \mid n, d < n} b_d \]Now, we'll apply Mobius Inversion Formula, from which we get \[ b_n = \sum_{d \mid n} \mu \left( \frac{n}{d} \right) (2b_d - e(d)) = 2 \sum_{d \mid n} \mu \left( \frac{n}{d} \right) b_d - \mu(n) \]Claim 01. If there exists prime $p$ such that $\nu_p(n) \ge k + 1$, then $2^k \mid b_n$. Proof. We'll induct on $k$. For $k = 1$, notice that if $p^2 \mid n$, then $\mu(n) = 0$, forces $b_n \equiv 0 \pmod{2}$. Now, suppose that the statement this is true for $k = \ell - 1$. We'll prove this for $k = \ell$. Indeed, for such $n$, we must have $\mu(n) = 0$. So, \[ b_n = 2 \sum_{d \mid n} \mu \left( \frac{n}{d} \right) b_d = 2 \sum_{d \mid n, \nu_p(d) \ge \ell} \mu \left( \frac{n}{d} \right) b_d \]By induction, all such $b_{d}$ is divisible by $2^{\ell - 1}$, and therefore $b_n$ is divisible by $2^{\ell}$. Now, we will finish the problem. By the Chinese Remainder Theorem, we can find infinitely many $2^{2010}$ consecutive integers that are divisible by $P^{2011}$ for some primes. Therefore, their corresponding $b_i$s must be divisible by $2^{2010}$ as well. This finishes the problem.

Denote $x_n$ by $a_{n+1}-a_n$ Observe that $x_n=\sum_{k=2}^n a_{\lfloor \frac{n}{k} \rfloor}-\sum_{k=2}^{n-1} a_{\lfloor \frac{n-1}{k} \rfloor}=\sum_{\stackrel{d|n}{d<n}} x_d$ Claim: $2^{\max_{p|n} v_p(n)-1}|x_n$ Proof: Let $k=v_p(n)$ then $x_n=\sum_{d|\frac{n}{p}}x_d+\sum_{\stackrel{p^k|d}{d<n}} x_d=2x_{\frac{n}{p}}+\sum_{\stackrel{p^k|d}{d<n}}x_d$ is divisible by $2^{k-1}$ by the inductive hypothesis so we are done. By the Chinese Remainder Theorem, we can find infinitely many $2^{2010}$ consecutive integers that are divisible by $P^{2011}$ for some primes. Therefore, their corresponding $b_i$'s must be divisible by $2^{2010}$

Let $a_0=0$ and let $f(n)=a_n-a_{n-1}$ for $n \geq 1$. One can easily verify that $$f(n)=\sum_{d \mid n, d<n} f(d).$$Define $g$ such that $g(n)=2f(n)$ for $n>1$ and $g(1)=1$. Then $g = f * \mathbf{1}$ (where $*$ denotes Dirichlet convolution), hence $f=g*\mu$ where $\mu$ is the Mobius function. We now prove the following claim by induction: Claim: If there exists some prime $p$ such that $p^k \mid f(n)$ for some $k\geq 1$, then $2^{k-1} \mid f(n)$. Proof: Induction on $k$, with $k=1$ trivial. For the inductive step, note that in general we have $$f(n)=\sum_{d \mid n, d\text{ squarefree}} \mu(d)g(n/d).$$If $k>1$, then $n/d$ for any squarefree $d \mid n$ has some $p^{k-1}$ dividing it, so by hypothesis $2^{k-2} \mid f(n/d)$. Since $n/d \neq 1$ clearly, it follows that $2^{k-1} \mid g(n/d)$, so $2^{k-1} \mid f(n)$ as well. $\blacksquare$ Let $p_1,\ldots$ be the primes in increasing order. By CRT we can pick infinitely many positive integers $N$ such that \begin{align*} N &\equiv 0 \pmod{p_1^{9999}}\\ N &\equiv -1 \pmod{p_2^{9999}}\\ N &\equiv -2 \pmod{p_3^{9999}}\\ &\vdots\\ N &\equiv -2^{9999}+1 \pmod{p_{2^{9999}}^{9999}}, \end{align*}in which case there are $2^{9999}$ consecutive integers (starting with $N$) that satisfy the claim for $k=2011$, i.e. $2^{2010} \mid f(N),f(N+1),\ldots$. Then $$a_N \equiv a_{N+1} \equiv \cdots \pmod{2^{2010}},$$while $N,N+1,\ldots$ certainly cycles through every residue modulo $2^{2010}$, so at some point it must be congruent to $a_N$. Since $N$ can be unbounded, it follows that infinitely many $n$ satisfy $a_n \equiv n \pmod{2^{2010}}$ as desired. $\blacksquare$ Remarks: At least the way I did this problem, I think this is a very good lesson in the dangers of overforcing and "culling" possible paths early. There's no immediate use for both Mobius inversion nor the definition of $f$, since both seem somewhat tangential to what we're trying to prove (at least to my eyes, perhaps someone more experienced would feel otherwise), and only initially appear useful to the extent of which they feel like somewhat neat expressions. If one considers this and decides prematurely that the solution path lies elsewhere, then they are surely doomed—one has to be open to exploration. In general one should be very hesitant to discard neat "rephrasings" of the problem, even if they appear to have no relation with the actual statement we want to prove—I think they're rarely coincidences.

Let $f(n) = a_n - a_{n-1}$ (with $f(1)=1$) so that the recurrence gives $$f(n) = \sum_{d|n,d<n} f(d)$$ Claim: let $g(n)$ denote the largest power of a prime in the prime factorization of $n$. Then $2^{g(n)-1} | f(n)$. Proof: we double strong induct on $g(n)$ and $\Omega(n)$. The base case of $g(n) = 1$ is just true. Now assume the claim holds whenever $g(n) < k$ for some $k\ge 2$. The base case of our second induction is $n=p^k$, as this is when $\Omega(n)$ is minimal over $n$ such that $g(n)=k$, and it is not hard to check that $g(p^e) = 2^{e-1}$ for all $p,e$. For the inductive step, suppose we have some $n$ with $g(n) = k$ and we know that $2^{k-1} | f(n')$ for all $n'$ with $g(n')=k$ and $\Omega(n')<\Omega(n)$. Let $S$ be the set of $d|n$ with $g(d)=k$, and let $m|n$ be maximal such that $g(m)<k$ (obtained by replacing all exponents of $k$ in the prime factorization of $n$ with $k-1$). Note that $\{d|n\} = S\cup\{d|m\}$, so $$f(n) = \sum_{d\in S,d<n}f(d) + \sum_{d|m}f(d) = \sum_{d\in S,d<n}f(d) + 2f(m).$$ The former term is divisible by $2^{k-1}$ by the inner inductive hypothesis, and the latter is divisible by $2^{k-1}$ by the outer inductive hypothesis, so the claim is proved. To finish, let $p_1,\dots,p_{2^{2010}}$ be distinct primes and choose infinitely many $N$ by CRT for which $$p_i^{2^{2010}+1} | N+i$$ for each $i$. By the claim, this guarantees $$a_N \equiv a_{N+1}\equiv \dots \equiv a_{N+2^{2010}}\pmod{2^{2010}}$$ so at least one $n$ in this range satisfies $a_n\equiv n\pmod{2^{2010}}$, as desired.

Good problem！

Let $b_n = a_n - a_{n-1}$. Then note that for $n \ge 2$, we have $b_n = a_n - a_{n-1} = a_1 + \sum_{i=2}^{n-1} a_{\lfloor \frac{n}{i} \rfloor} - a_{\lfloor \frac{n-1}{i} \rfloor} = 1 + \sum_{d \mid n, 1 < d < n} a_{\frac{n}{d}} - a_{\frac{n}{d} - 1} = 1 + \sum_{d \mid n, 1 < d < n} b_{\frac{n}{d}}$. If we let $a_0 = 0$, then we get $b_n = \sum_{d \mid n, d < n} b_d$ for $n \ge 2$. Let $(c_n)_{n \ge 1}$ be a sequence such that $c_1 = 1$ and for $n \ge 2$, $c_n = 2b_n$. Then, we get $c_n = \sum_{d \mid n} b_n$ for all $n \ge 1$. Now consider the following claim: Claim: If $p^k \mid n$, then $2^{k-1} \mid b_n$ Proof. We'll prove it by proceeding induction. Base case $k = 1$ is clear. Assume it's true on $k-1$ and let's prove it on $k$. Firstly, observe that $b_{p^k} = 2^{k-1}$ for all prime $p$ and all positive integer $k$. Now let $n = p^kn_1$. We'll prove that $2^{k-1} \mid b_{p^kn_1}$ by inducting on $n_1$. Base case $n_1 = 1$ was mentioned. Now assume that for all $1 \le m \le n_1 - 1$, we have $p^k \mid b_{p^km}$. Mobius inversion formula gives $b_n = \sum_{d \mid n} \mu(\frac{n}{d}) c_d$ for all $n \ge 1$. Unless $p^{k-1} \mid d$, $\mu(\frac{n}{d}) = 0$, so if $\mu(\frac{n}{d}) \neq 0$, we get that $p^{k-1} \mid b_d$ and $c_d = 2b_d$ for all $d$ satisfying $p^{k-1} \mid d$. Thus $\nu_2(c_d) = 1 + \nu_2(b_d) \ge k -2 + 1 = k - 1$ by induction hypothesis, so $2^{k-1} \mid b_n$. Hence, induction is completed. $\blacksquare$ Now we can choose a positive integer $N$ such that \begin{align*} N &\equiv 0 (p_1^{2011})\\ N &\equiv 1 (p_2^{2011})\\ &\vdots\\ N &\equiv k (p_k^{2011})\\. \end{align*} From this, we see that $a_{N-k-1} = b_1 + b_2 + \dots + b_{N-k-1} \equiv b_1 + b_2 + \dots + b_i \equiv a_i(2^{2010})$ for all $N-k-1 \le i \le N$, so if we let $k$ larger that $2^{2010}$, then by pigeonhole principle, we see that there is a positive integer $n$ such that $a_n \equiv n (2^{2010})$ and since there are infinitely many such $N$, there exists infinitely many $n$, as required. $\blacksquare$