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.
 A: (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}$
A: As you have seen, from a and c $f(2^n)=n+1$.  Then for each region $[2^n,2^{n+1})$ you have to choose exactly one place to increment the function value because of b.  If you incremented at $k$ in the previous region, you can increment at $2k$ or $2k+1$ in the current increment.  If you know where the increment happens in one region, the location of all the previous ones is determined.  You just divide by $2$ and round down.
There are $2020-1024=996$ places the increment can happen in the last region of interest.  Each of those leads to a unique list of function values.  If $f(2020)=11$ the increment happens higher.  We then have $f(1010)=10$ and the increment in that region can happen in $14$ places.  This gives that the number of lists of function values is $996+14=1010$ and taking $\bmod 1000$ gives $10$.
A: This is not a new answer, but an explanation of the answer by Ross
For any $a\in\mathbb{N}_+$, from (c), we have
$$f(a) = f(2a)-1 \text{ where } a\in (2^{k-1},2^{k}] \text{ and } 2a\in (2^{k},2^{k+1}] \text{ with } k\triangleq \lceil\log_2 a\rceil.$$
Therefore, for any $k\in\mathbb{N}_+$, the function values of the even numbers in the interval $(2^{k},2^{k+1}]$ uniquely define the function values in the interval $(2^{k-1},2^{k}]$.
Consequently, the tuple $(f(1),f(2),\ldots,f(1024))$ is uniquely defined by the tuple $(f(1026),f(1028),\ldots, f(2048))$. Thus, $M$ is the number of tuples $(f(1025),f(1026),\ldots, f(2020), f(2022), f(2024),\ldots,f(2048))$.
Further, from (c), we note that
$$f(1024)= f(2^9)+1=f(1)+10=11 \text{ and } f(2048)=f(1024)+1=12.$$
So from (b), when $a\in [1025,2048]$, we get that $f(a)$ can either be $11$ or $12$, and there exists $r\in [1025,2048]$ such that
$$f(a)=\begin{cases}
10, & \text{ if } 1025\leq a < r\\
11, & \text{ if } r\leq a \leq 2048.
\end{cases}$$
Thus, for each value of $r=1025,1026,\ldots,2020,2022, 2024,\ldots,2048$, we get a different tuple $(f(1025),f(1026),\ldots, f(2020), f(2022), f(2024),\ldots,f(2048)=12)$.
Hence, the number of tuples is $$M=(2020-1024)+(2048-2020)/2=1010\implies M\bmod 1000=10.$$
