4. The function $f: \mathbb{N} \rightarrow \mathbb{N}$ is given such that $f(n)=1$ if $n$ is odd, and $f(n)=k$ for every even number $n=2^{k} l$, where $k$ is a natural number and $l$ is an odd number. Determine the largest natural number $n$ for which

$$
f(1)+f(2)+\ldots+f(n) \leqq 123456 .
$$
SOLUTION. Let

$$
S(n)=f(1)+f(2)+\ldots+f(n)
$$

From the problem statement, it follows that $S(1)=1$. Since $f(n) \geq 1$ for all natural numbers $n$, $S: \mathbb{N} \rightarrow \mathbb{N}$ is an increasing function. If $n$ is a natural number of the form $n=2^{k}$, where $k$ is a natural number, we determine the sum $S(n)$ as follows: The number of odd numbers not greater than $n$ is $2^{k-1}$. Each odd number contributes a value of 1 to the sum $S(n)$. The number of even numbers not greater than $n$ is also $2^{k-1}$, and each even number contributes a value of at least 1 to the sum. If the number is divisible by four, it contributes an additional 1. If the number is divisible by eight, it contributes another 1, and so on (the value of $S(n)$ is formed by adding values of 1 "layer by layer"). Therefore, we have

$$
\begin{aligned}
S\left(2^{k}\right) & =2^{k-1}+2^{k-1}+2^{k-2}+\ldots+2+1=2^{k-1}+\frac{2^{k}-1}{2-1}= \\
& =2^{k}+2^{k-1}-1=3 \cdot 2^{k-1}-1 .
\end{aligned}
$$

Let $p$ be a natural number that can be written in the form $p=2^{m} s$, where $m$ is a non-negative integer and $s$ is an odd natural number. Let $k$ be a natural number such that $pm$, and $l$ an odd number. According to the previous paragraph,

$$
\begin{aligned}
S\left(2^{k} l+2^{m}\right)= & f(1)+f(2)+\ldots+f\left(2^{k} l\right)+f\left(2^{k} l+1\right)+f\left(2^{k} l+2\right)+\ldots+ \\
& +f\left(2^{k} l+2^{m}\right)= \\
= & f(1)+f(2)+\ldots+f\left(2^{k} l\right)+f(1)+f(2)+\ldots+f\left(2^{m}\right)= \\
= & S\left(2^{k} l\right)+S\left(2^{m}\right) .
\end{aligned}
$$

From this, we can easily prove by mathematical induction that if $k_{1}>k_{2}>\ldots>k_{i}$ are non-negative integers, then

$$
S\left(2^{k_{1}}+2^{k_{2}}+\ldots+2^{k_{i}}\right)=S\left(2^{k_{1}}\right)+S\left(2^{k_{2}}\right)+\ldots+S\left(2^{k_{i}}\right)
$$

The largest non-negative integer $k_{1}$ such that $3 \cdot 2^{k_{1}-1}-1=S\left(2^{k_{1}}\right) \leq 123456$ is $k_{1}=16$. In this case, $S\left(2^{16}\right)=98303$.

The largest non-negative integer $k_{2}$ such that $3 \cdot 2^{k_{2}-1}-1=S\left(2^{k_{2}}\right) \leq 123456-$ $-98303=25153$ is $k_{2}=14$. In this case, $S\left(2^{14}\right)=24575$.

The largest non-negative integer $k_{3}$ such that $3 \cdot 2^{k_{3}-1}-1=S\left(2^{k_{3}}\right) \leq 25153-$ $-24575=578$ is $k_{3}=8$. In this case, $S\left(2^{8}\right)=383$.

The largest non-negative integer $k_{4}$ such that $3 \cdot 2^{k_{4}-1}-1=S\left(2^{k_{4}}\right) \leq 578-$ $-383=195$ is $k_{4}=7$. In this case, $S\left(2^{7}\right)=191$.

The largest non-negative integer $k_{5}$ such that $3 \cdot 2^{k_{5}-1}-1=S\left(2^{k_{5}}\right) \leq 195-$ $-191=4$ is $k_{5}=1$. In this case, $S\left(2^{1}\right)=2$.

The largest non-negative integer $k_{6}$ such that $S\left(2^{k_{6}}\right) \leq 4-2=2$ is $k_{6}=0$. In this case, $S\left(2^{0}\right)=1$.

Thus,

$$
\begin{aligned}
S(82307) & =S\left(2^{16}+2^{14}+2^{8}+2^{7}+2+1\right)= \\
& =S\left(2^{16}\right)+S\left(2^{14}\right)+S\left(2^{8}\right)+S\left(2^{7}\right)+S(2)+S(1)= \\
& =123455 \leq 123456 .
\end{aligned}
$$

Moreover, $S(82308)=S(82307)+f(82308)=123455+2=123457>123456$.

The largest natural number $n$ for which $S(n) \leq 123456$ is $n=82307$.