整数の性質の問題

Step 1: $e(n)$ を $3$ 進法の各位の数字で表す

$1$ から $n$ までのうち、$3$ の倍数は $\lfloor \frac{n}{3}\rfloor$ 個、$9$ の倍数は $\lfloor \frac{n}{9}\rfloor$ 個、$\dots$ ある。各数が持つ素因数 $3$ の個数を数えると
$$e(n)=\sum _{j\geqq 1}\lfloor \frac{n}{3^j}\rfloor$$
となる。

$n$ を $3$ 進法で $n={\sum }_{i\geqq 0}{d}_i{3}^i$（$d_i\in \{0,1,2\}$）と表すと、
$$\lfloor \frac{n}{3^j}\rfloor =\sum _{i\geqq j}{d}_i{3}^{i-j}$$
である。これを $j\geqq 1$ について足し、$d_i$ ごとにまとめると
$$e(n)=\sum _i{d}_i(3^{i-1}+3^{i-2}+\cdots +1)=\sum _i{d}_i\cdot \frac{3^i-1}{2}.$$
各位の数字の和を $s(n)={\sum }_i{d}_i$ とおくと
$$e(n)=\frac{n-s(n)}{2},n-2e(n)=s(n)$$
が成り立つ。

したがって条件は「$n$ を $3$ 進法で表したときの各位の数字の和が $4$」と同値である。

Step 2: $500$ を $3$ 進法で表す

$3^5=243$, $3^6=729$ である。
$$500=2\cdot 243+14,14=1\cdot 9+1\cdot 3+2$$
より $500=200112_{(3)}$ となる。

Step 3: 数え上げ

$n$ を $6$ 桁 $d_5{d}_4{d}_3{d}_2{d}_1{d}_0$（先頭の $0$ を許す）で表し、数字の和が $4$ で $n\leqq 200112_{(3)}$ となるものを数える。

(i) $d_5=0$ のとき：残り $5$ 桁の和が $4$ である。$2$ の個数で分けると
- $2$ が $0$ 個（$1$ が $4$ 個）：${}_5{\mathrm{C}}_4=5$
- $2$ が $1$ 個（$1$ が $2$ 個）：$5\times {}_4{\mathrm{C}}_2=30$
- $2$ が $2$ 個：${}_5{\mathrm{C}}_2=10$

合計 $45$ 個。これらはすべて $243$ 未満なので条件を満たす。

(ii) $d_5=1$ のとき：残り $5$ 桁の和が $3$ である。
- $1$ が $3$ 個：${}_5{\mathrm{C}}_3=10$
- $2$ と $1$ が $1$ 個ずつ：$5\times 4=20$

合計 $30$ 個。これらはすべて $486$ 未満なので条件を満たす。

(iii) $d_5=2$ のとき：残り $5$ 桁の和は $2$ で、残りの部分の値が $14=00112_{(3)}$ 以下でなければならない。$d_4$ または $d_3$ が $0$ でないと値は $27$ 以上になるので、$d_4=d_3=0$ である。$d_2{d}_1{d}_0$ の和が $2$ となるのは $002,011,020,101,110,200$ である。それぞれの値は $2,4,6,10,12,18$ なので、$14$ 以下のものは $5$ 個。

以上より、求める個数は
$$45+30+5=80$$
である。

（確認：$n=8=22_{(3)}$ のとき $e(8)=2$ で、$8-4=4$ となり成り立つ。）

ルジャンドルの公式より $e(n)={\sum }_{i\ge 1}\lfloor n/3^i\rfloor =\frac{n-s(n)}{2}$ である。ここで $s(n)$ は $n$ を 3 進法で表したときの各桁の和である。したがって $n-2e(n)=s(n)$ となり、条件は $s(n)=4$ と同値になる。

よって $1\le n\le 500$ で、3 進法の各桁の和が 4 になる $n$ の個数を数える。$500=2\cdot 243+14=200112_3$ である。$n=0$ は桁和が 0 なので数えなくてよい。0 以上 500 以下で数える。6 桁(上位の 0 も含む)で考える。

(i) 最上位の桁が 0 または 1 の場合は、残り 5 桁が自由である。$(1+x+x^2{)}^5$ の展開係数は $1,5,15,30,45,51,\dots$ である。
- 最上位が 0 のとき、残り 5 桁の和は 4 で、$x^4$ の係数より 45 通り。
- 最上位が 1 のとき、残り 5 桁の和は 3 で、$x^3$ の係数より 30 通り。

(ii) 最上位の桁が 2 の場合は、残り 5 桁が $00112_3$ 以下で、桁和が 2 であればよい。
- 上から 2 桁は 0 に決まる。
- 続く 3 桁 $d_2{d}_1{d}_0$ が $112_3$ 以下で、桁和が 2 であればよい。
- $d_2=0$ のとき、$(d_1,d_0)=(0,2),(1,1),(2,0)$ の 3 通り。
- $d_2=1$ のとき、$d_1{d}_0\le 12_3$ かつ桁和 1 なので $(0,1),(1,0)$ の 2 通り。
- 合計 5 通り。

以上より $45+30+5=80$ 個である。

検算として、$n=4=11_3$ は $e(4)=1$ なので $4-2=2$ となり、桁和 2 と一致する。$n=13=111_3$ は桁和 3 で、$e(13)=4+1=5$ なので $13-10=3$ となり、これも一致する。