Complete sequence

In mathematics, an integer sequence 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.
• Powers of three; no integer having a digit "2" in its ternary representation (2, 5, 6...) can be formed.

Conditions for completeness

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

.

Then the conditions

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

A corollary to the above states that

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

Below is a list of the better-known complete sequences.

• The sequence of the number 1 followed by the prime numbers (studied by S. S. Pillai^[2] 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.^[3] (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 (see Fibonacci_numbers#Second_identity).
• All Fibonacci n-Step numbers,^[4] where n=2 gives the Fibonacci numbers above, n=3 gives the Tribonacci numbers etc.
• The Lazy caterer's sequence that gives the maximum number of partitions that a plane can be divided into, using n straight lines as dividers.
• All higher dimensions of the Lazy caterer's sequence that uses n hyperplanes (of dimension d-1) to maximally divide a space (of dimension d). (sequence A216274 in the OEIS)
• The Cookie cutter's sequence that gives the maximum number of partitions that a plane can be divided into, using n circles as dividers.^[5]
• All higher dimensions of the Cookie cutter's sequence that uses n hyperspherical surfaces (of dimension d-1) to maximally divide a space (of dimension d). (sequence A059250 in the OEIS)
• The ordered set of proper divisors of every practical number (that includes 1 and itself) forms a complete sub-sequence.

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.

Fibonacci coding

For example, in the Fibonacci arithmetic system, based on the Fibonacci sequence, the number 17 can be encoded in six different ways:

 110111 (F₆ + F₅ + F₃ + F₂ + F₁ = 8 + 5 + 2 + 1 + 1 = 17, maximal form)

 111001 (F₆ + F₅ + F₄ + F₁ = 8 + 5 + 3 + 1 = 17)

 111010 (F₆ + F₅ + F₄ + F₂ = 8 + 5 + 3 + 1 = 17)

1000111 (F₇ + F₃ + F₂ + F₁ = 13 + 2 + 1 + 1 = 17)

1001001 (F₇ + F₄ + F₁ = 13 + 3 + 1 = 17)

1001010 (F₇ + F₄ + F₂ = 13 + 3 + 1 = 17, minimal form, as used in Fibonacci coding)

The maximal form above will always use F₁ and will always have a trailing one. The full coding without the trailing one can be found at

(sequence A104326 in the OEIS). Note that by dropping the trailing one, the coding for 17 above occurs as the 16th term of A104326.

The minimal form will never use F₁ and will always have a trailing zero. The full coding without the trailing zero can be found at

(sequence A014417 in the OEIS). This coding is known as the Zeckendorf representation .

In this numeral system, any substring "100" can be replaced by "011" and vice versa due to the definition of the Fibonacci numbers.^[6] Continual application of these rules will translate form the maximal to the minimal, and vice versa. The fact that any number (greater than 1) can be represented with a terminal 0 means that it is always possible to add 1, and given that, for 1 and 2 can be represented in Fibonacci coding, completeness follows by induction.

Other coding systems

Other coding systems can be similarly devised. As with the Fibonacci sequence above, these coding systems that employ complete sequences will need to deal with multiple encoding solutions. The two main methods used are the greedy algorithm that will attempt to minimize the number of terms needed to encode an integer from the complete sequence and a minimizing algorithm that will attempt to maximize the number of terms needed to encode the same integer.

• A coding for the sequence of the number 1 followed by the prime numbers using the greedy algorithm can be found at

(sequence A007924 in the OEIS).

• A coding for the sequence of the number 1 followed by the prime numbers using a minimizing algorithm can be found at

(sequence A205598 in the OEIS).

• A coding for the Lazy caterer's sequence using the greedy algorithm can be found at

(sequence A204009 in the OEIS).

See also

• Ostrowski numeration

References

1. 1 2 3 4 Honsberger, R. Mathematical Gems III. Washington, DC: Math. Assoc. Amer., 1985, pp.123-128.
2. ↑ S. S. Pillai, "An arithmetical function concerning primes", Annamalai University Journal (1930), pp. 159–167.
3. ↑ Srinivasan, A. K. (1948), "Practical numbers" (PDF), Current Science, 17: 179–180, MR 0027799 .
4. ↑ Weisstein, Eric W. "Fibonacci n-Step Number". MathWorld. 
5. ↑ Weisstein, Eric W. "Plane Division by Circles". MathWorld. 
6. ↑ Stakhov, Alexey. ""The main operations of the Fibonacci arithmetic"". Retrieved September 11, 2016. , Museum of Harmony and Golden Section. Originally accessed: 27 July 2010.

External links

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

Sequences and series
Integer sequences	Basic Arithmetic progression Geometric progression Square number Cubic number Factorial Powers of two Powers of 10 Advanced Complete sequence Fibonacci numbers Figurate number Heptagonal number Hexagonal number Lucas number Pell number Pentagonal number Polygonal number Triangular number others
Properties of sequences	Cauchy sequence Monotone sequence Periodic sequence
Properties of series	Convergent series Divergent series Conditional convergence Absolute convergence Uniform convergence Alternating series Telescoping series
Explicit series	Convergent 1/2 − 1/4 + 1/8 − 1/16 + ⋯ 1/2 + 1/4 + 1/8 + 1/16 + ⋯ 1/4 + 1/16 + 1/64 + 1/256 + ⋯ 1 + 1/1s + 1/2s+ 1/3s + ... (Riemann zeta function) Divergent 1 + 1 + 1 + 1 + ⋯ 1 + 2 + 3 + 4 + ⋯ 1 + 2 + 4 + 8 + ⋯ 1 − 1 + 1 − 1 + ⋯ (Grandi's series) Infinite arithmetic series 1 − 2 + 3 − 4 + ⋯ 1 − 2 + 4 − 8 + ⋯ 1 + 1/2 + 1/3 + 1/4 + ⋯ (harmonic series) 1 − 1 + 2 − 6 + 24 − 120 + ⋯ (alternating factorials) 1/2 + 1/3 + 1/5 + 1/7 + 1/11 + ⋯ (inverses of primes)
Kinds of series	Taylor series Power series Formal power series Laurent series Puiseux series Dirichlet series Trigonometric series Fourier series Generating series
Hypergeometric series	Generalized hypergeometric series Hypergeometric function of a matrix argument Lauricella hypergeometric series Modular hypergeometric series Riemann's differential equation Theta hypergeometric series