整数問題2

ちょうど15個の約数を持つ自然数、の中で最小のものを求めよ。

(注: 約数には、1及びその数自身を含める。例えば、6の約数は、1, 2, 3, 6の4個である。)

解答1

約数の個数が奇数になるような整数を発見

自然数nの約数の個数をa(n)と表すと、
a(1)=1, a(2)=2, a(3)=2, a(4)=3, a(5)=2, a(6)=4, a(7)=2, a(8)=4, a(9)=3, a(10)=4, ...
nのある約数をpとすると、n/pもnの約数である。よって、a(n)は偶数になる。
しかし、nが平方数の場合は、pがnの平方根の場合にp=n/pとなるため、a(n)は奇数になる。
a(n)=15となるのはnが平方数の場合である。
10以降の平方数nについて、a(n)は次のとおりである。
a(16)=5, a(25)=3, a(36)=9, a(49)=3, a(64)=7, a(81)=5, a(100)=9, a(121)=3, a(144)=15, ...
よって求める数は、144.


解答2

素因数分解された整数と、その約数の個数、の関係を利用

p, q, r, ...を互いに異なる素数とするとき、合成数n=paqbrc...の約数は、
(pa+pa-1+...+p+1)(qb+...+1)(rc+...+1)...
を展開したときの項として得られる。
そして、約数の個数は、
(a+1)(b+1)(c+1)...となる。
これが15になるのは、a=14又はa=4, b=2のときである。
a=14のとき、nが最小になるのはpが最小の素数2のときである。
このとき、n=214=16384.
又、a=4, b=2のとき、nが最小になるのはp=2, q=3のときである。
このとき、n=24*32=144.
よって求める数は、144.


数学の問題

© 2006 島崎 崇
更新: 2013年4月14日