素因数の数の評価～京大特色2023

$f(n) = k$ とおく。$k \geqq 4$ のとき，条件を満たす $n$ が存在しないことを示す。

$k \geqq 4$ のとき $k = f(n) < \dfrac{\sqrt{n}}{2}$，変形して $n > 4k^2$ であることを示せばよい。

$k$ 番目の素数を $p_k$ とおくと， $n \geqq 2 \times 3 \times \cdots \times p_k$ となる。

$$\begin{aligned} n &\geqq 2 \times 3 \times 5 \times \cdots \times p_k \\ & > 2 \times 2 \times 4 \times \cdots \times 4\\ &= 4^{k-1} \end{aligned}$$ となる。よって $n > 4k^2$ という不等式を示すには $$4^{k-1} > 4k^2$$ すなわち $$2^{k-1} > k$$ が成立することを示せばよい。

これを数学的帰納法で証明する。

• $k = 4$ のとき $2^{4-1} = 8 > 4 = k$ である。

• $k = m$ で不等式が成立すると仮定する。
  $k = m+1$ のとき $$\begin{aligned} 2^{k-1} &= 2^m\\ &= 2 \cdot 2^{m-1}\\ &> 2m\\ &> m+1 \end{aligned}$$ こうして $k=m$ で不等式が成立すると仮定した場合，$k = m+1$ で不等式が成立することが従う。

よって，数学的帰納法から $k \geqq 4$ の自然数に対して不等式 $2^{k-1}>k$ が成立することが分かる。

以上より $k \geqq 4$ のとき，条件を満たす $n$ は存在しない。

$p_k$ は $k$ 番目の奇数以上になるため，$p_k \geqq 2k+1$，$p_{k-1} \geqq 2k-1$ となる。

よって $$\begin{aligned} n & \geqq 2 \times 3 \times \cdots \times p_k\\ & \geqq 2 \times 3 \times (2k-1) \times (2k+1)\\ & = 6 (4k^2 - 1)\\ & > 4 k^2 \end{aligned}$$ である。

よって $k \geqq 4$ のとき $f(n) < \dfrac{\sqrt{n}}{2}$ となる。

1. $f(n) =0$ のとき
   $n=1$ のみだが，このとき条件は満たされない。

2. $f(n)=1$ のとき
   $f(n) \geqq \dfrac{\sqrt{n}}{2}$ に $f(n) = 1$ を代入すると，$1 \geqq \dfrac{\sqrt{n}}{2}$，つまり $n \leqq 4$ を得る。
   このうち素因数が1つであるものは $n = 2,3,4$ である。

3. $f(n) = 2$ のとき
   $f(n) \geqq \dfrac{\sqrt{n}}{2}$ に $f(n) = 2$ を代入して変形すると，$n \leqq 16$ を得る。
   このうち素因数が2つであるものは $n = 6,10,12,14,15$ である。

4. $f(n) = 3$ のとき
   $f(n) \geqq \dfrac{\sqrt{n}}{2}$ に $f(n) = 3$ を代入して変形すると，$n \leqq 36$ を得る。
   このうち素因数が3つであるものは $n = 30$ だけである。

以上をまとめると，求める $n$ は $$n = 2,3,4,6,10,12,14,15,30$$ である。