トップ› 九州大学› 1998年› 文系第5問

九州大学 1998年文系第5問解説

方針・初手

与えられたBASICのプログラムを1行ずつ数学的な意味に翻訳し、このプログラムがどのような計算を行っているかを把握する。特に、INT 関数がガウス記号の役割を果たすこと、X=N-K*INT(N/K) が割り算の余りを求める式であることを見抜くのが最初のステップである。

解法1

まず、プログラムの各行の意味を解析する。プログラム中の INT(x) は $x$ を超えない最大の整数を表し、数学におけるガウス記号 $[x]$ と同じ働きをする。

30行目の M=2 * INT(N/2)+1 について、 $N$ が偶数 $2m$ のとき、$INT(N/2) = m$ より $M = 2m+1 = N+1$ となる。 $N$ が奇数 $2m+1$ のとき、$INT(N/2) = m$ より $M = 2m+1 = N$ となる。

40行目の FOR K=1 TO M STEP 2 により、$K$ は $1, 3, 5, \dots, M$ と奇数の値を順番にとる。

50行目の X=N-K * INT(N/K) について、$INT(N/K)$ は $N$ を $K$ で割ったときの商であるため、$X$ は $N$ を $K$ で割ったときの余りを表す。

60行目と70行目により、余り $X$ が $0$ になる場合、すなわち $N$ が $K$ で割り切れる場合のみ、$S$ に $K$ の値が加算される。

$K$ は $M$ まで動くが、$K > N$ のときは $X = N \neq 0$ となり加算されないため、結局このプログラムは 「入力された自然数 $N$ の正の奇数の約数をすべて足し合わせる」 ものであると分かる。

(1) $N=12$ のとき、$12$ の正の奇数の約数は $1, 3$ である。したがって、出力される値 $S$ は

$$1 + 3 = 4$$

(2) 出力が $1$ となるのは、$N$ の正の奇数の約数が $1$ のみであるときである。これは、$N$ を素因数分解したときに、奇数の素因数を持たないことと同値である。したがって、求める自然数 $N$ は $2$ の累乗、すなわち $n$ を $0$ 以上の整数として $2^n$ と表される数である。

(3) 自然数 $N$ を次のように素因数分解する。

$$N = 2^a \cdot p_1^{e_1} \cdot p_2^{e_2} \cdots p_k^{e_k}$$

（$a$ は $0$ 以上の整数、$p_1, \dots, p_k$ は互いに異なる奇素数、$e_1, \dots, e_k$ は自然数）

$N$ の正の奇数の約数の総和 $S$ は、約数の総和の公式より以下のようになる。

$$S = (1 + p_1 + p_1^2 + \dots + p_1^{e_1}) \cdots (1 + p_k + p_k^2 + \dots + p_k^{e_k})$$

この出力 $S$ が奇数になる条件を考える。積が奇数になるためには、各因数 $(1 + p_i + p_i^2 + \dots + p_i^{e_i})$ がすべて奇数でなければならない。 $p_i$ は奇数であるから、$p_i$ の累乗はすべて奇数である。奇数を足し合わせて奇数になるためには、足し合わせる項の数が奇数個でなければならない。因数に含まれる項の数は $(e_i + 1)$ 個であるため、$e_i + 1$ が奇数、すなわち $e_i$ が偶数である必要がある。これがすべての $i$ について成り立つので、$N$ の奇数部分は平方数となる。

さらに、出力 $S$ が $1$ より大きくなるためには、$N$ が $1$ 以外の奇数の約数を持つ必要があるため、奇数部分は $1$ ではない（すなわち奇素数を含む）。以上より、出力が $1$ より大きな奇数となる自然数 $N$ は、「$1$ より大きな奇数の平方数」と「$2$ の累乗」の積として表される。

$1$ より大きな奇数の平方数を $L^2$ （$L=3, 5, 7, \dots$）とする。 $N$ の範囲は $2 \leqq N \leqq 50$ である。

(i) $L=3$（すなわち奇数部分が $9$）のとき $N = 9 \cdot 2^a$ となり、$2 \leqq 9 \cdot 2^a \leqq 50$ を満たすのは $a = 0, 1, 2$ のとき。これに対応する $N$ は $N = 9, 18, 36$。

(ii) $L=5$（すなわち奇数部分が $25$）のとき $N = 25 \cdot 2^a$ となり、$2 \leqq 25 \cdot 2^a \leqq 50$ を満たすのは $a = 0, 1$ のとき。これに対応する $N$ は $N = 25, 50$。

(iii) $L=7$（すなわち奇数部分が $49$）のとき $N = 49 \cdot 2^a$ となり、$2 \leqq 49 \cdot 2^a \leqq 50$ を満たすのは $a = 0$ のとき。これに対応する $N$ は $N = 49$。

$L \geqq 9$ のときは $L^2 \geqq 81$ となり、$N \leqq 50$ を満たさない。以上より、条件を満たす $N$ をすべて求めると、$N = 9, 18, 25, 36, 49, 50$ である。

解説

プログラムの処理を数学の言葉に翻訳する問題である。特に INT 関数を用いて「商」と「余り」を表現する N - K * INT(N/K) は、情報処理やアルゴリズムで頻出の記法である。この意味に気づくことができれば、あとは整数問題としての標準的な解法に持ち込める。 (3)では、約数の総和が奇数になる条件が「素因数分解した際の指数がすべて偶数であること（平方数であること）」と同値になるという、整数分野の有名な性質を利用している。