【挑戦状】問28 想定解答. - ぷりんの雑記帳

今日はクリスマスに因んだ整数問題です。

【すむーずぷりんからの挑戦状】
問28. 約数の個数が 1225 個の自然数のうち, 最小のものを求めよ.

想定回答は後ほど。
— すむーずぷりんちゃん🍮【挑戦状】は固定ツイート (@mat_der_D) 2019年12月25日

問題とは関係ありませんが、みなさんはクリスマスプレゼントをもらえましたか？
もしこの問題がプレゼントということであれば、楽しんでいただけたら幸いです。
以下に解答を書きます。

想定解答.
自然数 $n$ が

$\displaystyle n = \prod_{k = 1}^{N} p_{k}^{a_{k}}$

と素因数分解されたとする. ただし $p_{1}, \dots, p_{N}$ は互いに異なる素数であり, $a_{1}, \dots, a_{N}$ は自然数である. このとき $n$ の約数の個数 $d(n)$ は

$\displaystyle d(n) = \prod_{k = 1}^{N} (a_{k} + 1)$

と表される. よって $d(n) = 1225$ となるには

$\displaystyle \prod_{k = 1}^{N} (a_{k} + 1) = 1225$

となることが必要かつ十分である. $1225 = 5^{2} \cdot 7^{2}$ となることから, $1225$ は $5$ 個以上の $2$ 以上の自然数の積で表せないので, $1 \leqq N \leqq 4$ である.

(i) $N = 4$ のとき
$n$ が条件を満たすには

$n = p_{1}^{6} \cdot p_{2}^{6} \cdot p_{3}^{4} \cdot p_{4}^{4}$

となる必要がある. 最も $n$ が小さくなるのは $(p_{1}, p_{2}, p_{3}, p_{4}) = (2, 3, 5, 7)$ のときである. そこで

$N_{0} = 2^{6} \cdot 3^{6} \cdot 5^{4} \cdot 7^{4}$

とおく. 後のために

$N_{1} = 2^{38}, \quad N_{2} = 2^{30} \cdot 3^{6}, \quad N_{3} = 2^{18} \cdot 3^{6} \cdot 5^{4}$

とおく. このとき

$\displaystyle N_{0} = 2^{6} \cdot 3^{2} \cdot 15^{4} \cdot 7^{4} < 2^{6} \cdot 4^{2} \cdot 16^{4} \cdot 8^{4} = 2^{38} = N_{1},$
$\displaystyle N_{0} = 2^{6} \cdot 3^{6} \cdot 35^{4} < 2^{6} \cdot 3^{6} \cdot 64^{4} = 2^{30} \cdot 3^{6} = N_{2},$
$\displaystyle N_{0} < 2^{6} \cdot 3^{6} \cdot 5^{4} \cdot 8^{4} = 2^{18} \cdot 3^{6} \cdot 5^{4} = N_{3}$

が成り立つ.

(ii) $N = 3$ のとき
$n$ は

$n = p_{1}^{a_{1}} \cdot p_{2}^{a_{2}} \cdot p_{3}^{a_{3}}$

と表され, $n$ が条件を満たすとき

$(a_{1} + 1) (a_{2} + 1) (a_{3} + 1) = 5^{2} \cdot 7^{2}$

を満たす. このような $a_{1}, a_{2}, a_{3}$ の組を列挙すると, $a_{1} \geqq a_{2} \geqq a_{3}$ の下で

$(a_{1}, a_{2}, a_{3}) = (48, 4, 4), (34, 6, 4), (24, 6, 6)$

ですべてである. いずれの場合も $(p_{1}, p_{2}, p_{3}) = (2, 3, 5)$ の場合が最小であるが, それぞれ

$2^{48} \cdot 3^{4} \cdot 5^{4} > 2^{38} = N_{1} > N_{0},$
$2^{34} \cdot 3^{6} \cdot 5^{4} > 2^{18} \cdot 3^{6} \cdot 5^{4} = N_{3} > N_{0},$
$2^{24} \cdot 3^{6} \cdot 5^{6} > 2^{18} \cdot 3^{6} \cdot 5^{4} = N_{3} > N_{0}$

となり, $N_{0}$ より大きい.

(iii) $N = 2$ のとき
$n$ は

$n = p_{1}^{a_{1}} \cdot p_{2}^{a_{2}}$

と表され, $n$ が条件を満たすとき

$(a_{1} + 1) (a_{2} + 1) = 5^{2} \cdot 7^{2}$

を満たす. このような $a_{1}, a_{2}$ の組を列挙すると, $a_{1} \geqq a_{2}$ の下で

$(a_{1}, a_{2}) = (244, 4), (174, 6), (48, 24), (34, 34)$

ですべてである. いずれの場合も $(p_{1}, p_{2}) = (2, 3)$ の場合が最小であるが, それぞれ

$2^{244} \cdot 3^{4} > 2^{38} = N_{1} > N_{0},$
$2^{176} \cdot 3^{6} > 2^{30} \cdot 3^{6} = N_{2} > N_{0},$
$2^{48} \cdot 3^{24} > 2^{30} \cdot 3^{6} = N_{2} > N_{0},$
$2^{34} \cdot 2^{34} > 2^{30} \cdot 3^{6} = N_{2} > N_{0}$