約数がちょうど 15 個の自然数で最小のものは 144 になる

約数がちょうど 15 個ある自然数のうち、いちばん小さいのは $144$ です。 $144 = 2^{4} \times 3^{2}$ 。

$1$ から順に約数を数えていく必要はありません。 $15$ という個数を分解した時点で、 $n$ の形が数通りに決まります。

個数から形を決める

$n = p_{1}^{a_{1}} p_{2}^{a_{2}} \dots$ のとき、約数の個数は $(a_{1} + 1) (a_{2} + 1) \dots$ でした^[1]。

だから $d (n) = 15$ は、 $15$ を $2$ 以上の整数の積に分ける問題に変わります。分け方は $15$ そのものと $3 \times 5$ の 2 通り。

前者なら指数は $14$ の 1 つで $n = p^{14}$ 。後者なら指数が $2$ と $4$ で $n = p^{2} q^{4}$ の形です。

canvas: 式は呼び出しにそのまま書いてください。この引数は焼けません -> drawMath(… splForm …)

$p^{14}$ の最小は $2^{14} = 16384$ 。 $p^{2} q^{4}$ のほうがはるかに小さくなります。

小さい素数に大きい指数を当てる

$p^{2} q^{4}$ の形で最小を作るには、素数の選び方と指数の当て方の 2 つを決めます。

素数は小さいものから使うのが得。 $2$ と $3$ を選びます。 $5$ 以上を混ぜると必ず大きくなる^[2]。

指数は、大きいほうを小さい素数に当てます。 $2^{4} \times 3^{2} = 144$ に対し、 $2^{2} \times 3^{4} = 324$ 。

canvas: 式は呼び出しにそのまま書いてください。この引数は焼けません -> drawMath(… swpCase[swpIndex][0] …)

$2^{4} \times 5^{2} = 400$ 、 $3^{4} \times 5^{2} = 2025$ 。 $2$ と $3$ に大きい指数から順に当てた $144$ が最小です。

例：3 桁の範囲を全部挙げる

$d (n) = 15$ をみたす 3 桁の数を並べます。 $p^{14}$ は 3 桁に入らないので、 $p^{2} q^{4}$ だけ。

$2^{4} \times 3^{2} = 144$ 、 $3^{4} \times 2^{2} = 324$ 、 $2^{4} \times 5^{2} = 400$ 、 $2^{4} \times 7^{2} = 784$ 。

$2^{4} \times 1 1^{2} = 1936$ で 4 桁に届くため、ここで打ち切り。答えは 4 個です。

例：個数が 12 のとき

$12$ の分け方は $12$ 、 $2 \times 6$ 、 $3 \times 4$ 、 $2 \times 2 \times 3$ の 4 通り。指数はそれぞれ $11$ 、 $(1, 5)$ 、 $(2, 3)$ 、 $(1, 1, 2)$ 。

最小の候補を作ります。 $2^{11} = 2048$ 、 $2^{5} \times 3 = 96$ 、 $2^{3} \times 3^{2} = 72$ 、 $2^{2} \times 3 \times 5 = 60$ 。

いちばん小さいのは $60$ 。素因数を増やすほど小さくなる場合があるので、分け方をすべて試す必要があります。

$d (n)$	最小の $n$	素因数分解
$12$	$60$	$2^{2} \times 3 \times 5$
$15$	$144$	$2^{4} \times 3^{2}$
$18$	$180$	$2^{2} \times 3^{2} \times 5$
$20$	$240$	$2^{4} \times 3 \times 5$

例：個数が 16 のとき

$16$ の分け方は $16$ 、 $2 \times 8$ 、 $4 \times 4$ 、 $2 \times 2 \times 4$ 、 $2 \times 2 \times 2 \times 2$ の 5 通りあります。

順に最小の候補を作ると $2^{15}$ 、 $2^{7} \times 3 = 384$ 、 $2^{3} \times 3^{3} = 216$ 、 $2^{3} \times 3 \times 5 = 120$ 、 $2 \times 3 \times 5 \times 7 = 210$ 。

最小は $120$ でした。素因数をいちばん多くした $210$ より小さい。分け方を増やせば必ず小さくなる、というわけではありません。

最小を作るとき、指数の並びは大きい順に小さい素数へ当てます^[2]。

$2^{a} 3^{b}$ で $a < b$ なら、入れかえたほうが小さい。 $2$ と $3$ の比が効くため。

例：奇数に限ると

$d (n) = 15$ で $n$ が奇数のものを探します。 $2$ が使えないので、素数は $3$ から始まります。

$3^{4} \times 5^{2} = 2025$ 、 $3^{2} \times 5^{4} = 5625$ 、 $3^{14}$ は 7 桁。

最小は $2025$ 。 $144$ の 14 倍ほどになりました。使える素数を 1 つ削ると、こう跳ね上がります。

例：個数が奇数になる条件

$d (n)$ が奇数なのは、 $(a_{1} + 1) (a_{2} + 1) \dots$ が奇数のとき。すべての $a_{i}$ が偶数である必要があります。

指数が全部偶数の数は平方数です。逆に平方数なら指数は全部偶数なので、 $d (n)$ は奇数になる。

$d (n) = 15$ の解がすべて平方数なのは、このためです。 $144 = 1 2^{2}$ 、 $324 = 1 8^{2}$ 、 $400 = 2 0^{2}$ 、 $784 = 2 8^{2}$ 。

例：総和から素数を見分ける

約数の総和を $σ (n)$ と書きます。 $σ (n) = n + 1$ になるのは、 $n$ が素数のときだけです。

約数が $1$ と $n$ の 2 つしかない状態を、そのまま式にした形になります。

$σ (12) = 28$ 、 $σ (13) = 14$ 。 $13$ だけが $n + 1$ の形で、たしかに素数です。

約数がちょうど 8 個ある自然数のうち、最小のものはどれですか。

__RESULT__

$8$ の分け方は $8$ 、 $2 \times 4$ 、 $2 \times 2 \times 2$ 。それぞれ $2^{7} = 128$ 、 $2^{3} \times 3 = 24$ 、 $2 \times 3 \times 5 = 30$ で、最小は $24$ です。

個数を分解し、指数を大きい順に小さい素数へ当てる。手順が短いので、 $d (n)$ が変わっても同じ道でたどり着けます。

参考

Divisor function - Wikipedia

Highly composite number - Wikipedia

$1$ から順に数える必要はありません。$15$ を $2$ 以上の整数の積に分けると $15$ と $3 \times 5$ の 2 通りで、$n$ の形が $p^{14}$ か $p^2 q^4$ に決まります。あとは小さい素数へ大きい指数から当てるだけ。$2^4 \times 3^2 = 144$ が最小で、入れかえた $2^2 \times 3^4$ は $324$ に膨らみます。$d(n) = 12$ で $60$、$16$ で $120$ になる計算、3 桁に 4 個しかない理由、奇数に限ると $2025$ まで跳ね上がること、$d(n)$ が奇数なら必ず平方数になることまで並べました。