In mathematics, a sequence of natural numbers is called a complete sequence if every positive integer can be expressed as a sum of values in the sequence, using each value at most once.

For example, the sequence of powers of two (1, 2, 4, 8, ...), the basis of the binary numeral system, is a complete sequence; given any natural number, we can choose the values corresponding to the 1 bits in its binary representation and sum them to obtain that number (e.g. 37 = 100101₂ = 1 + 4 + 32). This sequence is minimal, since no value can be removed from it without making some natural numbers impossible to represent. Simple examples of sequences that are not complete include the even numbers, since adding even numbers produces only even numbers—no odd number can be formed.

Conditions for completeness

Without loss of generality, assume the sequence a_n is in non-decreasing order, and define the partial sums of a_n as:

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

Then the conditions

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

${\displaystyle s_{k-1}\geq a_{k}-1{\text{ for all }}k\geq 1}$

are both necessary and sufficient for a_n to be a complete sequence.^[1][2]

A corollary to the above states that

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

${\displaystyle 2a_{k}\geq a_{k+1}{\text{ for all }}k\geq 0}$

are sufficient for a_n to be a complete sequence.^[1]

However there are complete sequences that do not satisfy this corollary, for example (sequence A203074 in the OEIS), consisting of the number 1 and the first prime after each power of 2.

Other complete sequences

The complete sequences include:

• The sequence of the number 1 followed by the prime numbers (studied by S. S. Pillai^[3] and others); this follows from Bertrand's postulate.^[1]
• The sequence of practical numbers which has 1 as the first term and contains all other powers of 2 as a subset.^[4] (sequence A005153 in the OEIS)
• The Fibonacci numbers, as well as the Fibonacci numbers with any one number removed.^[1] This follows from the identity that the sum of the first n Fibonacci numbers is the (n + 2)nd Fibonacci number minus 1.

Applications

Just as the powers of two form a complete sequence due to the binary numeral system, in fact any complete sequence can be used to encode integers as bit strings. The rightmost bit position is assigned to the first, smallest member of the sequence; the next rightmost to the next member; and so on. Bits set to 1 are included in the sum. These representations may not be unique.

See also

• Ostrowski numeration

References

External links

• Weisstein, Eric W. "Complete Sequence". MathWorld.