Pythonで合計がNに等しい4つの約数の最大積を求める方法

問題の概要

ある整数 N が与えられたとき、N の約数の中から次の 2 つの条件を同時に満たす 4 つの約数を選び、その積を求めることを考えます。

• 選んだ 4 つの約数の合計が N と等しいこと
• その 4 つの約数の積が最大になること

なお、積を最大化するうえで、4 つの約数がすべて同じ値であっても構いません。むしろ一般に、合計が固定されたときは各数ができるだけ均等に近いほど積は大きくなります。

たとえば入力が N = 60 の場合、出力は 50625 です。60 の約数は 1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60 ですが、この中から 15 を 4 回選ぶと、合計は 15 × 4 = 60 で条件を満たし、積も 15⁴ = 50625 となって最大になります。

解法のアプローチ

「4 つの数の合計が N になる」という条件は、2 つの数のペアの合計に分解すると扱いやすくなります。全体の流れは次のとおりです。

1. N の約数をすべて列挙し、リスト v に格納する。
2. 約数ペア (v[i], v[j]) のうち合計が N 未満になるものをすべて調べ、その合計値をリスト v1 に記録するとともに、「どのペアからできた合計か」を配列 map1 に、「その合計が実現可能か」を辞書 my_map に保存する。
3. 各合計値 t に対して、残りの値 (N − t) も「2 つの約数の合計」として実現できるかを確認する。実現できれば、対応する 4 つの約数の積を計算し、最大値を更新する。
4. 最後まで最大値が更新されない場合は、条件を満たす組み合わせが存在しないので「Not Possible（解なし）」を出力する。

詳細な手順

• my_map := 新しい辞書を作成する
• v := 新しいリスト、v1 := 新しいリストを作成する
• i を 1 から ⌈√n⌉ まで繰り返す:
  • n % i == 0（i が約数）なら、i を v の末尾に追加する
  • さらに i ≠ n // i かつ i ≠ 1 なら、n // i も v の末尾に追加する（平方数や 1 による重複を防ぐ）
• s := v のサイズ、maximum := −1 とする
• map1 := サイズ (n + 5) の配列を 0 で初期化する
• i を 0 から s−1 まで、j を i から s−1 まで繰り返す:
  • v[i] + v[j] < n なら、v[i] + v[j] を v1 に追加し、map1[v[i] + v[j]] = [v[i], v[j]]、my_map[v[i] + v[j]] = 1 を記録する
• s := v1 のサイズとする
• i を 0 から s−1 まで繰り返す:
  • element := n − v1[i] とする
  • element が my_map に存在するなら、a = map1[v1[i]][0]、b = map1[v1[i]][1]、c = map1[n − v1[i]][0]、d = map1[n − v1[i]][1] とし、maximum を max(a × b × c × d, maximum) で更新する
• maximum が −1 のままなら「Not Possible」を表示し、そうでなければ maximum を表示する

Pythonでの実装例

理解を深めるために、実際の実装を見てみましょう。

from math import sqrt, ceil, floor

def get_product(n):
    my_map = dict()
    v = []
    v1 = []

    # ステップ1: 約数の列挙
    for i in range(1, ceil(sqrt(n)) + 1):
        if (n % i == 0):
            v.append(i)
            if (i != (n // i) and i != 1):
                v.append(n // i)

    s = len(v)
    maximum = -1
    map1 = [0] * (n + 5)

    # ステップ2: 2つの約数の合計をすべて記録
    for i in range(s):
        for j in range(i, s):
            if (v[i] + v[j] < n):
                v1.append(v[i] + v[j])
                map1[v[i] + v[j]] = [v[i], v[j]]
                my_map[v[i] + v[j]] = 1

    # ステップ3: 残りの半分もペアで作れるか確認
    s = len(v1)
    for i in range(s):
        element = n - (v1[i])
        if (element in my_map):
            a = map1[v1[i]][0]
            b = map1[v1[i]][1]
            c = map1[n - v1[i]][0]
            d = map1[n - v1[i]][1]
            maximum = max(a * b * c * d, maximum)

    # ステップ4: 結果の出力
    if (maximum == -1):
        print("Not Possible")
    else:
        print("Maximum product", maximum)

n = 60
get_product(n)

入力

60

出力

Maximum product 50625

まとめ

この記事では、合計が N に等しくなる 4 つの約数のうち積が最大の組み合わせを求める方法を解説しました。鍵となるのは、4 つの数の問題を「2 つの数のペアの合計」に分割し、あらかじめ計算したペア情報を辞書で管理することで、残り半分との対応を高速に判定できる点です。これは Meet in the Middle（ミート・イン・ザ・ミドル）と呼ばれる考え方に近く、単純な 4 重ループに比べて計算量を大きく削減できます。条件を満たす組み合わせがひとつも存在しない場合は「Not Possible」が出力される点にも注意してください。