Интересная функция

[Ktina]

Для каждого натурального $n$ определим функцию $f:\mathbb N\to{\mathbb N}$ следующим образом:
$f(n)=m^2+m+1$, где $2^m$ - наибольшая степень двойки, на которую делится $n$.
Найти наименьшее $n$, для которого $f(1)+f(2)+\dots +f(n)\ge 123456$

[hippie]

$n = 2^{14}+2^{13}+2^{7}+2^{2}+2^{1} = 24710$

При таком $n$ указанная сумма в точности равна 123456.

[Руст]

Если $S(n)=f(1)+...+f(n)$, то $S(2^k)=2S(2^{k-1})+2k\to S(2^k)=5*2^k-2k-4$.
Взяв двоичное представление $n=\sum_ia_i*2^i$ получаем $S(n)=S(\sum_i a^i*2^i)=\sum_i a_i(5*2^i-2i-4)=5n-2\sum_Ia_i(i+2)=5n-2a-4b$, где $a-$ сумма номеров позиций двоичных цифр, $b-$ количество ненулевых разрядов или (эквивалентно) сумма цифр в двоичном исчислении $n$. Отсюда уже вычисляется любое соотношение.