阪大の数学をプログラミングの目で見ると　～2024年理系第5問～

　こんにちは。東進衛星予備校　金沢南校の北川です。

　私事ではありますが、本日基本情報技術者試験に合格し、無事「ほんの少しならPCと対話できるおじさん」になりました。情報処理技術者としてはまだまだひよっこ、より上位の人の監督が必要とされる立場ではありますが、より正確かつ面白い情報発信ができるよう心がけて参りますのでよろしくお願いいたします。

　さて、入試問題をコンピュータの力で解く企画も第3弾。[1]

　今回扱う問題は次の問題です。

　東進の講評としてはやや難扱いのこの問題、(1)は確かに少し面倒な手順と正確な説明力が試されます。しかし、(2)は問題の意味さえ理解してしまえばパソコンにすべてを代理させることが可能です。

　今回は(2)に焦点を当てるのが目的ですから、(1)の証明については省略します。包除原理と呼ばれる手順と、倍数についての基本的な知識さえあれば証明ができます。

　では、ここからは(2)をプログラミングで解く方法について考えてみましょう。

1.トーシェント関数を愚直に実装する

　さて、実際にこの問題をプログラミングで解くとなると、様々な解法が考えられます。今回は（恐らく分かりやすいと思われる）以下の方策をとってみます。

(1)まず、問題文中で\(f(n)\)とされている関数を実装する。

(2)\(n\)を5から100まで順に動かし、実際に\(n/f(n)\)を計算させて判定する。

　\(f(n)\)の実装の仕方1つ取っても様々あります。今回はnが100までと比較的小さいですから、一番愚直なパターン――つまり、実際に1から\(n\)まで調べる方法――で実装してみることにします。

　まず、「互いに素である」とはどういう意味だったか思い出してみましょう。ある2つの正の整数m,nについて、mとnが「互いに素である」というのは、「mとnの最大公約数が1である」ということです。

　つまり、ある正整数とある正整数の最大公約数がいくつかを判断する方法さえあれば、それを1からまで繰り返すことで\(f(n)\)に期待する出力が得られそうです。

　早速実装してみましょう。mとnの最大公約数を求める関数をgcd(m,n)と書くとすると、以下のように実装することができます（以下のコード中ではtotient(n)[2]と書いてありますが、f(n)のことです）。

def totient(n: int) -> int:
    # 意図しない入力がされた場合、除外する
    if n < 1:
        return -1 
    counter = 0
    # iを1からnまで増やす
    # もしnとiの最大公約数が1なら変数counterを1増やす
    for i in range(1, n + 1):
        if gcd(n, i) == 1:
            counter += 1
    return counter

　これは1からnまですべての整数を走査して上手く行くかどうかを調べます。gcd(n, i)をn回計算することから、全体の計算回数としてはn×gcd(n, i)の値に比例することが分かります。gcd(n, i)がある程度効率的に実装されてさえいれば、問題なく動きそうです。

　あとはgcd(m,n)の中身を実装すればよさそうですね。どうするのかと言えば、かつて学校で習った人も多い「アレ」を使えばよいのです。

2.ユークリッドの互除法を実装する

　「アレ」というのはユークリッドの互除法です。聞いたことがない方もいるかもしれませんので、説明しておくと、ある正の整数mとnが与えられたときにmとnの最大公約数がいくつかを調べる手順です。

　実際にはこのように進行します。

① mとnのうち、大きいほうを小さい方で割った余りを出す(mとnが等しい場合はどちらをどちらで割った余りでもよい)。

② 「①で出した余り」と、「mとnのうち小さいほう」をそれぞれ新しくmとnに設定する。

③ mとnのどちらかが0になるまで①と②の手順を繰り返し続ける。最終的に出た2つの数のうち、0でない方の数が求める最大公約数である。

　具体的な例を出してやってみます。例えば、24と36の最大公約数はいくつになるでしょう？

