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 16Zunä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)$$
Wir wollen \(f(n)\) nun in geschlossener Darstellung und auch ohne Fallunterscheidungen darstellen. Dazu verwenden wir die 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.