Golomb-Folge

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

Die Golomb-Folge (nach dem Mathematiker Solomon W. Golomb, aber auch bekannt als Silverman-Folge)[1] ist eine sich selbst erzeugende Folge ganzer Zahlen, bei der die an n-ter Stelle stehende Zahl an angibt, wie oft n in der Folge vorkommt. Beispielsweise steht an fünfter Stelle (n=5) eine 3, also wird die 5 später 3-mal hinzugefügt.

Aufbau[Bearbeiten | Quelltext bearbeiten]

An erster Stelle steht die 1, die besagt, dass n=1 genau einmal vorkommt. Da diese Bedingung damit gleichzeitig erfüllt ist, kann keine weitere 1 auftauchen, und es folgt an zweiter Stelle (n=2) die 2. Daraus folgt, dass die 2 zweimal in der Folge vorkommt. Nach der bereits vorhandenen wird dementsprechend eine weitere 2 hinzugefügt, sodass an dritter Stelle (n=3) ebenfalls eine 2 steht. Das bedeutet, dass auch die 3 zweimal vorkommt. Somit lautet die Folge bis hierhin: 1,2,2,3,3. Da an vierter und an fünfter Stelle nun je eine 3 steht, werden genau 3 Vieren und 3 Fünfen hinzugefügt: 1,2,2,3,3,4,4,4,5,5,5. Damit erhält man die Stellen 6 bis 11 und kann an ihnen ablesen, wie viele Sechsen, Siebenen etc. die Folge fortsetzen.

Daraus ergibt sich für die ersten n: 1, 2, 2, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 6, 7, 7, 7, 7 (Folge A001462 in OEIS).

Formale Definition[Bearbeiten | Quelltext bearbeiten]

Als mathematische Beschreibung dieser Rekursion fand der Statistiker Colin Mallows für das jeweils nächste n die Differenzengleichung[1]

Oder in alternativer Schreibweise:


Beispiel

Wenn die ersten vier Stellen der Folge bekannt sind, gilt für die fünfte:


a5 = 3, also kommt die 5 dreimal vor.


Eine Annäherung an an für beliebige Werte von n kann man mit dem Goldenen Schnitt (≈ 1,618) berechnen:[2]


Beispiel


a57 ≈ 15, d. h., laut Annäherungsformel ist die 57 in der Folge 15-mal vorhanden (tatsächlicher Wert: 15).[3]

Siehe auch[Bearbeiten | Quelltext bearbeiten]

Einzelnachweise[Bearbeiten | Quelltext bearbeiten]

  1. a b OEIS: Golomb's sequence. Abgerufen am 16. März 2014.
  2. B. Cloitre, N. J. A. Sloane, M. J. Vandermast: Numerical Analogues of Aronson’s Sequence auf arXiv.org. Abgerufen am 16. März 2014.
  3. OEIS: Golomb's sequence: Table of n, a(n) for n = 1..10000. Abgerufen am 16. März 2014.