モーザー・ド・ブリュイン数列ジェネレーター | 4の累乗計算ツール

モーザー・デ・ブライン数列とは？

モーザー・デ・ブライン数列は、それぞれを相異なる 4 のべきの和として表せる整数のリストです。0、1、4、5、16、17、20、21、64、65、68、69、80、81、84、85で始まり、無限に続きます。数学者のレオ・モーザーとニコラース・ホーファート・デ・ブライにちなんで名付けられました。オンライン整数列百科事典では A000695 として登録されています。

ある数がこの数列に属するのは、その 4 進表記が 0 と 1 の数字だけを使い、2 や 3 を決して使わない場合に限ります。たとえば、21 は 4 進法では 111 と書けるため、数列に属します。22 は 4 進法では 112 と書かれるため、属しません。

モーザー・デ・ブライン数列の公式

この数列は、同値な3通りの方法で定義できます。

相異なる 4 のべきの和

ある整数 n が数列に含まれるのは、次のように表せる場合です。

$n = \sum_{i \in S} 4^i$

各 4 のべきが高々1回しか使われない、非負整数の集合 S に対して。

4 進の数字による判定

数を 4 進法で表します。すべての数字が 0 または 1 なら、その数は数列に含まれます。2 または 3 が一つでもあれば、含まれません。

二進数から 4 進数への置換

n = 0 から項を数えると、添字 n の項は次のようになります。

$M(n) = \sum_{i=0}^{k} b_i \cdot 4^i$

ここで $b_i$ は n の二進数の各桁です。つまり、n を二進法で書き、各二進数の数字を同じ位置の 4 進数の数字として読み取ります。生成器がこの方法を使うのは、ビットの確認と数の加算だけで済むためです。

第 n 項の計算方法

M(n) を求めるため、生成器は n = 0 から始めて、各添字 n に対して次の処理を行います。

1. n の二進表記を確認する。
2. 1 と等しい各ビットについて、その位置を j として、4^j を累計に加える。
3. 0 と等しいビットは無視する。
4. その累計が M(n) である。

計算例：M(5)

• 5 の二進表記は 101 です。
• ビット 0（右端）は 1 なので、4⁰ = 1 を加えます。
• ビット 1 は 0 なので、何も加えません。
• ビット 2 は 1 なので、4² = 16 を加えます。
• 合計：1 + 16 = 17。

したがって M(5) = 17 です。M(0) から数え始めるため、これは生成器が出力する6番目の値です。

最初の 32 項の例

数が数列に含まれるか確認する方法

数を 4 進法に変換し、その数字を読み取ります。

• 85：4 進法では 85 は 1111（64 + 16 + 4 + 1）です。0 と 1 だけが現れるため、85 は数列に含まれます。
• 90：4 進法では 90 は 1122 です。2 が含まれるため、90 は数列に含まれません。

増加率

この数列は急速に増加します。これは、添字にビットが一つ増えるたびに、それが加える値がおよそ四倍になるためです。M(19) は 261 です。M(99) は 5,125 です。M(999) は、この生成器が生成できる最大の項で、349,205 です。添字が大きくなるほど項どうしの間隔は広がり、この数列はまばらになります。無限個の項を持つにもかかわらず、ほとんどの整数は現れません。

モーザー・デ・ブライン数列生成器の使い方

1. 生成する項数を入力します。空欄のままにすると、初期値は 20 になります。
2. 項のリストは自動的に更新され、M(0) から始まります。
3. 「結果をコピー」ボタンでリスト全体をコピーできます。

このツールは 1 から 1000 までの整数を受け付けます。小数、負の数、数字以外の入力は拒否されます。20 項を要求すると、M(0) から M(19) までが返され、最後に表示される値は 261 です。計算はすべてブラウザー内で行われるため、結果はすぐに表示され、データがサーバーに送信されることはありません。

関連する数列

• 2 のべき（OEIS A000079）：1、2、4、8、16、32など。通常の二進数を構成する基本要素です。
• 相異なる 3 のべきの和（OEIS A005836）：0、1、3、4、9、10、12、13など。モーザー・デ・ブライン数列と同じ考え方で、4 進法ではなく 3 進法を使って構成されます。
• フィビナリ数（OEIS A003714）：0、1、2、4、5、8、9、10など。二進表記に1が2個連続して現れない数。

歴史

レオ・モーザー（1921-1970）は、整数論、組合せ論、幾何学を研究したオーストリア系カナダ人の数学者です。ニコラース・ホーフェルト・デ・ブライン（1918-2012）は、組合せ論、グラフ理論、計算機科学の研究で知られるオランダの数学者です。彼にちなんだデ・ブライン数列は、これとは無関係ですが、符号理論で広く使われています。二人はいずれも加法的基底を研究しました。加法的基底とは、4 のべきのように、表現可能なすべての数がただ一通りの和として表される整数の集合です。二人の名を冠するこの数列は、そのような基底の一例です。

よくある質問

モーザー・デ・ブライン数列は何に使われますか？

加法的整数論や組合せ論、特に和なし集合や加法的基底の研究で登場します。また、計算機科学では基数変換やビット演算の学習にも使われます。

モーザー・デ・ブライン数列はどのように生成しますか？

添字 n を二進法で書き、各二進数の数字を同じ位置の 4 進数の数字として読み取ります。n = 5（二進表記 101）の場合、4² + 4⁰ = 17 となります。

数が数列に含まれるかどうかを確認するにはどうすればよいですか？

その数を 4 進法に変換します。すべての数字が 0 または 1 なら、その数は数列に含まれます。2 または 3 が一つでもあれば、含まれません。

第 n 項の公式は何ですか？

M(n) = すべての i についての $b_i \cdot 4^i$ の総和。ここで $b_i$ は n の二進数の各桁です。

この数列は無限ですか？

はい。項は無限にありますが、n が大きくなるほど項どうしの間隔は広がります。

二進数とはどのように異なりますか？

二進数、つまり相異なる 2 のべきの和は、すべての非負整数を表せます。一方、モーザー・デ・ブライン数列は 4 のべきを使うため、ほとんどの整数は含まれません。