約数がちょうど15個ある最小の整数

方針

解答

⓪ 発想 — どう考え始めるか。 約数の個数は、素因数分解 $p^a{q}^b\cdots$ に対して $(a+1)(b+1)\cdots$。これが $15$ になる指数の組を探すのが出発点。

$15=15,5\times 3,3\times 5$ と分解できる。指数の組は $(a+1)=15$ すなわち $a=14$($p^{14}$)、または $(a+1,b+1)=(5,3)$ すなわち $p^4{q}^2$。

最小にするには「小さい素数に大きい指数」を割り当てる。$p^4{q}^2$ で $p=2,q=3$ なら $2^4\cdot 3^2=144$。$p^{14}=2^{14}$ は巨大。だから最小は $144$。

① 個数 $15$ を分解する。 $(a+1)(b+1)\cdots =15$。$15=15$ または $15=3\times 5$。

• $15=15$:指数 $(a)=(14)$ → $N=2^{14}=16384$。
• $15=3\times 5$:指数 $(a,b)=(2,4)$ または $(4,2)$。

② 最小化する。 $2$ 素数のときは、小さい素数 $2$ に大きい指数を与えると小さくなる。

• $2^4\cdot 3^2=16\cdot 9=144$
• $2^2\cdot 3^4=4\cdot 81=324$

$144<324<16384$。よって最小は $144$。

③ 確認。 $144=2^4\cdot 3^2$ の約数の個数は $(4+1)(2+1)=15$。

まとめ:約数の個数の逆問題は「$15$ を積に分解 → 指数の組 → 小さい素数に大きい指数」。指数の割り当てで数の大きさが大きく変わるので、$2^4\cdot 3^2$ のように小さい素数を厚く使うのが最小化のコツ。

発展 — 一歩先へ。 「約数の個数を保って数を最小化」は、小さい素数に大きい指数を割り当てるのが原則。逆に「$n$ 以下で約数が最も多い数」(高度合成数 $12,24,36,48,60,\dots$)も同じ発想で見つかる。約数の個数 $\tau (n)=\prod (a_i+1)$ は、素因数分解の指数だけで決まる乗法的な関数だ。

別解

別解 — 約数 $15$ 個の“形”を全部書き出して比べる(苦手な人向け)。 $15$ の約数分解 $15=15,15=3\times 5$ から、素因数分解の“形”は $2$ 通りしかない。それぞれで最小の数を作って比べる。

【形 A: $p^{14}$】約数 $(14+1)=15$ 個。最小は $2^{14}=16384$。

【形 B: $p^4{q}^2$】約数 $(4+1)(2+1)=15$ 個。最小にするには、大きい指数 $4$ を小さい素数 $2$ に、小さい指数 $2$ を次の素数 $3$ に。$2^4\cdot 3^2=16\cdot 9=144$。

(もし逆に $2^2\cdot 3^4=4\cdot 81=324$ とすると大きくなる。指数の割り当てが効く。)

$2$ つの形の最小 $16384$ と $144$ を比べて、$144$ が全体の最小。

「小さい素数に大きい指数」の理由も見える。$2^4\cdot 3^2$ と $2^2\cdot 3^4$ は指数の合計が同じでも、$2$ を多く使う方が小さい。約数の個数を保ったまま数を最小化する原則だ。