6.- Determine the function $f: N \rightarrow N$ (where $N=\{1,2,3, \ldots\}$ is the set of natural numbers) that satisfies, for any $s, n \in N$, the following two conditions:

a) $f(1)=1, f\left(2^{s}\right)=1$.

b) If $n<2^{\text {s }}$, then $f\left(2^{\mathrm{s}}+n\right)=f(n)+1$.

Calculate the maximum value of $f(n)$ when $n \leq 2001$.

Find the smallest natural number $n$ such that $f(n)=2001$.
Solution

For each natural number $n$, we define $f(n)$ as the sum of the digits of the expression of $n$ written in base 2. It is clear that this function $f$ satisfies conditions a) and b). Moreover, it is the only function that satisfies them, because the value of $f(n)$ is determined by conditions a) and b). We prove this claim by induction on $n$. If $n=1$ or $n=2^{s}, f(n)=1$. Suppose $n>1, n \neq 2^{s}$ and that $f(m)$ is known for all $m<n$; we can write $n=2^{s}+m$ with $m<2^{s}$ by taking $2^{s}$ as the largest power of 2 that is less than $n$; then $f(n)=f(m)+1$.

Now, it is easy to solve the two questions we are asked:

In the first case, it is a matter of seeing how many ones a number less than or equal to 2001 can have at most when written in base 2. This number, written in base 2, is obviously 1111111111, which corresponds to $n=1023=2^{10}-1$. It is $f(n)=10$.

In the second case, reasoning similarly, we observe that the answer is $n=2^{2001}-1$.