Complete sequence

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 2 = 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.

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 2 = 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. s_n=\sum_{m=0}^n a_m . Then the conditions a_0 = 1 \, s_{k-1} \ge a_k - 1 \text{ for all } k \ge 1 are both necessary and sufficient for a n to be a complete sequence. A corollary to the above states that a_0 = 1\, 2a_k \ge a_{k+1} \text{ for all } k \ge 0 are sufficient for a n to be a complete sequence. However there are complete sequences that do not satisfy this corollary, for example , consisting of the number 1 and the first prime after each power of 2. ===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 6 + F 5 + F 3 + F 2 + F 1 = 8 + 5 + 2 + 1 + 1 = 17, maximal form) 111001 (F 6 + F 5 + F 4 + F 1 = 8 + 5 + 3 + 1 = 17) 111010 (F 6 + F 5 + F 4 + F 2 = 8 + 5 + 3 + 1 = 17) 1000111 (F 7 + F 3 + F 2 + F 1 = 13 + 2 + 1 + 1 = 17) 1001001 (F 7 + F 4 + F 1 = 13 + 3 + 1 = 17) 1001010 (F 7 + F 4 + F 2 = 13 + 3 + 1 = 17, minimal form, as used in Fibonacci coding) The maximal form above will always use F 1 and will always have a trailing one. The full coding without the trailing one can be found at . By dropping the trailing one, the coding for 17 above occurs as the 16th term of A104326. The minimal form will never use F 1 and will always have a trailing zero. The full coding without the trailing zero can be found at . 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. 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. ==See also== Ostrowski numeration

Text derived from https://en.wikipedia.org/w/index.php?oldid=1340723569 under CC BY-SA 4.0; modifications have been made.