NF杯2024(C)

　十進法で $2,3,7,8$ のみを桁に持つ自然数の集合を $S_0$ とおく． $S_0$ の要素で桁数が $k$ 以下であるものは $4^k+4^{k-1}+\dots+4^1=\frac{4^{k+1}-4}{3}$ 個あることに注意する．

　条件を満たす $n$ は $N\in S_0$ と $M=0,1,2,\dots$ を用いて $n=N^{(2^M)}$ と表せる．そこで，不等式 $N^{(2^{M})} \lt 10000$ を各 $M$ について考える．

• $M=0,1,2$ のとき，それぞれ $N \lt 10^{4}, 10^2, 10^1$ なので $N$ はそれぞれ桁数$4,2,1$ 以下の $S_{0}$ の要素である．
• $M=3$ のとき，$N^8\lt 10000$ より $N\lt \sqrt{10}\lt 4$ なので $N=2, 3$ のみ．
• $M\geq 4$ のとき，$10000\lt 2^{16}\leq N^{2^{M}}$ なので不適．

　さらに，相異なる $x,y\in S_0$ と正の整数 $n \gt m$ が $x^{(2^n)}=y^{(2^m)}$ を満たしたとすると， $$x^{(2^{n-m})} = y$$ であるが，左辺は平方数なので下 $1$ 桁が $2,3,7,8$ ではなく矛盾する．したがって，$M$ で場合分けして得られたそれぞれの $N$ の個数を足しあげても重複は生じないから，求める個数は $$\frac{4^{5}-4}{3} + \frac{4^{3}-4}{3}+\frac{4^{2}-4}{3} + 2 = \mathbf{366}$$ である．