词条 | 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 = 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:
Conditions for completenessWithout loss of generality, assume the sequence an is in non-decreasing order, and define the partial sums of an as: . Then the conditions are both necessary and sufficient for an to be a complete sequence.[1][2] A corollary to the above states that are sufficient for an to be a complete sequence.[1] However there are complete sequences that do not satisfy this corollary, {{Anchor|OEIS A203074}} for example {{OEIS|A203074}}, consisting of the number 1 and the first prime after each power of 2. Other complete sequencesBelow is a list of the better-known complete sequences.
ApplicationsJust 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 codingFor 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) 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 {{OEIS|id=A104326}}. 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 F1 and will always have a trailing zero. The full coding without the trailing zero can be found at {{OEIS|id=A014417}}. 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.[7] 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 systemsOther 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.
{{OEIS|id=A007924}}.
{{OEIS|id=A205598}}.
{{OEIS|id=A204009}}. See also
References1. ^1 2 3 Honsberger, R. Mathematical Gems III. Washington, DC: Math. Assoc. Amer., 1985, pp.123-128. 2. ^{{Cite journal|last=Brown|first=J. L.|date=1961|title=Note on Complete Sequences of Integers|journal=The American Mathematical Monthly|volume=68|issue=6|pages=557–560|doi=10.2307/2311150|jstor=2311150}} 3. ^S. S. Pillai, "An arithmetical function concerning primes", Annamalai University Journal (1930), pp. 159–167. 4. ^{{Citation|last = Srinivasan |first = A. K.|title = Practical numbers|journal = Current Science|volume = 17|year = 1948|pages = 179–180|mr = 0027799|url = http://www.currentscience.ac.in/Downloads/article_id_017_06_0179_0180_0.pdf}}. 5. ^{{Mathworld|title=Fibonacci n-Step Number|urlname=Fibonaccin-StepNumber}} 6. ^{{Mathworld|title=Plane Division by Circles|urlname=PlaneDivisionbyCircles}} 7. ^Stakhov, Alexey. {{cite web |url=http://www.goldenmuseum.com/1202FibCdeTransf_engl.html |archive-url=https://archive.is/20130124230213/http://www.goldenmuseum.com/1202FibCdeTransf_engl.html |archive-date=January 24, 2013 |title=The main operations of the Fibonacci arithmetic |dead-url=yes |access-date=September 11, 2016}}, Museum of Harmony and Golden Section. Originally accessed: 27 July 2010. External links
1 : Integer sequences |
随便看 |
|
开放百科全书收录14589846条英语、德语、日语等多语种百科知识,基本涵盖了大多数领域的百科知识,是一部内容自由、开放的电子版国际百科全书。