C++でフェルマーの最終定理を検証するプログラムの作り方

数論におけるフェルマーの最終定理(別名：フェルマーの予想)とは、「2より大きい整数 n に対して、次の等式を満たす3つの正の整数 a, b, c は存在しない」と主張する有名な定理です。

aⁿ + bⁿ = cⁿ

つまり、次のように整理できます。

• n ≤ 2 の場合：aⁿ + bⁿ = cⁿ を満たす組み合わせが存在します。
• n ≥ 3 の場合：aⁿ + bⁿ ≠ cⁿ となり、そのような組み合わせは一切存在しません。

n = 2 の具体例(ピタゴラス数)

3, 4, 5 ⇒ 3² + 4² = 9 + 16 = 25 = 5²

5, 12, 13 ⇒ 5² + 12² = 25 + 144 = 169 = 13²

この問題では、範囲 [L, R] とべき乗を表す3つの値 L・R・pow が与えられます。与えられた範囲とべき乗に対して、フェルマーの最終定理が実際に成り立つことを検証するのが課題です。

問題を理解するための例

例1:
入力:L = 4, R = 12, power = 2
出力：5, 12, 13

例2:
入力:L = 4, R = 12, power = 4
出力：該当する値は見つかりません

解法アプローチ

まず、べき乗 n が2より大きいかどうかを確認します。2より大きい場合は、フェルマーの最終定理により解が存在しないことが保証されているため、「該当する値は見つかりません」と出力して終了します。

n が2以下の場合は、範囲 [L, R] 内のすべての組み合わせ(a ≤ b)について、aⁿ + bⁿ = cⁿ を満たす値が存在するかを順番にチェックしていきます。

アルゴリズムの流れ

1. n ≥ 3 ならば、定理により解は存在しないため即座に処理を終了します。
2. n ≤ 2 の場合、二重ループで a と b のすべての組み合わせを走査し、sum = aⁿ + bⁿ を計算します。
3. c を sum の n 乗根として求め、cⁿ が sum と一致するか(つまり sum が完全な n 乗数かどうか)を確認します。
4. 条件を満たす組み合わせが見つかればそれを出力し、最後まで見つからなければ「見つかりません」と出力します。

ソリューションの動作を示すプログラム

例

#include <iostream>
#include <math.h>
using namespace std;

void checkFermatsLastTh(int L, int R, int n) {

    if (n >= 3)
    cout<<"No example found!";
    else {
        for (int a = L; a <= R; a++)
        for (int b=a; b<=R; b++)
        {
            int sum = pow(a, n) + pow(b, n);
            double c = pow(sum, 1.0/n);
            int cpowN = pow((int)c, n);
            if (cpowN == sum)
        {
            cout<<"Example found with value : "<<a<<", "<<b<<", "<<c;
            return;
        }
    }
    
    cout << "No example found!";
    }
}

int main() {
    
    int L = 3, R = 15, power = 2;
    cout<<"Run 1 \n";
    checkFermatsLastTh(L, R, power);
    
    L = 5, R = 42; power = 5;
    cout<<"\n\nRun 2\n";
    checkFermatsLastTh(L, R, power);

    return 0;
}

出力

Run 1
Example found with value : 3, 4, 5
Run 2
No example found!

実行結果を見ると、power = 2 の場合はピタゴラス数である 3, 4, 5 の組み合わせが見つかり、power = 5 の場合はフェルマーの最終定理どおり該当する組み合わせが存在しないことが確認できます。

なお、この実装では浮動小数点演算(pow 関数)を使用しているため、非常に大きな値を扱う際には丸め誤差が生じる可能性があります。厳密な検証が必要なケースでは、整数型のみでの累乗計算や多倍長整数ライブラリの利用を検討するとよいでしょう。