完整數列

数学裡，完整數列（complete sequence）是指一自然数的數列，所有整數都可以用此數列中部份數字的和表示，而且每一項最多只出現一次^[1]。

例如，2的幂（1, 2, 4, 8, ...）組成的數列，就是完整數列。給定任意自然數，可以依二进制表示，每一位數對應2的不同乘幂，根據數字為1的位數，找到其2的乘幂，相加後，即為原自然數（例如，37 = 100101₂ = 1 + 4 + 32）。此完整數列中任何一個數字都是必要的，不能移除。若移除了任何一個，就會有些自然數無法組成。有些完整數列沒有此特性，數列中少了一個數字，仍然可以表示所有的自然數。

常見許多自然數數列不是完整數列，例如只由偶數組成的數列就不是完整數列，因為任意數個偶數的和只會是偶數，無法用這些數字相加，得到奇數。

完整數列的條件

為了簡化推導，在不失一般性的前提下，假設數列a_n是非遞減數列，定義a_n的部份和為：

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

則以下條件

${\displaystyle a_{0}=1\,}$

${\displaystyle s_{k-1}\geq a_{k}-1}$，針對所有${\displaystyle k\geq 1}$

是a_n為完整數列的充份必要條件^[2][1]。

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

${\displaystyle a_{0}=1\,}$

${\displaystyle 2a_{k}\geq a_{k+1}}$，針對所有${\displaystyle k\geq 0}$

是a_n是完整數列的充份條件^[2]。

不過，有些完整數列不符合上述推理出的答案。像是包括1，以及針對每一個2的乘幂，大於乘幂的最小質數所組成的數列1, 2, 3, 5, 11......（OEIS數列A203074），是完整數列，但不符合充份條件。

其他完整數列

完整數列包括：

• 1和所有质数組成的數列（是由印度數學家蘇巴亞‧席瓦桑卡拉納拉亞納‧皮萊（英语：Subbayya Sivasankaranarayana Pillai）^[3]等人所證明），這是伯特蘭-切比雪夫定理的結果^[2]。
• 實際數，1是第一項，所有2的乘幂均在實際數內^[4] （OEIS數列A005153）。
• 斐波那契数列，以及移去任何一項後的斐波那契数列^[2]。這是因為前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。

像斐波那契编码就是用斐波那契数的和表達正整數，而且其表示方式裡，不會出現連續的斐波那契数（齊肯多夫定理）。

相關條目

• 奧斯特羅夫斯基計數法（英语：Ostrowski numeration）