莫泽-德布鲁因序列生成器 | 4的幂计算器
计算莫泽-德布鲁因数列，该数列中的每一项都是由若干个互不相同的4的幂次相加得到的整数，其对应的4进制表示中每一位数字只能是0或1，是数论中一种典型的无和自由集合。免费在线工具可根据需要生成任意项数的完整数列，适用于数论课程学习、组合数学研究和相关算法课堂教学演示。
莫泽-德布鲁因序列生成器
生成的序列
文档
什么是莫泽尔-德布鲁因序列？
莫泽尔-德布鲁因序列是一个整数列表，其中每个整数都可以表示为互不相同的 4 的幂之和。它从 0、1、4、5、16、17、20、21、64、65、68、69、80、81、84、85开始，并无限延续。它以数学家 Leo Moser 和 Nicolaas Govert de Bruijn 的名字命名。在《在线整数数列百科全书》中，该序列编为 A000695。
当且仅当一个数的 4 进制表示只使用数字 0 和 1，而从不使用 2 或 3 时，它才属于该序列。例如，21 的 4 进制表示是 111，因此它属于该序列。数 22 的 4 进制表示是 112，因此它不属于该序列。
莫泽尔-德布鲁因序列公式
该序列有三种等价的定义方式。
不同 4 的幂之和
如果一个数 n 可以表示为
对某个非负整数集合 S 而言，其中每个 4 的幂最多使用一次。
4 进制数字检验
将该数写成 4 进制。如果每一位都是 0 或 1，该数就属于此序列。如果有任何一位是 2 或 3，则不属于此序列。
二进制到 4 进制的替换
从 n = 0 开始对各项计数时，索引 n 处的项为
其中 是 n 的二进制数字。换言之，先将 n 写成二进制，然后将每个二进制数字在相同位置作为 4 进制数字读取。这就是生成器所采用的方法，因为它只需检查位并进行加法。
如何计算第 N 项
为了求出 M(n)，生成器从 n = 0 开始，对每个索引 n 执行以下操作：
- 查看 n 的二进制形式。
- 对于位置 j 上每个等于 1 的位，将 4^j 加到累计总数中。
- 跳过等于 0 的位。
- 累计总数就是 M(n)。
示例：M(5)
- 5 的二进制表示是 101。
- 位 0（最右位）是 1，因此加上 4⁰ = 1。
- 位 1 是 0，因此不加任何数。
- 位 2 是 1，因此加上 4² = 16。
- 总计：1 + 16 = 17。
因此，M(5) = 17。这是生成器产生的第六个值，因为计数从 M(0) 开始。
示例：前 32 项
| 索引 | 项 | 分解 | 4 进制 |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 1 | 1 | 4⁰ | 1 |
| 2 | 4 | 4¹ | 10 |
| 3 | 5 | 4¹ + 4⁰ | 11 |
| 4 | 16 | 4² | 100 |
| 5 | 17 | 4² + 4⁰ | 101 |
| 6 | 20 | 4² + 4¹ | 110 |
| 7 | 21 | 4² + 4¹ + 4⁰ | 111 |
| 8 | 64 | 4³ | 1000 |
| 9 | 65 | 4³ + 4⁰ | 1001 |
| 10 | 68 | 4³ + 4¹ | 1010 |
| 11 | 69 | 4³ + 4¹ + 4⁰ | 1011 |
| 12 | 80 | 4³ + 4² | 1100 |
| 13 | 81 | 4³ + 4² + 4⁰ | 1101 |
| 14 | 84 | 4³ + 4² + 4¹ | 1110 |
| 15 | 85 | 4³ + 4² + 4¹ + 4⁰ | 1111 |
| 16 | 256 | 4⁴ | 10000 |
| 17 | 257 | 4⁴ + 4⁰ | 10001 |
| 18 | 260 | 4⁴ + 4¹ | 10010 |
| 19 | 261 | 4⁴ + 4¹ + 4⁰ | 10011 |
| 20 | 272 | 4⁴ + 4² | 10100 |
| 21 | 273 | 4⁴ + 4² + 4⁰ | 10101 |
| 22 | 276 | 4⁴ + 4² + 4¹ | 10110 |
| 23 | 277 | 4⁴ + 4² + 4¹ + 4⁰ | 10111 |
| 24 | 320 | 4⁴ + 4³ | 11000 |
| 25 | 321 | 4⁴ + 4³ + 4⁰ | 11001 |
| 26 | 324 | 4⁴ + 4³ + 4¹ | 11010 |
| 27 | 325 | 4⁴ + 4³ + 4¹ + 4⁰ | 11011 |
| 28 | 336 | 4⁴ + 4³ + 4² | 11100 |
| 29 | 337 | 4⁴ + 4³ + 4² + 4⁰ | 11101 |
| 30 | 340 | 4⁴ + 4³ + 4² + 4¹ | 11110 |
| 31 | 341 | 4⁴ + 4³ + 4² + 4¹ + 4⁰ | 11111 |
如何检查一个数是否属于该序列
将该数转换为 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。随着索引增大，各项之间的间隔越来越大，因此该序列很稀疏：尽管它有无穷多项，但大多数整数不会出现在其中。
如何使用莫泽尔-德布鲁因序列生成器
- 输入要生成的项数。如果留空，该字段默认为 20。
- 项列表会自动更新，从 M(0) 开始。
- 点击“复制结果”按钮，复制完整列表。
该工具接受从 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，依此类推。其思想与莫泽尔-德布鲁因序列相同，但构造基础是 3 进制，而不是 4 进制。
- 斐波那契二进制数（OEIS A003714）：0、1、2、4、5、8、9、10，依此类推。其二进制形式中不含两个连续的 1。
历史
Leo Moser（1921-1970）是奥地利裔加拿大数学家，研究领域包括数论、组合学和几何学。Nicolaas Govert de Bruijn（1918-2012）是荷兰数学家，因在组合学、图论和计算机科学领域的研究而知名；与此无关的德布鲁因序列广泛用于编码理论。两人都研究过加性基：由整数构成的集合，例如 4 的幂，使每个可表示的数恰好有一种求和表示。以他们名字命名的序列就是这种基的一个例子。
常见问题
莫泽尔-德布鲁因序列有什么用途？
它出现在加性数论和组合学中，尤其用于研究无和集和加性基。它还用于计算机科学中教授进制转换和位运算。
如何生成莫泽尔-德布鲁因序列？
将索引 n 写成二进制，然后在相同位置将每个二进制数字作为 4 进制数字读取。对于 n = 5（二进制为 101），得到 4² + 4⁰ = 17。
如何检查一个数是否属于该序列？
将它转换为 4 进制。如果每一位都是 0 或 1，该数就属于该序列。如果有任何一位是 2 或 3，则不属于该序列。
第 n 项的公式是什么？
M(n) = 对所有 i 求 之和，其中 是 n 的二进制数字。
该序列是无限的吗？
是的。它有无穷多项，但随着 n 增大，各项之间的间隔也会越来越大。
这与二进制有什么不同？
二进制，即不同 2 的幂之和，可以表示每个非负整数。而莫泽尔-德布鲁因序列使用 4 的幂，因此大多数整数都不会出现。