C++で数値が連続する整数の和として表現できるか判定する方法

この記事では、ある数値が2つ以上の連続する整数の和として表現できるかどうかを判定する方法を解説します。例えば、12は「3 + 4 + 5」のように表現できます。

この問題には、非常にシンプルで効率的な解法があります。鍵となるのは次の性質です。「2の累乗である数は、連続する整数の和として表現できない」というものです。この性質を理解するために、以下の2つの事実を押さえておきましょう。

• 任意の2つの連続する整数の和は必ず奇数になります。これは、一方が奇数でもう一方が偶数であるためです。
• 2ⁿ = 2^(n-1) + 2^(n-1) という関係が常に成り立ちます。

これらの事実から、2の累乗は1以外の奇数の約数を持たないため、どのように分解しても連続する整数の和にはできません。逆に言えば、2の累乗以外のすべての正の整数は、連続する整数の和として表現可能です。

実装例（C++）

以下のコードでは、ビット演算 n & (n-1) を使って2の累乗かどうかを判定しています。nが2の累乗の場合、n と n-1 のビットパターンは完全に異なるため、AND演算の結果は0になります。この性質により、O(1)の計算量で高速に判定できます。

#include <iostream>
using namespace std;

bool isSumofconsecutiveNumbers(int n) {
    // nが2の累乗でなければtrueを返す
    if ((n & (n - 1)) && n) {
        return true;
    } else {
        return false;
    }
}

int main() {
    int num = 36;
    if (isSumofconsecutiveNumbers(num)) {
        cout << "Can be represented";
    } else {
        cout << "Cannot be represented";
    }
}

出力結果

Can be represented

この例では、36は「11 + 12 + 13」のように連続する整数の和として表現できるため、"Can be represented" が出力されます。もし引数が8や16などの2の累乗であれば、"Cannot be represented" となります。この手法は追加のループや配列を必要とせず、大きな数値に対しても即座に判定できるのが魅力です。