① 36の方が24より大きいので、36を24で割った余りを求めます。今回は12ですね。

② 「①で出した余り(12)」と、「36と24のうち小さいほう(24)」について、同じ操作を考えていきます。

　24の方が12より大きいですから、24を12で割った余りを考えます。これは0になります。

③ 「②で出した余り(0)」と、「24と12のうち小さいほう(12)」について考えます。今回は片方が0ですから、残った12の方が求める最大公約数であると分かります。

　実際に、36と24の最大公約数が12であることは割り算で簡単に確かめられます。

　今回は「なぜこの方法が上手く行くのか」の証明には立ち入りません（高校数学の範囲内である程度納得できる証明は得られるのではないかと思います）。代わりに、これを上手く実装する方法について考えていきます。

　結論から書くと、今回のコードはこちらです。

def gcd(m: int, n: int) -> int:
    # 予期しない入力を弾く
    if m <= 0 or n <= 0:
        return -1

    # もしnの方が大きければmとnを入れ替える
    # これにより、常にmの方が大きいと考えて操作できる
    if m < n:
        m, n = n, m
    # 小さいほう(=n)が0になるまでひたすら所定の計算を続ける
    while n != 0:
        m, n = n, m % n
    return m

　実装する際にネックになりやすいのは「大きいほうから小さいほうを」という処理です。

　しかしよく考えると、「ある数n」と「nで割った余りr」は、常にnよりrの方が小さくなりますから、最初だけきちんと処理すればあとは深く考えなくても勝手にm>nを満たすようにコードが書けるわけです。

　計算量については、mの方が大きいとするとざっくりlogm（底は2であることに注意）に比例します。これはmが100以下という制約下では十分に高速です。

　そういうわけで、この部分も実装できました。あとは組み合わせてコードを書くだけです。

　先のf(n)の式と合体させると、以下のようなコードになります。

# 最大公約数を求める関数
def gcd(m: int, n: int) -> int:
    if m <= 0 or n <= 0:
        return -1
    if m < n:
        m, n = n, m
    while n != 0:
        m, n = n, m % n
    return m

# 1以上n以下でnと互いに素な正の整数の個数を求める関数
def totient(n: int) -> int:
    if n < 1:
        return -1
    counter = 0
    for i in range(1, n + 1):
        if gcd(n, i) == 1:
            counter += 1
    return counter

# 答えを入れる配列を用意
answer = []

# 5から101まで「nをf(n)で割った余りが0かどうか（＝割り切れるか）」を判定
for i in range(5, 101):
    if i % totient(i) == 0:
        answer.append(i)

# 答えの配列をアンパックして出力
print(*answer)

　実行すると、1秒足らずで以下のような結果が得られます。

6 8 12 16 18 24 32 36 48 54 64 72 96

　これは今回の問題の答えとぴったり一致します。無事に解けましたね！

3.おわりに

　プログラミングで問題を解くと、確かに人が解くより圧倒的に早く答えが出ます。

　しかし、そのプログラムを組むのは、様々なアルゴリズムを理解した人間です。もちろんこれくらいのコードならAIも書けますが、そこに何が書いてあるのか読むのはやはり人間です。

　この記事シリーズでは「コンピュータだったら早く解けた！」という話だけをしたいのではなく、「コンピュータはどんな命令を受け取って期待する結果を出しているのか」という理屈の部分の話がしたいと常に思っています。

　今回の記事では「互除法」という簡単な、それでいて頻繁に使いうるアルゴリズムをテーマに上げました。数学の問題を一風変わった解き方で解くことを通して、少しでも身近なアルゴリズムへの関心が深まれば幸いです。

　今月の記事はここまで。来月もお楽しみに！

====================================================================

[1] 前回の記事はこちらから。東大の問題を扱ったものになります。

[2] 問題文中でf(n)と呼ばれている関数は、たびたび「オイラーのトーシェント関数」と呼ばれます。今回はこのネーミングから借りて関数を命名しています。