Komplette Sequenz - Complete sequence

In der Mathematik ist eine Folge der natürlichen Zahlen ist eine sogenannte vollständige Sequenz , wenn jede positive ganze Zahl als eine Summe von Werten in der Folge ausgedrückt werden, wobei jeden Wert höchstens einmal verwendet.

Zum Beispiel ist die Folge von Zweierpotenzen (1, 2, 4, 8, ...), die Grundlage des binären Zahlensystems , eine vollständige Folge; Bei jeder natürlichen Zahl können wir die Werte auswählen, die den 1 Bits in ihrer Binärdarstellung entsprechen, und sie summieren, um diese Zahl zu erhalten (z. B. 37 = 100101 ₂ = 1 + 4 + 32). Diese Sequenz ist minimal, da kein Wert daraus entfernt werden kann, ohne dass einige natürliche Zahlen nicht dargestellt werden können. Einfache Beispiele für Sequenzen, die nicht vollständig sind, umfassen die geraden Zahlen , da das Hinzufügen von geraden Zahlen nur gerade Zahlen ergibt - es kann keine ungerade Zahl gebildet werden.

Bedingungen für die Vollständigkeit

Nehmen Sie ohne Verlust der Allgemeinheit an, dass die Folge a _n in nicht abnehmender Reihenfolge vorliegt, und definieren Sie die Teilsummen von a _n wie folgt :

${\ displaystyle s_ {n} = \ sum _ {m = 0} ^ {n} a_ {m}}$.

Dann die Bedingungen

${\ displaystyle a_ {0} = 1 \,}$

${\ displaystyle s_ {k-1} \ geq a_ {k} -1 {\ text {für alle}} k \ geq 1}$

sind sowohl notwendig als auch ausreichend, damit ein _n eine vollständige Sequenz ist.

Eine Folgerung aus dem oben Gesagten besagt, dass

${\ displaystyle a_ {0} = 1 \,}$

${\ displaystyle 2a_ {k} \ geq a_ {k + 1} {\ text {für alle}} k \ geq 1}$

sind ausreichend, damit ein _n eine vollständige Sequenz ist.

Es gibt jedoch vollständige Sequenzen, die diese Folgerung nicht erfüllen. Zum Beispiel (Sequenz A203074 im OEIS ), bestehend aus der Nummer 1 und der ersten Primzahl nach jeder Potenz von 2.

Andere vollständige Sequenzen

Die vollständigen Sequenzen umfassen:

• Die Reihenfolge der Zahl 1, gefolgt von den Primzahlen (untersucht von SS Pillai und anderen); dies folgt aus Bertrands Postulat .
• Die Folge von praktischen Zahlen, die 1 als ersten Term hat und alle anderen Potenzen von 2 als Teilmenge enthält. (Sequenz A005153 im OEIS )
• Die Fibonacci-Zahlen sowie die Fibonacci-Zahlen, bei denen eine Zahl entfernt wurde. Dies folgt aus der Identität, dass die Summe der ersten n Fibonacci-Zahlen die ( n  + 2) -te Fibonacci-Zahl minus 1 ist (siehe Fibonacci_numbers # Second_identity ).

Anwendungen

So wie die Zweierpotenzen aufgrund des binären Zahlensystems eine vollständige Sequenz bilden, kann tatsächlich jede vollständige Sequenz verwendet werden, um Ganzzahlen als Bitfolgen zu codieren. Die Bitposition ganz rechts wird dem ersten, kleinsten Mitglied der Sequenz zugewiesen. das nächste ganz rechts zum nächsten Mitglied; und so weiter. Auf 1 gesetzte Bits sind in der Summe enthalten. Diese Darstellungen sind möglicherweise nicht eindeutig.

Fibonacci-Codierung

Beispielsweise kann im Fibonacci-Arithmetiksystem , das auf der Fibonacci-Sequenz basiert, die Zahl 17 auf sechs verschiedene Arten codiert werden:

 110111 (F ₆ + F ₅ + F ₃ + F ₂ + F ₁ = 8 + 5 + 2 + 1 + 1 = 17, maximale 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, minimale Form, wie in der Fibonacci-Codierung verwendet )

Die obige Maximalform verwendet immer F ₁ und hat immer eine nachfolgende. Die vollständige Codierung ohne die nachfolgende finden Sie unter (Sequenz A104326 im OEIS ). Durch Löschen des nachfolgenden wird die Codierung für 17 oben als 16. Term von A104326 ausgeführt. Die Minimalform verwendet niemals F ₁ und hat immer eine nachgestellte Null. Die vollständige Codierung ohne die nachfolgende Null finden Sie unter (Sequenz A014417 im OEIS ). Diese Kodierung ist als Zeckendorf-Darstellung bekannt .

In diesem Zahlensystem kann jeder Teilstring "100" aufgrund der Definition der Fibonacci-Zahlen durch "011" ersetzt werden und umgekehrt. Die fortlaufende Anwendung dieser Regeln übersetzt vom Maximum zum Minimal und umgekehrt. Die Tatsache, dass jede Zahl (größer als 1) mit einem Terminal 0 dargestellt werden kann, bedeutet, dass es immer möglich ist, 1 zu addieren, und vorausgesetzt, dass für 1 und 2 in der Fibonacci-Codierung dargestellt werden kann, folgt die Vollständigkeit durch Induktion .

Siehe auch

• Ostrowski-Nummerierung

Verweise

Externe Links

• Weisstein, Eric W. "Komplette Sequenz" . MathWorld .