<s>[INST] Function with many values in a sequence Cool problem I was reading but couldn't solve!
Problem:
Let $f(n)$ be a function satisfying the following conditions:
a) $f(1) = 1$.
b) $f(a) \leq f(b)$ where $a$ and $b$ are positive integers with $a \leq b$.
c) $f(2a) = f(a) + 1$ for all positive integers a.
Let $M$ denote the number of possible values of the $2020$-tuple $(f(1), f(2), f(3), ..., f(2020))$ can take. Find $M ($mod $1000)$.
$\\$
My solution (incomplete):
I started listing a few values of $f(n)$, such as $f(1) = 1, f(2) = 2, f(3) = 2, 3, f(4) = 3, $etc. When $n$ is not a power of $2$, $f(n)$ has many values. For example, $f(3) = 2, 3$ and $f(5), f(6), f(7) = 3, 4.$ Using condition b, there are $2$ ways to select a value for $f(3); 2, 3$. $f(5), f(6), f(7)$ has $4$ ways to select values for those $3$; $(3, 3, 3), (3, 3, 4), (3, 4, 4), (4, 4, 4)$ respectively for $f(5), f(6), f(7).$ For the next "group"; $f(9), f(10), ..., f(15)$, there are $8$ ways. This process keeps happening for when a group starts with $f(n)$ such that $n = 2^x + 1$ for some positive integer $x$ and the group ends with $f(n) = 2^{x+1} - 1$, there are $2^x$ ways to assign values to that group. However, from here, I don't know how to calculate how many total possible values the $2020$-tuple can take. Do I add or multiply the values in these groups because they are independent events? Please help. Thanks in advance to those who help.
By the way, the correct answer is $\boxed{502}$ but I don't know how to get this.
 [/INST] (My final answer differs from yours. I believe Ross and I are right.)
Define $ k_n$ to be the maximal $k$ such that $ f(k) = n$.
Show that

*

*$f (k_n  ) = f(k_n - 1 ) = \ldots = f(k_{n-1} + 1) = n$

*$k_1 = 1$

*$k_{n+1} = 2k_n $ or $ 2k_{n}+1$.

*$k_n = \lfloor \frac{k_{n+1} }{2} \rfloor $

*A sequence $f(1), f(2), \ldots $ is uniquely defined by $k_1, k_2, k_3, \ldots  $

*For this problem, we only care about $k_n  \leq 2020$.

*A sequence is uniquely defined by the largest $k_n$, as all previous values are uniquely determined. Let's denote this $K$.

*We have $1011 \leq K \leq 2020$, so there are $2020-1011 + 1 = 1010$ such sequences.


As an example, if we care about the first 10 numbers, then we have  $ 6 \leq K \leq 10$ giving the corresponding sequences:
$\begin{array} {l l l}
K  = 6 \rightarrow  & 1, 3, 6 \rightarrow &  1, 2, 2, 3, 3, 3, 4, 4, 4, 4 \\
 K = 7 \rightarrow  & 1, 3, 7 \rightarrow  & 1, 2, 2, 3, 3, 3, 3, 4, 4, 4 \\
 K = 8 \rightarrow  & 1, 2, 4, 8 \rightarrow &  1, 2, 3, 3,  4, 4, 4, 4, 5, 5 \\
 K = 9 \rightarrow  & 1, 2, 4, 9 \rightarrow &  1, 2, 3, 3, 4, 4, 4, 4, 4, 5 \\
K = 10 \rightarrow  & 1, 2, 5, 10 \rightarrow  & 1, 2, 3, 3, 3, 4, 4, 4, 4, 4\\
\end{array}$
</s>