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]

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]

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

a_{n+1} = 1 + a_{n+1-a_{a_n}} (\text{für } n > 1; a_1 = 1)

Oder in alternativer Schreibweise:

a(n+1) = 1 + a(n+1-a(a(n)))


Beispiel

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

a_5 = a_{4 + 1} = 1 + a_{4 + 1 - a_{a_4}} = 1 + a_{5 - a_3} = 1 + a_{5 - 2} = 1 + a_3 = 1 + 2 = 3


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 \Phi (≈ 1,618) berechnen:[2]

a_n \approx \Phi^{2-\Phi} \cdot n^{\Phi-1}


Beispiel

a_{57} \approx \Phi^{2-\Phi} \cdot {57}^{\Phi-1} \approx 14{,}6223278 \approx 15


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

Siehe auch[Bearbeiten]

Einzelnachweise[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.