Function with many values in a sequence

Question

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.

Answer 1

(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}$

Answer 2

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$.

Answer 3

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.$$