Pythonで「最初のN個の自然数の2乗和がX以下」となる最大のNを二分探索で求める方法

整数 X が与えられたとき、「最初の N 個の自然数の2乗の合計が X を超えない」ような最大の N を求める問題を考えてみましょう。

例えば、X = 7 の場合を考えます。N = 3 とすると、1² + 2² + 3² = 1 + 4 + 9 = 14 となり、X = 7 を超えてしまいます。一方、N = 2 なら 1² + 2² = 5 であり、X 以下に収まります。したがって、答えは 2 となります。

解法のアプローチ

この問題は、次の手順で二分探索（バイナリサーチ）を使うことで効率的に解くことができます。

• まず、2乗和を計算する関数 sum_of_squares() を定義します。引数として N を受け取ります。

• 計算には有名な公式「N × (N + 1) × (2N + 1) / 6」を使用します。これにより、ループで1つずつ足し合わせる必要がなく、O(1) で2乗和を求められます。

• メインの処理では、探索範囲の下限 low := 1、上限 high := 100000、答えの初期値 N := 0 を設定します。

• low ≤ high の間、以下を繰り返します。

  • mid := (high + low) / 2 として中央値を求めます。

  • sum_of_squares(mid) ≤ X であれば、mid は条件を満たす候補なので、N := mid と更新し、さらに大きい値を探すために low := mid + 1 とします。

  • そうでなければ（X を超えてしまった場合）、high := mid − 1 として探索範囲を狭めます。

• ループが終了した時点での N が答えとなります。

この方法の計算量は O(log N) であり、非常に大きな X に対しても高速に動作するのがポイントです。

実装例

それでは、実際のPythonコードを見てみましょう。

def sum_of_squares(N):
    res = (N * (N + 1) * (2 * N + 1)) // 6
    return res

def get_max(X):
    low, high = 1, 100000
    N = 0
    while low <= high:
        mid = (high + low) // 2
        if sum_of_squares(mid) <= X:
            N = mid
            low = mid + 1
        else:
            high = mid - 1
    return N

X = 7
print(get_max(X))

入力

7

出力

2

コードのポイント

• 整数除算の使用： Pythonでは // 演算子を使うことで、結果を整数として取得できます。N × (N + 1) × (2N + 1) は必ず6で割り切れるため、誤差は発生しません。

• 上限値の設定： high = 100000 としていますが、これは十分大きな値です。必要に応じて調整可能です。ちなみに、sum_of_squares(100000) ≒ 3.3 × 10¹⁴ となるため、かなり大きな X まで対応できます。

• 単調性の利用： 2乗和は N に対して単調増加するため、二分探索が適用できます。これがこのアルゴリズムが成立する数学的な根拠です。

なお、二分探索を使わずに、平方根を用いて直接計算する方法もあります。N³/3 ≒ X より、N ≈ (3X)^(1/3) の近傍を調べる方法です。しかし、二分探索の方がロジックがシンプルで汎用的なため、競技プログラミングなどでも広く使われる手法です。