　$a_{2n-1}=a_{n}+2$ および $a_{2n}=a_n+1$ に注意すれば，$S_n=a_{2^{n-1}+1}+\cdots+a_{2^n}$ について

$$ S_{n+1}=2S_{n}+3\cdot 2^{n-1}$$

が成立する．$S_{1}=1$ を踏まえれば，一般項は $S_{n}=(3n-1)2^{n-2}=2^{n-1} + 3(n-1)2^{n-2}$ となる．よって，

$$ \sum_{n=1}^{M} S_n = (2^M-1)+3\bigl(2^{M-1}M-2^{M}+1\bigr)=( 3M-4 )2^{M-1}+2$$

が成立するから，$S_1+S_2+\cdots+S_{1024}$ を $1021$ で割った余りはフェルマーの小定理より $\mathbf{42}$ である ． ただし，以下の等式を用いた：
$$\sum_{k=1}^{M} k2^{k-1} = 2^MM-2^M+1.$$
公式解説
https://onlinemathcontest.com/contests/omc145/editorial/5260
公式解説における $S_n$ を求める過程です. 

---

$n-1$ を $2$ 進法表示すると，操作は以下のように表せる. 
- $1$ の位が $1$ のとき，その $1$ を取り除く. 
- $1$ の位が $0$ のとき，これを $1$ に変える. 

$a_n$ は操作で値が $0$ になるまでの回数であり，これは $n-1$ を $2$ 進法表示したときの $$(各位に現れる0の個数)×2+(各位に現れる1の個数)$$ に等しい (ただし，最高位は $0$ ではないものとする. ). したがって，$2^{k-1}+1\leq n\leq 2^{k}$ における $a_n$ の期待値は，$1+\dfrac{3}{2}(k-1)=\dfrac{3}{2}k-\dfrac{1}{2}$ であるから，$S_n=2^{n-2}(3n-1)$ がわかる.
ユーザー解説
https://onlinemathcontest.com/contests/omc145/editorial/5260/199
　$2$ 以上の整数 $n$ に対し，以下の操作を $n$ が $1$ になるまで繰り返します：
- $n$ が奇数ならば，$n$ に $1$ を足す．
- $n$ が偶数ならば，$n$ を $2$ で割る．

このとき，$a_n$ を $n$ が $1$ になるまでに必要な操作の回数で定めます．\
　例えば $5$ は以下のように操作されるので，$a_5=5$ です：
$$5\rightarrow6\rightarrow3\rightarrow4\rightarrow2\rightarrow1.$$
　このとき，以下の総和を素数 $1021$ で割った余りを求めてください：
$$a_2+a_3+a_4+\cdots+a_{2^{1024}-1}+a_{2^{1024}}$$