XXII OBM

Let $S_k=f(1)+f(2)+f(3)+\cdots +f(2^k)$. Then $$S_k=f(1)+f(2)+\cdots +f(2^{k-1})+f(1)+f(2)+\cdots +f(2^{k-1}-1)+f(2^k)$$ $$\iff S_k=2S_{k-1}-f(2^{k-1})+f(2^k)$$ $$\iff S_k=2(S_{k-1}+k)$$ If $n=(a_t{a}_{t-1}\dots a_0{)}_2$ is the binary expansion of $n$, it is easy to see that $f(1)+\cdots +f(n)=\sum a_i\cdot S_i$. Also, by induction, $S_k>S_{k-1}+\cdots +S_0$, so that in order to obtain the least $n$ satisfying $f(1)+\cdots +f(n)\ge 123456$, we have to choose $$S_{14}+S_{13}+S_7+S_2+S_1=123456,$$ that is, $n=2^{14}+2^{13}+2^7+2^2+2^1=24710$.