完整數列

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

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

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

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

.

則以下條件

，針對所有

是an為完整數列的充份必要條件Honsberger, R. Mathematical Gems III. Washington, DC: Math. Assoc. Amer., 1985, pp.123-128.。

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

，針對所有

是an是完整數列的充份條件。

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

 其他完整數列 
完整數列包括：
 1和所有质数組成的數列（是由印度數學家S. S. Pillai, "An arithmetical function concerning primes", Annamalai University Journal (1930), pp. 159–167.等人所證明），這是伯特蘭-切比雪夫定理的結果。
 實際數，1是第一項，所有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。

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

相關條目


參考資料

外部連結



Category:整数数列