C++でウッダル数（Woodall Number）を判定する方法

この問題では、ある数値が与えられ、それがウッダル数（Woodall number）であるかどうかを判定します。

ウッダル数とは、次の式で表される特殊な数のことです。

Wn = n × 2n − 1

最初の5つのウッダル数は 1、7、23、63、159 です。

具体例を見て、問題を理解しましょう。

入力

X = 159

出力

Yes

159 は 5 × 2⁵ − 1 = 159 と表せるため、ウッダル数であると判定できます。

解法のアプローチ

この問題を解くには、まず数の性質を観察します。ウッダル数は n × 2ⁿ − 1 という形で表されるため、必ず奇数になります。したがって、与えられた数が偶数であれば、その時点でウッダル数ではないと判断できます。

数が奇数の場合は、その数に 1 を加えてから、2 で割れる限り繰り返し 2 で割っていき、割った回数をカウントします。そして、各段階で「割った回数」と「残った数」が一致するかどうかを確認します。

この方法が成立する理由は、ウッダル数に 1 を加えると n × 2ⁿ という形になるためです。2 で割り続けた結果、最終的に残る値が n であり、そのときの割った回数も n に等しければ、その数はウッダル数であると判定できます。

実装例

#include <iostream>
using namespace std;

bool isWoodallNumber(int x){
    if (x % 2 == 0)
        return false;
    if (x == 1)
        return true;
    x += 1;
    int p = 0;
    while (x % 2 == 0){
        x = x / 2;
        p++;
        if (p == x)
            return true;
    }
    return false;
}

int main() {
    int x = 1424;
    cout << x;
    (isWoodallNumber(x)) ? cout << " はウッダル数です" : cout << " はウッダル数ではありません";
    return 0;
}

出力

1424 はウッダル数ではありません

コードの解説

isWoodallNumber 関数では、まず入力値が偶数かどうかを確認し、偶数であれば false を返します。次に、x が 1 の場合は true を返します（1 = 1 × 2¹ − 1 はウッダル数です）。

その後、x に 1 を加え、2 で割れる限り割り続けながら割った回数 p をカウントします。割った回数 p と残りの値 x が一致した時点で true を返し、ループが終了しても一致しなければ false を返します。

計算量

時間計算量： O(log n) — 数を 2 で割り続けるため、反復回数は対数オーダーに収まります。
空間計算量： O(1) — 追加のメモリは定数個の変数のみで済みます。