Eine Zahlenspirale

In den letzten Tagen habe ich mich mit der folgenden Frage auf StackExchange über eine Spirale aus Ganzzahlen beschäftigt. Dabei suchen wir eine geschlossene Formel für die Koordinaten des \(n\)-ten Elements in der folgenden Ganzzahl-Spirale, die sich vom Ursprung nach außen hin immer weiter ins Unendliche ausdehnt:

..  9 10 11 12
23  8  1  2 13
22  7  0  3 14
21  6  5  4 15
20 19 18 17 16

Zunächst teilen wir die natürlichen Zahlen in folgende Gruppen ein:

$$G_1 = \{ 1,...,8 \}\\G_2 = \{ 9, ..., 24 \}\\G_3 = \{ 25, ... 48 \}\\...\\G_k = \left\{ (2k-1)^2, (2k+1)^2 - 1 \right\}$$

Wir nennen

$$a^2 = \left(\left \lfloor \left( \frac{\left \lfloor \sqrt{n} \right \rfloor + 1}{2} \right) \right \rfloor \cdot 2 - 1 \right)^2$$

die Anfangszahl in einer Gruppe.

Innerhalb einer Gruppe gibt es jeweils vier gleich große Untergruppen (beispielsweise für \(G_1\) ist das \(g_1 = \{ 1,2 \}, g_2 = \{ 3,4 \}, g_3 = \{ 5,6 \}, g_4 = \{7,8\}\)). Wechselt \(n\) von einer Untergruppe zur nächsten, wird gleichzeitig auch die Richtung auf dem Weg der Spirale (in unserem Beispiel im Uhrzeigersinn) gewechselt. Wir erhalten die aktuelle Richtung \( b \in \{0,1,2,3\} \), indem wir die Position \(n-a^2\) innerhalb einer Gruppe durch die Anzahl der Elemente einer Untergruppe teilen:

$$b = \left \lfloor \frac{ n - a^2 }{ \text{abs}\left( a \right) + 1 } \right \rfloor$$

Nun können wir das erste Element innerhalb einer Untergruppe \(g_n\) bestimmen, indem wir zur Anfangszahl \(a^2\) ein Vielfaches \(b\) von der Anzahl \(a+1\) der Elemente innerhalb einer Gruppe hinzuaddieren:

$$c = a^2 + b \cdot (a+1)$$

Nun können wir durch einfache Beobachtung ermitteln:

$$x_{right} = \left(n - c - \frac{ a + 1 }{2}+1\right),\, y_{right} = \left(\frac{ a + 1 }{2}\right) \\ x_{bottom} = \left(\frac{ a + 1 }{2}\right),\, y_{bottom} = (-1) \cdot \left( n - c - \frac{ a + 1 }{2}+1\right) \\ x_{left} = (-1) \cdot \left(n - c - \frac{ a + 1 }{2}+1\right),\, y_{left} = (-1) \cdot \left(\frac{ a + 1 }{2}\right) \\ x_{top} = (-1) \cdot \left(\frac{ a + 1 }{2}\right),\, y_{top} = \left( n - c - \frac{ a + 1 }{2}+1\right)$$

Wie wollen \(f(n)\) nun in geschlossener Darstellung und auch ohne Fallunterscheidungen darstellen. Die verwenden wir Signumsfunktion, das Verfahren habe ich hier beschrieben. Damit wir eine reine Formel in Abhängigkeit von \(n\) bekommen, erhalten wir:

Dass das Ganze auch wirklich funktioniert, sehen wir mit Hilfe von SVG.js in dieser kleinen Visualisierung:

See the Pen ulam spiral by David Vielhuber (@vielhuber) on CodePen.

Die Spirale ist auch bekannt als Ulam's Spiral und hat einen spannenden Bezug zu Primzahlen.

Zurück