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

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.

 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). 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.^[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.

See also

• Ostrowski numeration

References