# Complete sequence

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Complete_sequence
> Markdown URL: https://mediated.wiki/source/Complete_sequence.md
> Source: https://en.wikipedia.org/wiki/Complete_sequence
> Source revision: 1340723569
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

Sequence of natural numbers

In [mathematics](/source/Mathematics), a [sequence](/source/Sequence) of [natural numbers](/source/Natural_number) is called a **complete sequence** if every positive [integer](/source/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](/source/Powers_of_two) (1, 2, 4, 8, ...), the basis of the [binary numeral system](/source/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 = 1001012 = 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](/source/Even_and_odd_numbers), since adding even numbers produces only even numbers—no [odd number](/source/Even_and_odd_numbers) 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:

- s n = ∑ m = 0 n a m {\displaystyle s_{n}=\sum _{m=0}^{n}a_{m}} .

Then the conditions

- a 0 = 1 {\displaystyle a_{0}=1\,}

- s k − 1 ≥ a k − 1 for all k ≥ 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

- a 0 = 1 {\displaystyle a_{0}=1\,}

- 2 a k ≥ a k + 1 for all k ≥ 0 {\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](https://oeis.org/A203074) in the [OEIS](/source/On-Line_Encyclopedia_of_Integer_Sequences)), consisting of the number 1 and the first [prime](/source/Prime_number) after each power of 2.

## Other complete sequences

The complete sequences include:

- The sequence of the number 1 followed by the [prime numbers](/source/Prime_number) (studied by [S. S. Pillai](/source/Subbayya_Sivasankaranarayana_Pillai)[3] and others); this follows from [Bertrand's postulate](/source/Bertrand's_postulate).[1]

- The sequence of [practical numbers](/source/Practical_number) which has 1 as the first term and contains all other powers of 2 as a subset.[4] (sequence [A005153](https://oeis.org/A005153) in the [OEIS](/source/On-Line_Encyclopedia_of_Integer_Sequences))

- The [Fibonacci numbers](/source/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 ) t h {\displaystyle (n+2)th} 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.

### 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 (F6 + F5 + F3 + F2 + F1 = 8 + 5 + 2 + 1 + 1 = 17, maximal form)

- 111001 (F6 + F5 + F4 + F1 = 8 + 5 + 3 + 1 = 17)

- 111010 (F6 + F5 + F4 + F2 = 8 + 5 + 3 + 1 = 17)

- 1000111 (F7 + F3 + F2 + F1 = 13 + 2 + 1 + 1 = 17)

- 1001001 (F7 + F4 + F1 = 13 + 3 + 1 = 17)

- 1001010 (F7 + F4 + F2 = 13 + 3 + 1 = 17, minimal form, as used in [Fibonacci coding](/source/Fibonacci_coding))

The maximal form above will always use F1 and will always have a trailing one. The full coding without the trailing one can be found at (sequence [A104326](https://oeis.org/A104326) in the [OEIS](/source/On-Line_Encyclopedia_of_Integer_Sequences)). By dropping the trailing one, the coding for 17 above occurs as the 16th term of A104326. The minimal form will never use F1 and will always have a trailing zero. The full coding without the trailing zero can be found at (sequence [A014417](https://oeis.org/A014417) in the [OEIS](/source/On-Line_Encyclopedia_of_Integer_Sequences)). This coding is known as the [Zeckendorf representation](/source/Zeckendorf's_theorem).

In this numeral system, any substring "100" can be replaced by "011" and vice versa due to the definition of the Fibonacci numbers.[5] 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](/source/Mathematical_induction).

## See also

- [Ostrowski numeration](/source/Ostrowski_numeration)

## References

1. ^ [***a***](#cite_ref-Honsberger_1-0) [***b***](#cite_ref-Honsberger_1-1) [***c***](#cite_ref-Honsberger_1-2) [***d***](#cite_ref-Honsberger_1-3) Honsberger, R. Mathematical Gems III. Washington, DC: Math. Assoc. Amer., 1985, pp.123-128.

1. **[^](#cite_ref-2)** Brown, J. L. (1961). "Note on Complete Sequences of Integers". *The American Mathematical Monthly*. **68** (6): 557–560. [doi](/source/Doi_(identifier)):[10.2307/2311150](https://doi.org/10.2307%2F2311150). [JSTOR](/source/JSTOR_(identifier)) [2311150](https://www.jstor.org/stable/2311150).

1. **[^](#cite_ref-3)** S. S. Pillai, "An arithmetical function concerning primes", Annamalai University Journal (1930), pp. 159–167.

1. **[^](#cite_ref-4)** Srinivasan, A. K. (1948), ["Practical numbers"](http://www.currentscience.ac.in/Downloads/article_id_017_06_0179_0180_0.pdf) (PDF), *[Current Science](/source/Current_Science)*, **17**: 179–180, [MR](/source/MR_(identifier)) [0027799](https://mathscinet.ams.org/mathscinet-getitem?mr=0027799).

1. **[^](#cite_ref-Stakhov_5-0)** Stakhov, Alexey. ["The main operations of the Fibonacci arithmetic"](http://www.goldenmuseum.com/1202FibCdeTransf_engl.html). Retrieved September 11, 2016.{{[cite web](https://en.wikipedia.org/wiki/Template:Cite_web)}}: CS1 maint: deprecated archival service ([link](https://en.wikipedia.org/wiki/Category:CS1_maint:_deprecated_archival_service)), *Museum of Harmony and Golden Section*. Originally accessed: 27 July 2010.

## External links

- [Weisstein, Eric W.](/source/Eric_W._Weisstein) ["Complete Sequence"](https://mathworld.wolfram.com/CompleteSequence.html). *[MathWorld](/source/MathWorld)*.

v t e Sequences and series List of mathematical series Integer sequences Basic Arithmetic progression Geometric progression Harmonic progression Square number Cubic number Factorial Powers of two Powers of three Powers of 10 Advanced (list) Complete sequence Fibonacci sequence Figurate number Heptagonal number Hexagonal number Lucas number Pell number Pentagonal number Polygonal number Triangular number array Properties of sequences Cauchy sequence Monotonic function Periodic sequence Properties of series Series Alternating Convergent Divergent Telescoping Convergence Absolute Conditional Uniform 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/2s + 1/3s + ... (Riemann zeta function) Arithmetico-geometric Binomial Divergent 1 + 1 + 1 + 1 + ⋯ 1 − 1 + 1 − 1 + ⋯ (Grandi's series) 1 + 2 + 3 + 4 + ⋯ 1 − 2 + 3 − 4 + ⋯ 1 + 2 + 4 + 8 + ⋯ 1 − 2 + 4 − 8 + ⋯ Infinite arithmetic series 1 − 1 + 2 − 6 + 24 − 120 + ⋯ (alternating factorials) 1 + 1/2 + 1/3 + 1/4 + ⋯ (harmonic series) 1/2 + 1/3 + 1/5 + 1/7 + 1/11 + ⋯ (inverses of primes) Kinds of series Geometric Taylor series Power series Formal power series Laurent series Puiseux series Dirichlet series Trigonometric series Fourier series Generating series Tests of convergence Abel's Alternating series Cauchy condensation Direct comparison Dirichlet's Integral Limit comparison Ratio Root Term Hypergeometric series Generalized hypergeometric series Hypergeometric function of a matrix argument Lauricella hypergeometric series Modular hypergeometric series Riemann's differential equation Theta hypergeometric series Category

---
Adapted from the Wikipedia article [Complete sequence](https://en.wikipedia.org/wiki/Complete_sequence) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Complete_sequence?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.