　$f(n)$ は「$n$ を二進数で表記したときの各桁の総和」であることが容易にわかる. ここで $f(n)=k$ かつ二進数で表記して $i$ 桁目が $1$ であるような $n$ は, $i$ によらず
$$\binom{N-1}{k-1}= \frac{k}{N}\binom{N}{k}$$
個存在するから,
$$\sum_{f(n)=k,n\lt 2^N}nf(n)=\sum_{i=1}^{N}k2^{i-1}\binom{N}{k}\frac{k}{N}=\frac{k^2}{N}\binom{N}{k}(2^N-1)$$
----
**補題.**　$\displaystyle\sum_{k=0}^{N}k^2\binom{N}{k}=2^{N-2}N(N+1)$

**証明.**　様々な方法が考えられるが, ここでは以下の式を出発点とする.
$$(1+x)^N=\sum_{k=0}^{N} \binom{N}{k}x^k$$
両辺を $x$ で微分し, $x$ を乗じることで
$$Nx(1+x)^{N-1}=\sum_{k=0}^{N} k\binom{N}{k}x^k$$
これをさらに $x$ で微分し,  $x=1$ を代入することで結論を得る,
$$N(1+x)^{N-1}+N(N-1)x(1+x)^{N-2}=\sum_{k=0}^{N} k^2\binom{N}{k}x^{k-1}$$
----
したがって, 補題より求める総和は
$$\sum_{n=0}^{2^N-1}nf(n)=\frac{2^N-1}{N}\sum_{k=0}^{N}k^2\binom{N}{k}=2^{N-2}(N+1)(2^N-1)$$
特にこれが $2$ で割り切れる最大の回数は, $(N-2)+20=\textbf{1048593}$ である.
公式解説
https://onlinemathcontest.com/contests/omc057/editorial/1314
https:\/\/youtu.be\/ZmKUA71W4Pc
ユーザー解説
https://onlinemathcontest.com/contests/omc057/editorial/1314/97
　非負整数に対して定義される関数 $f$ は, $f(0)=0$ および正整数 $n$ に対して
$$f(n)=\begin{cases}  f(n\/2) & (n\ \text{が偶数のとき}) \\\\ f((n-1)\/2)+1 & (n\ \text{が奇数のとき}) \end{cases}$$
をみたします. このとき, $N=2^{20}-1(=1048575)$ に対し以下の総和
 $$M=\sum_{n=0}^{2^N-1}nf(n)$$
が $2$ で割り切れる最大の回数を求めてください.