Golomb-Folge

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 ${\displaystyle n}$ -ter Stelle stehende Zahl ${\displaystyle a_{n}}$ angibt, wie oft ${\displaystyle n}$ in der Folge vorkommt. Beispielsweise steht an fünfter Stelle ${\displaystyle (n=5)}$ eine 3, also wird die 5 später 3-mal hinzugefügt.

Aufbau

An erster Stelle steht die 1, die besagt, dass ${\displaystyle n=1}$ genau einmal vorkommt. Da diese Bedingung damit gleichzeitig erfüllt ist, kann keine weitere 1 auftauchen, und es folgt an zweiter Stelle (${\displaystyle 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 (${\displaystyle 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 ${\displaystyle 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

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

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

Oder i​n alternativer Schreibweise:

${\displaystyle a(n+1)=1+a(n+1-a(a(n)))}$

Beispiel

Wenn d​ie ersten v​ier Stellen d​er Folge bekannt sind, g​ilt für d​ie fünfte:

${\displaystyle 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}$

${\displaystyle a_{5}=3}$ , also kommt die 5 dreimal vor.

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

${\displaystyle a_{n}\approx \Phi ^{2-\Phi }\cdot n^{\Phi -1}}$

Beispiel

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

${\displaystyle a_{57}\approx 15}$ , d. h., laut Annäherungsformel ist die 57 in der Folge 15-mal vorhanden (tatsächlicher Wert: 15).[3]

Siehe auch

• Fibonacci-Folge
• Conway-Folge

Einzelnachweise

1. 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.