Golomb-Folge

Die Golomb-Folge (nach dem Mathematiker Solomon W. Golomb, aber auch bekannt als Silverman-Folge) ist eine sich selbst erzeugende Folge ganzer Zahlen, bei der die an $n$-ter Stelle stehende Zahl $a_{n}$ 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

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

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

$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$

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

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

$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$

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

Siehe auch

• Fibonacci-Folge
• Conway-Folge