Moser-de Bruijn Sequenz Generator | Potenzen von 4 Rechner

Was ist die Moser-de-Bruijn-Folge?

Die Moser-de-Bruijn-Folge ist eine Liste ganzer Zahlen, die jeweils als Summe verschiedener Potenzen von 4 geschrieben werden können. Sie beginnt mit 0, 1, 4, 5, 16, 17, 20, 21, 64, 65, 68, 69, 80, 81, 84, 85 und setzt sich ohne Ende fort. Benannt ist sie nach den Mathematikern Leo Moser und Nicolaas Govert de Bruijn. In der Online Encyclopedia of Integer Sequences ist sie als A000695 katalogisiert.

Eine Zahl gehört genau dann zur Folge, wenn ihre Darstellung zur Basis 4 nur die Ziffern 0 und 1 verwendet, niemals 2 oder 3. Zum Beispiel wird 21 zur Basis 4 als 111 geschrieben und gehört daher zur Folge. Die Zahl 22 wird zur Basis 4 als 112 geschrieben und gehört daher nicht dazu.

Formel der Moser-de-Bruijn-Folge

Die Folge kann auf drei gleichwertige Arten definiert werden.

Summe verschiedener Potenzen von 4

Eine Zahl n gehört zur Folge, wenn sie geschrieben werden kann als

$n = \sum_{i \in S} 4^i$

für eine Menge S nichtnegativer ganzer Zahlen, wobei jede Potenz von 4 höchstens einmal verwendet wird.

Zifferntest zur Basis 4

Schreibe die Zahl zur Basis 4. Wenn jede Ziffer 0 oder 1 ist, gehört die Zahl zur Folge. Wenn eine Ziffer 2 oder 3 vorkommt, gehört sie nicht dazu.

Ersetzung von Binärziffern durch Ziffern zur Basis 4

Zählt man die Folgenglieder ab n = 0, lautet das Folgenglied am Index n

$M(n) = \sum_{i=0}^{k} b_i \cdot 4^i$

wobei die $b_i$ die Binärziffern von n sind. Anders gesagt: Schreibe n binär und lies dann jede Binärziffer an derselben Stelle als Ziffer zur Basis 4. Dies ist die Methode des Generators, da er nur Bits prüfen und Zahlen addieren muss.

So berechnet man das n-te Folgenglied

Um M(n) zu bestimmen, führt der Generator für jeden Index n, beginnend mit n = 0, Folgendes aus:

1. Betrachte die Binärdarstellung von n.
2. Addiere für jedes Bit mit dem Wert 1 an der Position j den Wert 4^j zu einer laufenden Summe.
3. Überspringe Bits mit dem Wert 0.
4. Die laufende Summe ist M(n).

Durchgerechnetes Beispiel: M(5)

• 5 ist binär 101.
• Das Bit 0 (ganz rechts) ist 1, also addiere 4⁰ = 1.
• Das Bit 1 ist 0, also wird nichts addiert.
• Das Bit 2 ist 1, also addiere 4² = 16.
• Summe: 1 + 16 = 17.

Somit gilt M(5) = 17. Es ist der sechste vom Generator erzeugte Wert, da die Zählung bei M(0) beginnt.

Beispiel: Die ersten 32 Folgenglieder

So prüft man, ob eine Zahl zur Folge gehört

Wandle die Zahl in die Basis 4 um und lies ihre Ziffern.

• 85: Zur Basis 4 ist 85 gleich 1111 (64 + 16 + 4 + 1). Es kommen nur 0en und 1en vor, daher gehört 85 zur Folge.
• 90: Zur Basis 4 ist 90 gleich 1122. Die Darstellung enthält eine 2, daher gehört 90 nicht zur Folge.

Wachstumsrate

Die Folge wächst schnell, weil jedes zusätzliche Bit im Index den von ihm hinzugefügten Wert ungefähr vervierfachen kann. M(19) ist 261. M(99) ist 5.125. M(999), das größte Folgenglied, das dieser Generator erzeugen kann, ist 349.205. Mit wachsendem Index liegen die Folgenglieder immer weiter auseinander. Dadurch ist die Folge dünn besetzt: Die meisten ganzen Zahlen kommen darin nie vor, obwohl sie unendlich viele Folgenglieder hat.

