OMC076(E) - オモローの補題

　十進法表記で桁の数字に $3$ を持つ正整数を，昇順で並べた数列を $\left\{a_n\right\}_{n=0,1,...}$ とする．このとき以下の補題を示そう．

オモローの補題*．任意の $n$ に対して $a_n \equiv n \pmod3$ が成立する．

証明．$3$ を法とする．任意の $n$ に対して，$a_{n+1} - a_n$ は $1, 4, 7, 10$ のどれかであり，いずれの場合も $1$ と合同．また $a_0 = 3 \equiv 0$ であるから，帰納的に主張を得る．

　$\left\{a_n\right\}$ に現れない正整数を昇順で並べた数列 $\left\{b_n\right\}_{n=0,1,...}$ について，十進法表記での $b_n$ の各桁の数字を $$k \to \begin{cases} k & (k = 0, 1, 2) \\ k - 1 & (k = 4,\ldots, 9) \end{cases}$$ と置き換えて九進法で解釈したものは，番号 $n$ に一致．$2021$ は $\left\{a_n\right\}$ に現れず，また $2021_{(10)} - 2021_{(9)} = 544_{(10)}$ より，$1,\ldots,2021$ のうち $\left\{a_n\right\}$ に現れるものは $544$ 個．
　ここでオモローの補題より，$\left\{a_n\right\}$ に現れる $544$ 個のうち $3$ の倍数でないのは $362$ 個．$1,\ldots, 2021$ の中に $3$ の倍数は $673$ 個あるから，求める個数は $362 + 673 = \mathbf{1035}$．

　なお，$2021$ を一般に $N \ge 1$ とおくと， $\left\{b_n\right\}$ に現れる $N$ 以下の最大の整数を $b_m$（上と同様の議論で簡単に $m$ が求まる）としたとき，求める個数は $$\left\lfloor\frac{2 \left(N - m - 1\right)}3\right\rfloor + \left\lfloor\frac N3\right\rfloor\mathclose{}.$$

*　ここだけの呼称である．