C++で整数を連続する自然数の和として表現する方法の数を求める

整数 num が入力として与えられたとき、その数を「2つ以上の連続する自然数の和」として表現できるパターンが何通りあるかを求めるのが本記事の目的です。たとえば n=3 の場合は 1+2 と表現できるため、答えは 1 通りになります。

入力例

num=6

出力

連続する数の和として数を表現する方法の数：1

説明

6 を連続する自然数の和で表現する方法：1+2+3

入力例

num=19

出力

連続する数の和として数を表現する方法の数：1

説明

19 を連続する自然数の和で表現する方法：9+10

アルゴリズムの考え方

ここで採用するアプローチは、対象の数を「a + (a+1) + (a+2) + … + (a+i)」という連続する自然数の和の形で表現するものです。この和は次のように変形できます。

a×(i+1) + (1+2+…+i) = a×(i+1) + i×(i+1)/2

したがって、次の等式が成り立ちます。

num = a×(i+1) + i×(i+1)/2

これを開始値 a について解くと、

a = [num − i×(i+1)/2] / (i+1)

あとは i を 1 から順に増やしながら「i×(i+1)/2 < num」を満たす範囲で a を計算し、a がきれいな整数になれば、その項数での表現が可能であることが分かります。

処理の手順

• 整数 num を入力として受け取ります。
• 関数 sum_consecutive(int num) は、num を連続する自然数の和として表現する方法の数を返します。
• カウンタ変数 count を 0 で初期化します。
• 計算結果を保持する一時変数 res を float 型で用意します。
• for ループで i を 1 から始め、「i×(i+1)/2 < num」を満たす間だけ繰り返します。
• [num − i×(i+1)/2] / (i+1) を計算して res に格納します。
• res が整数かどうか（res − (int)res が 0 になるか）を判定し、整数であれば count をインクリメントします。
• ループ終了後の count が、求めるべき表現方法の総数となります。
• count を結果として返します。

コード例

#include <bits/stdc++.h>
using namespace std;
int sum_consecutive(int num){
    int count = 0;
    int temp = num * 2;
    float res;
    for (int i = 1; i * (i + 1) < temp; i++){
        int store = i + 1;
        res = (1.0 * num - (i * (i + 1)) / 2) / store;
        float check = res - (int)res;
        if(check == 0.0){
            count++;
        }
    }
    return count;
}
int main(){
    int num = 20;
    cout<<"Count of ways to express a number as sum of consecutive numbers are: "<<sum_consecutive(num) << endl;
    return 0;
}

出力

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

Count of ways to express a number as sum of consecutive numbers are: 1

補足

サンプルコードの num=20 の場合、20 = 2+3+4+5+6 と表現できるため、答えは 1 通りです。ちなみに数学的には「2つ以上の連続する自然数の和で表せない数」は 2 の累乗（1, 2, 4, 8, 16, …）のみであることが知られています。興味があれば、さまざまな値を入力して挙動を確かめてみてください。