So verwendet man den Generator für die Moser-de-Bruijn-Folge

1. Gib die Anzahl der zu erzeugenden Folgenglieder ein. Wenn das Feld leer bleibt, ist der Standardwert 20.
2. Die Liste der Folgenglieder wird automatisch aktualisiert und beginnt mit M(0).
3. Kopiere die vollständige Liste mit der Schaltfläche „Ergebnis kopieren“.

Das Werkzeug akzeptiert ganze Zahlen von 1 bis 1000. Dezimalzahlen, negative Zahlen und nichtnumerische Eingaben werden abgelehnt. Die Anforderung von 20 Folgengliedern gibt M(0) bis M(19) zurück; der letzte angezeigte Wert ist 261. Alle Berechnungen erfolgen im Browser, daher werden die Ergebnisse sofort angezeigt und keine Daten an einen Server gesendet.

Verwandte Folgen

• Potenzen von 2 (OEIS A000079): 1, 2, 4, 8, 16, 32 und so weiter. Diese bilden die Bausteine gewöhnlicher Binärzahlen.
• Summen verschiedener Potenzen von 3 (OEIS A005836): 0, 1, 3, 4, 9, 10, 12, 13 und so weiter. Das ist dasselbe Prinzip wie bei der Moser-de-Bruijn-Folge, jedoch aus Potenzen zur Basis 3 statt zur Basis 4 aufgebaut.
• Fibbinary-Zahlen (OEIS A003714): 0, 1, 2, 4, 5, 8, 9, 10 und so weiter. Zahlen, deren Binärdarstellung keine zwei aufeinanderfolgenden 1en enthält.

Historie

Leo Moser (1921-1970) war ein österreichisch-kanadischer Mathematiker, der auf den Gebieten Zahlentheorie, Kombinatorik und Geometrie arbeitete. Nicolaas Govert de Bruijn (1918-2012) war ein niederländischer Mathematiker, der für seine Arbeiten in Kombinatorik, Graphentheorie und Informatik bekannt war; seine unabhängigen de-Bruijn-Folgen werden in der Codierungstheorie häufig verwendet. Beide beschäftigten sich mit additiven Basen: Mengen von ganzen Zahlen, etwa den Potenzen von 4, aus denen jede darstellbare Zahl genau eine Summendarstellung besitzt. Die nach ihnen benannte Folge ist ein Beispiel für eine solche Basis.

Häufig gestellte Fragen

Wofür wird die Moser-de-Bruijn-Folge verwendet?

Sie kommt in der additiven Zahlentheorie und der Kombinatorik vor, insbesondere bei der Untersuchung summentfreier Mengen und additiver Basen. Außerdem wird sie verwendet, um in der Informatik die Umwandlung von Zahlensystemen und bitweise Operationen zu vermitteln.

Wie erzeugt man die Moser-de-Bruijn-Folge?

Schreibe den Index n binär und lies dann jede Binärziffer an derselben Stelle als Ziffer zur Basis 4. Für n = 5 (binär 101) ergibt das 4² + 4⁰ = 17.

Wie kann man prüfen, ob eine Zahl zur Folge gehört?

Wandle sie in die Basis 4 um. Wenn jede Ziffer 0 oder 1 ist, gehört die Zahl zur Folge. Wenn eine Ziffer 2 oder 3 vorkommt, gehört sie nicht dazu.

Wie lautet die Formel für das n-te Folgenglied?

M(n) = die Summe über alle i von $b_i \cdot 4^i$, wobei die $b_i$ die Binärziffern von n sind.

Ist die Folge unendlich?

Ja. Sie hat unendlich viele Folgenglieder, die mit wachsendem n jedoch immer weiter auseinanderliegen.

Worin unterscheidet sie sich von der Binärdarstellung?

Die Binärdarstellung, also Summen verschiedener Potenzen von 2, kann jede nichtnegative ganze Zahl darstellen. Die Moser-de-Bruijn-Folge verwendet stattdessen Potenzen von 4, sodass die meisten ganzen Zahlen ausgelassen werden.