完整数列

数学里，完整数列（complete sequence）是指一自然数的数列，所有整数都可以用此数列中部分数字的和表示，而且每一项最多只出现一次。

例如，2的幂（1, 2, 4, 8, ...）组成的数列，就是完整数列。给定任意自然数，可以依二进制表示，每一位数对应2的不同乘幂，根据数字为1的位数，找到其2的乘幂，相加后，即为原自然数（例如，37 = 100101₂ = 1 + 4 + 32）。此完整数列中任何一个数字都是必要的，不能移除。若移除了任何一个，就会有些自然数无法组成。有些完整数列没有此特性，数列中少了一个数字，仍然可以表示所有的自然数。

常见许多自然数数列不是完整数列，例如只由偶数组成的数列就不是完整数列，因为任意数个偶数的和只会是偶数，无法用这些数字相加，得到奇数。

完整数列的条件

为了简化推导，在不失一般性的前提下，假设数列a_n是非递减数列，定义a_n的部分和为：

$s_{n}=\sum _{m=0}^{n}a_{m}$.

则以下条件

$a_{0}=1\,$

$s_{k-1}\geq a_{k}-1$，针对所有$k\geq 1$

是a_n为完整数列的充份必要条件。

以上述条件可以推理出，以下条件

$a_{0}=1\,$

$2a_{k}\geq a_{k+1}$，针对所有$k\geq 0$

是a_n是完整数列的充份条件。

不过，有些完整数列不符合上述推理出的答案。像是包括1，以及针对每一个2的乘幂，大于乘幂的最小质数所组成的数列1, 2, 3, 5, 11......（OEIS数列A203074），是完整数列，但不符合充份条件。

其他完整数列

完整数列包括：

• 1和所有质数组成的数列（是由印度数学家苏巴亚‧席瓦桑卡拉纳拉亚纳‧皮莱等人所证明），这是伯特兰-切比雪夫定理的结果。
• 实际数，1是第一项，所有2的乘幂均在实际数内 （OEIS数列A005153）。
• 斐波那契数列，以及移去任何一项后的斐波那契数列。这是因为前n个斐波那契数的部分和等于第n + 2个斐波那契数减1。

应用

依照2进制，2的幂可以组成完整数列。也可以用任何一个完整数列，将所有自然数编码成以0和1组合的字串。字串最右边的数字代表数列的第一项，接着是第二项……。数字为1的表示部分和中需考虑该项。

例如考虑1和所有质数组成的数列，以此为8编码，8可以表示为3和5的和，3和5分别是第2个质数和第3个质数，是数列的第3项和第4项，因此8的编码为0011。

此表示方式可能不唯一。像8也可以表示为1和7的和，7是第4个质数，数列的第5项，因此12的编码也可以是10001。

像斐波那契编码就是用斐波那契数的和表达正整数，而且其表示方式里，不会出现连续的斐波那契数（齐肯多夫定理）。

相关条目

• 奥斯特罗夫斯基计数法

外部链接

• 埃里克·韦斯坦因. Complete Sequence. MathWorld.