C++で実装するバウム・スイート数列（Baum-Sweet Sequence）の求め方

この記事では、バウム・スイート数列（Baum-Sweet Sequence）について解説します。バウム・スイート数列は、0と1のみから構成される二進数列の一種です。

この数列の定義は次の通りです。ある自然数 n を二進表現したとき、連続する 0 のブロックが奇数個含まれていれば第 n 項は 0、そうでなければ第 n 項は 1 となります。

つまり与えられた自然数 n に対して、二進表現中に「奇数長の連続する0」が存在するかどうかを調べるのがタスクです。

具体例

例として n = 4 を考えてみましょう。4 の二進表現は 100 であり、末尾に連続する 0 が 2 個（偶数）あります。奇数長の 0 ブロックは存在しないため、第 4 項の値は 1 となります。

アルゴリズム

バウム・スイート数列の第 n 項を求める手順は以下の通りです。

BaumSweetSeqTerm(n) ――
begin
    長さ n のビット列 seq を定義する
    baum := 1
    len := n の二進表現のビット数
    for i in range 0 to len, do
        j := i + 1
        count := 1
        if seq[i] = 0, then
            for j in range i + 1 to len, do
                if seq[j] = 0, then
                    count を 1 増やす
                else
                    break
                end if
            done
            if count が奇数, then
                baum := 0
            end if
        end if
    done
    return baum
end

アルゴリズムのポイントは、ビット列を先頭から走査し、0 を検出したらその後に続く連続する 0 の個数をカウントすることです。カウントが奇数であれば baum フラグを 0 に更新し、最終的に baum の値を返します。

C++による実装例

#include <bits/stdc++.h>
using namespace std;
int BaumSweetSeqTerm(int n) {
    bitset<32> sequence(n); // ビット表現を格納
    int len = 32 - __builtin_clz(n);
    // __builtin_clz() は先頭の 1 より前にある 0 の個数を返す関数
    int baum = 1; // バウム・スイート数列の第 n 項
    for (int i = 0; i < len;) {
        int j = i + 1;
        if (sequence[i] == 0) {
            int count = 1;
            for (j = i + 1; j < len; j++) {
                if (sequence[j] == 0) // 連続する 0 をカウント
                    count++;
                else
                    break;
            }
            if (count % 2 == 1) // 奇数か偶数かを判定
                baum = 0;
        }
        i = j;
    }
    return baum;
}
int main() {
    int n = 4;
    cout << BaumSweetSeqTerm(n);
}

このコードでは bitset<32> を使って整数 n の二進表現を保持し、__builtin_clz()（先頭の 1 までに並ぶ 0 の個数を返す GCC 組み込み関数）によって有効なビット長を計算しています。その後、連続する 0 のブロックごとに長さを調べ、奇数長のブロックが一つでも見つかれば結果を 0 としています。内側のループで j を進めているため、同じブロックを二重に走査する無駄がなく、計算量は O(len) と効率的です。

出力結果

1

n = 4 の場合、二進表現「100」に含まれる連続する 0 は 2 個（偶数）なので、出力は 1 となります。