C++で学ぶラグランジュの四平方定理

はじめに

このチュートリアルでは、ラグランジュの四平方定理について解説します。

ラグランジュの四平方定理とは、「すべての自然数は、高々4つの非負整数の平方の和で表すことができる」という有名な定理です。例えば、7 = 1×1 + 1×1 + 1×1 + 2×2 のように表せます。

以下のコードでは、与えられた数 n に対して、この定理を満たす4つの数の組み合わせをすべて求めます。

コード例

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

#include <bits/stdc++.h>
using namespace std;

void printSquareCombinations(int n) {
    for (int i = 0; i * i <= n; i++) {
        for (int j = i; j * j <= n; j++) {
            for (int k = j; k * k <= n; k++) {
                for (int l = k; l * l <= n; l++) {
                    if (i * i + j * j + k * k + l * l == n) {
                        cout << n << " = " << i << "*" << i << " + " << j << "*" << j << " + " << k << "*" << k << " + " << l << "*" << l << endl;
                    }
                }
            }
        }
    }
}

int main() {
    int n = 25;
    printSquareCombinations(n);
    return 0;
}

実行結果

上記のコードを実行すると、次のような出力が得られます。

25 = 0*0 + 0*0 + 0*0 + 5*5
25 = 0*0 + 0*0 + 3*3 + 4*4
25 = 1*1 + 2*2 + 2*2 + 4*4

アルゴリズムのポイント

このコードでは、4重ループによってすべての組み合わせを網羅的に調べています。各ループの開始値を直前のループ変数と同じにすることで、順序が異なるだけの重複した組み合わせを排除し、無駄なく探索できるのがポイントです。

なお、各ループは最大でも √n 回程度しか回らないため、全体の計算量は O(n²) となります。より大きな数を扱う場合は、動的計画法や数論的な性質を利用した高速な手法を検討するとよいでしょう。

まとめ

この記事では、ラグランジュの四平方定理をC++で実装する方法を紹介しました。本チュートリアルについてご不明な点がある場合は、コメント欄でお気軽にお知らせください。