　手順の定め方より, $i$ 番目に書かれる数 $a_i$ は $i$ の二進数表示での各桁の和に等しい. 

**証明.** 正整数 $n$ を二進数表記した時の $1$ の個数を $\mathrm{popcount}(n)$ とすると, $\mathrm{popcount}(n)$ は

- $\mathrm{popcount}(1)=1$
- $\mathrm{popcount}(2n)=\mathrm{popcount}(n)$
- $\mathrm{popcount}(2n+1)=\mathrm{popcount}(2n)+1$

を満たし, これはそれぞれの操作に対応する. 

　$M=9$ が容易に従うから, 求める $i$ は $1023_{(10)}=1111111111_{(2)}$ の $10$ 桁からちょうど一桁を $0$ とすることで得られ, これらのうち $1000$ 以下のものの総和は
$$(1023-2^9)+(1023-2^8)+(1023-2^7)+(1023-2^6)+(1023-2^5)=\textbf{4123}$$
公式解説
https://onlinemathcontest.com/contests/omc068/editorial/1676
　OMC君は以下の手順によって黒板に $1000$ 個の数を書くことにしました：

- $1$ 番目には $1$ を書く.
- 正整数 $n$ に対し, $2n$ 番目には $n$ 番目に書いた数と同じ数を書く.
- 正整数 $n$ に対し, $2n+1$ 番目には $2n$ 番目に書いた数よりちょうど $1$ 大きい数を書く.

　一連の操作で黒板に書かれた数のうち最大のものを $M$ としたとき, $i$ 番目に $M$ を書いたような $1000$ 以下の正整数 $i$ の総和を求めてください.