The sequence $a_i$ is defined as $a_1 = 1$ and \[a_n = a_{\left\lfloor \dfrac{n}{2} \right\rfloor} + a_{\left\lfloor \dfrac{n}{3} \right\rfloor} + a_{\left\lfloor \dfrac{n}{4} \right\rfloor} + \cdots + a_{\left\lfloor \dfrac{n}{n} \right\rfloor} + 1\] for every positive integer $n > 1$. Prove that there are infinitely many values of $n$ such that $a_n \equiv n \mod 2012$.
Problem
Source: 2012 Indonesia Round 2.5 TST 2 Problem 4
Tags: floor function, number theory unsolved, number theory
Saikrishnadeep
21.05.2012 18:29
Is $a_0$ defined in this sequence ?
chaotic_iak
21.05.2012 18:55
No.
Saikrishnadeep
21.05.2012 19:16
chaotic_iak wrote: No. Is it $0$ ?? I mean to ask, what happens to the other terms when $a_2$ is calculated ?
mavropnevma
21.05.2012 19:33
The "other terms" don't exist; the numerator is at least as large as the denominator for all floor expressions, so their value is at least $1$. Thus $a_2 = a_{\lfloor \frac {2} {2} \rfloor } + 1 = a_1 + 1 = 2$, $a_3 = a_{\lfloor \frac {3} {2} \rfloor } + a_{\lfloor \frac {3} {3} \rfloor } +1 = 2a_1 + 1 = 3$, etc.
Saikrishnadeep
21.05.2012 20:02
mavropnevma wrote: The "other terms" don't exist; the numerator is at least as large as the denominator for all floor expressions, so their value is at least $1$. Thus $a_2 = a_{\lfloor \frac {2} {2} \rfloor } + 1 = a_1 + 1 = 2$, $a_3 = a_{\lfloor \frac {3} {2} \rfloor } + a_{\lfloor \frac {3} {3} \rfloor } +1 = 2a_1 + 1 = 3$, etc. Oh k..Thanks..I'll try now..
dinoboy
28.05.2012 00:44
http://www.artofproblemsolving.com/Forum/viewtopic.php?p=1960093&sid=96caf9bba84c3446e1264ecef9ff5268#p1960093 (Same techniques are used to solve the problems)