整数の性質の問題

対応をつくる

$3$ 進法で各位の数字が $0$ か $1$ だけの数 ${\overline{d_k{d}_{k-1}\cdots d_0}}_{(3)}$ に、同じ数字の並びを $2$ 進法で読んだ数 ${\overline{d_k{d}_{k-1}\cdots d_0}}_{(2)}$ を対応させる。この対応で、正の整数全体と $a_1,a_2,\dots$ 全体が $1$ 対 $1$ に対応する。

さらに、この対応は大小関係を保つ。実際、数字が $0,1$ だけの $2$ つの数を比べるとき、桁数が多い方が大きく、桁数が同じなら上の位から見て初めて異なる位で $1$ の方が大きい。この判定は $3$ 進法でも $2$ 進法でも同じである（$3$ 進法の場合、上の位の $1$ は $3^j$、それより下の位の和は高々 $3^{j-1}+\cdots +1=\frac{3^j-1}{2}<3^j$ だから）。

よって、$a_m$ は「$m$ を $2$ 進法で表し、その数字の並びを $3$ 進法で読んだ数」である。たとえば $m=4=100_{(2)}$ なら $a_4=100_{(3)}=9$ で、問題文の例と一致する。

和を位ごとに数える

$m$ を $2$ 進法で表したとき、$2^j$ の位が $1$ なら、$a_m$ の $3^j$ の位が $1$ になる。したがって
$$a_1+\cdots +a_{100}=\sum _j{3}^j\times (1\leqq m\leqq 100\text{で}{2}^j\text{の位が}1\text{の}m\text{の個数})$$
である。$100=1100100_{(2)}$ なので $j=0,1,\dots ,6$ を考えればよい。

$2^j$ の位が $1$ である整数は、$2^{j+1}$ ごとに連続する $2^j$ 個ずつ現れる。$1\leqq m\leqq 100$ で数えると:
- $j=0$（奇数）: $50$ 個
- $j=1$: $2,3,6,7,\dots ,98,99$ の $25$ 組で $50$ 個
- $j=2$: $4\sim 7,12\sim 15,\dots ,92\sim 95$ の $12$ 組で $48$ 個と $100$ の $1$ 個、計 $49$ 個
- $j=3$: $8\sim 15,24\sim 31,40\sim 47,56\sim 63,72\sim 79,88\sim 95$ で $48$ 個
- $j=4$: $16\sim 31,48\sim 63,80\sim 95$ で $48$ 個
- $j=5$: $32\sim 63,96\sim 100$ で $32+5=37$ 個
- $j=6$: $64\sim 100$ で $37$ 個

よって
$$\begin{array}{rl}& 50\cdot 1+50\cdot 3+49\cdot 9+48\cdot 27+48\cdot 81+37\cdot 243+37\cdot 729\\ & =50+150+441+1296+3888+8991+26973\\ & =41789\end{array}$$

答えは $41789$ である。

$a_n$ は「$n$ を 2 進法で書き、その数字の並びを 3 進法として読んだ数」である（$0$ と $1$ だけの 3 進数は小さい順に 2 進数 $1,10,11,100,\dots$ と対応する）。実際 $a_1=1,a_2=3,a_3=4,a_4=9$ と合う。

$100=64+32+4=1100100_{(2)}$ より $a_{100}=3^6+3^5+3^2=729+243+9=981$。

和を $n=0$ からの区間に分けて求める（$a_0=0$ とみなしてよい）。

(1) $n=0,1,\dots ,63$（2 進 6 桁以下）: 各位（$3^0,\dots ,3^5$）が $1$ になる $n$ はそれぞれ $32$ 個。和は $32(1+3+9+27+81+243)=32\times 364=11648$。

(2) $n=64,\dots ,95$（2 進で上 2 桁が $10$、下 5 桁が $0\sim 31$）: 32 個すべてが $3^6=729$ を含むので $32\times 729=23328$。下 5 桁は各位が 16 個ずつ $1$ になるので $16(1+3+9+27+81)=16\times 121=1936$。計 $25264$。

(3) $n=96,\dots ,99$（上 5 桁が $11000$、下 2 桁が $0\sim 3$）: $4\times (729+243)=3888$、下 2 桁の部分は $0,1,3,4$ で和 $8$。計 $3896$。

(4) $n=100$: $981$。

合計 $11648+25264+3896+981=41789$。

検算: $n=1,\dots ,7$ で同様の公式を使うと和は $1+3+4+9+10+12+13=52$。公式 $4(1+3+9)=52$ と一致し、方法は正しい。また別の分け方として、$n=0\sim 127$ の総和は $64\times 1093=69952$ で、$101\sim 127$ の和を引くと $41789$ となることでも確かめられる（$101\sim 127$ の和 $=69952-41789=28163$、これは 27 個の項で平均約 $1043$ と妥当）。