The spiral starts with \(1\) at the center and writes the positive integers in a clockwise square pattern. For an odd side length \(N\), the goal is to compute the sum of the entries on the two diagonals of the resulting \(N \times N\) spiral without constructing the entire grid.
In the \(5 \times 5\) case, the diagonal entries are \(1,3,5,7,9,13,17,21,25\), so the total is \(101\). The same idea works for every positive odd \(N\), including the target size \(1001\).
The key observation is that when the spiral grows from one odd square size to the next, the diagonals gain only four new values: the four corners of the new outer ring. Every other value in that ring lies off both diagonals, so the full matrix is unnecessary.
View the spiral as a sequence of concentric square layers. Layer \(0\) is the center alone. Layer \(k\) has side length \(2k+1\), so moving from layer \(k-1\) to layer \(k\) means extending the spiral from size \(2k-1\) to size \(2k+1\).
If the diagonal sum of the inner spiral is already known, the only new diagonal values are the four corners of the surrounding ring. This reduces the problem to finding those four corner values explicitly.
Let \(s\) be an odd side length with \(s \ge 3\). The top-right corner of the outer ring is always \(s^2\), because the numbers increase until the ring closes there. Consecutive corners differ by exactly \(s-1\), which is the number of steps along one side of the square.
Therefore the four corners are
$$ s^2,\qquad s^2-(s-1),\qquad s^2-2(s-1),\qquad s^2-3(s-1). $$
Equivalently, for \(j=0,1,2,3\), the corners are \(s^2-j(s-1)\). Their sum is
$$ L(s)=\sum_{j=0}^{3}\bigl(s^2-j(s-1)\bigr)=4s^2-6(s-1)=4s^2-6s+6. $$
This is the exact ring contribution accumulated by the implementations.
Let \(D(s)\) denote the diagonal sum for the spiral of odd side length \(s\). The center gives the base case \(D(1)=1\). Every larger odd square is obtained by adding one outer ring, so for odd \(s \ge 3\),
$$ D(s)=D(s-2)+4s^2-6s+6. $$
The loop invariant in the code is precisely this statement: after processing side length \(s\), the running total equals \(D(s)\). The center is counted once in the base case and never appears again, so there is no double counting issue.
Write \(N=2m+1\), where \(m=(N-1)/2\) is the number of outer rings beyond the center. Substituting \(s=2k+1\) into the ring contribution gives
$$ L(2k+1)=16k^2+4k+4. $$
Hence
$$ D(N)=1+\sum_{k=1}^{m}(16k^2+4k+4). $$
Using the standard formulas for \(\sum k\) and \(\sum k^2\), this becomes
$$ D(N)=\frac{16m^3+30m^2+26m+3}{3} =\frac{4N^3+3N^2+8N-9}{6}. $$
The implementations do not need the closed form, because the layer-by-layer loop is already tiny for \(N=1001\). Still, the closed form shows that the recurrence is exact and that the answer depends only on the odd side length.
The \(5 \times 5\) spiral has diagonal sum \(101\). The next ring has side length \(s=7\), so its corners are
$$ 7^2=49,\qquad 49-6=43,\qquad 49-12=37,\qquad 49-18=31. $$
The new contribution is \(49+43+37+31=160\), so the \(7 \times 7\) diagonal sum is \(101+160=261\). This is exactly the second checkpoint used in the implementations.
The C++, Python, and Java implementations accept an optional odd size and default to \(1001\). They reject non-positive or even inputs because a centered spiral with a single middle cell exists only for odd side lengths.
Before producing the final result, the implementation can verify two known values: \(D(5)=101\) and \(D(7)=261\). These checkpoints confirm the corner formula and the loop boundaries.
The computation begins with a running total of \(1\) for the center. It then iterates over odd side lengths \(3,5,7,\dots,N\). For each side length \(s\), it adds \(4s^2-6(s-1)\), which is the sum of the four corners of the new outer ring.
No spiral array is allocated, and no individual interior cells are generated. The implementation stores only the current side length and the running total, so it mirrors the recurrence directly in constant space.
The loop visits each odd side length once, so the number of iterations is \((N-1)/2\). That gives \(O(N)\) time and \(O(1)\) space.
A literal construction of the whole spiral would require \(O(N^2)\) work and \(O(N^2)\) storage. The implemented method is faster and simpler because it uses only the corner arithmetic. A closed-form evaluation would be \(O(1)\), but for this problem size the iterative method is already effectively instantaneous.
Die Spirale beginnt mit \(1\) im Zentrum und schreibt die positiven Zahlen im Uhrzeigersinn in ein quadratisches Muster. Für eine ungerade Seitenlänge \(N\) soll die Summe der Einträge auf den beiden Diagonalen der entstehenden \(N \times N\)-Spirale berechnet werden, ohne das gesamte Gitter aufzubauen.
Im Fall \(5 \times 5\) lauten die Diagonalwerte \(1,3,5,7,9,13,17,21,25\), also ist die Summe \(101\). Dasselbe Prinzip gilt für jede positive ungerade Zahl \(N\), also auch für die Zielgröße \(1001\).
Die entscheidende Vereinfachung ist, dass beim Übergang von einer ungeraden Quadratgröße zur nächsten nur vier neue Diagonalwerte entstehen: die vier Ecken des neuen Außenrings. Alle übrigen Werte dieses Rings liegen auf keiner der beiden Diagonalen.
Man kann die Spirale als Folge konzentrischer quadratischer Schichten betrachten. Schicht \(0\) besteht nur aus dem Zentrum. Schicht \(k\) besitzt die Seitenlänge \(2k+1\). Der Übergang von Schicht \(k-1\) zu Schicht \(k\) erweitert die Spirale also von Größe \(2k-1\) auf Größe \(2k+1\).
Ist die Diagonalsumme der inneren Spirale bekannt, dann liefern genau die vier Ecken des neuen Außenrings den zusätzlichen Beitrag. Damit reduziert sich das Problem auf eine explizite Formel für diese vier Ecken.
Sei \(s\) eine ungerade Seitenlänge mit \(s \ge 3\). Die rechte obere Ecke des Außenrings ist immer \(s^2\), denn dort endet das Ausschreiben des Rings. Zwei benachbarte Ecken unterscheiden sich jeweils um genau \(s-1\), also um die Länge einer Quadratseite ohne den bereits gezählten Startpunkt.
Die vier Ecken sind daher
$$ s^2,\qquad s^2-(s-1),\qquad s^2-2(s-1),\qquad s^2-3(s-1). $$
Oder einheitlich für \(j=0,1,2,3\): \(s^2-j(s-1)\). Ihre Summe ist
$$ L(s)=\sum_{j=0}^{3}\bigl(s^2-j(s-1)\bigr)=4s^2-6(s-1)=4s^2-6s+6. $$
Genau dieser Ausdruck wird in den Implementierungen für jeden Ring addiert.
Bezeichne mit \(D(s)\) die Diagonalsumme der Spirale mit ungerader Seitenlänge \(s\). Für das Zentrum gilt \(D(1)=1\). Jede größere ungerade Spirale entsteht durch einen zusätzlichen Außenring, also gilt für ungerades \(s \ge 3\)
$$ D(s)=D(s-2)+4s^2-6s+6. $$
Das ist zugleich die Schleifeninvariante des Codes: Nach der Verarbeitung der Seitenlänge \(s\) ist die laufende Summe exakt gleich \(D(s)\). Das Zentrum wird nur im Basisfall gezählt und danach nie erneut berührt.
Schreibe \(N=2m+1\), wobei \(m=(N-1)/2\) die Zahl der Außenringe außerhalb des Zentrums ist. Setzt man \(s=2k+1\) in den Ringbeitrag ein, erhält man
$$ L(2k+1)=16k^2+4k+4. $$
Damit folgt
$$ D(N)=1+\sum_{k=1}^{m}(16k^2+4k+4). $$
Mit den Standardformeln für \(\sum k\) und \(\sum k^2\) ergibt sich die geschlossene Form
$$ D(N)=\frac{16m^3+30m^2+26m+3}{3} =\frac{4N^3+3N^2+8N-9}{6}. $$
Die Implementierungen brauchen diese geschlossene Form nicht, weil die Schleife über die wenigen Ringe bereits sehr klein ist. Sie macht aber transparent, warum die Rekurrenz exakt ist und warum nur die ungerade Seitenlänge zählt.
Für \(5 \times 5\) beträgt die Diagonalsumme \(101\). Der nächste Ring hat die Seitenlänge \(s=7\), also lauten seine Ecken
$$ 7^2=49,\qquad 49-6=43,\qquad 49-12=37,\qquad 49-18=31. $$
Der neue Ring trägt also \(49+43+37+31=160\) bei. Damit ist die Diagonalsumme der \(7 \times 7\)-Spirale gleich \(101+160=261\). Genau dieser Wert dient in den Implementierungen als zweiter Kontrollpunkt.
Die C++-, Python- und Java-Implementierungen akzeptieren optional eine ungerade Größe und verwenden standardmäßig \(1001\). Nichtpositive oder gerade Eingaben werden verworfen, weil eine zentrierte Spirale mit genau einem Mittelpunkt nur für ungerade Seitenlängen existiert.
Vor der endgültigen Ausgabe kann die Implementierung zwei bekannte Werte prüfen: \(D(5)=101\) und \(D(7)=261\). Diese Tests bestätigen sowohl die Eckformel als auch die Schleifengrenzen.
Die Berechnung beginnt mit der laufenden Summe \(1\) für das Zentrum. Danach werden die ungeraden Seitenlängen \(3,5,7,\dots,N\) durchlaufen. Für jede Seitenlänge \(s\) wird \(4s^2-6(s-1)\) addiert, also genau die Summe der vier Ecken des neuen Außenrings.
Es wird weder ein Spiral-Array aufgebaut noch werden innere Felder einzeln erzeugt. Gespeichert werden nur die aktuelle Seitenlänge und die laufende Summe, also genau die Größen aus der Rekurrenz.
Die Schleife besucht jede ungerade Seitenlänge genau einmal, also insgesamt \((N-1)/2\) Iterationen. Daraus folgen \(O(N)\) Laufzeit und \(O(1)\) Speicherverbrauch.
Ein wörtlicher Aufbau der gesamten Spirale würde \(O(N^2)\) Arbeit und \(O(N^2)\) Speicher benötigen. Die implementierte Methode ist schneller und deutlich einfacher, weil sie nur mit den Eckwerten arbeitet. Eine direkte Auswertung der geschlossenen Form wäre zwar \(O(1)\), doch für diese Problemgröße ist die iterative Lösung bereits praktisch sofort fertig.
Spiral, merkezdeki \(1\) ile başlar ve pozitif tam sayılar saat yönünde ilerleyen kare bir düzen içinde yazılır. Tek bir kenar uzunluğu \(N\) verildiğinde amaç, oluşan \(N \times N\) spiralinin iki köşegenindeki sayıların toplamını tüm tabloyu kurmadan hesaplamaktır.
\(5 \times 5\) durumda köşegen üzerindeki değerler \(1,3,5,7,9,13,17,21,25\) olur ve toplam \(101\) çıkar. Aynı yaklaşım her pozitif tek \(N\) için geçerlidir; buna hedef boyut olan \(1001\) de dahildir.
Asıl sadeleştirme şudur: spiral bir sonraki tek kare boyuta büyüdüğünde köşegenlere yalnızca dört yeni sayı eklenir. Bunlar yeni dış halkadaki dört köşedir. Halkadaki diğer bütün sayılar iki köşegenin de dışındadır; dolayısıyla tüm matrisi üretmeye gerek yoktur.
Spirali iç içe geçmiş kare katmanlar olarak düşünelim. \(0\). katman yalnızca merkezdir. \(k\). katmanın kenar uzunluğu \(2k+1\) olduğundan, \(k-1\). katmandan \(k\). katmana geçmek spirali \(2k-1\) boyutundan \(2k+1\) boyutuna genişletir.
İçteki spiral için köşegen toplamı biliniyorsa, yeni katkı yalnızca dıştaki halkanın dört köşesinden gelir. Böylece problem, bu dört köşeyi açık bir formülle yazmaya indirgenir.
\(s \ge 3\) olacak şekilde tek bir kenar uzunluğu \(s\) alalım. Dış halkanın sağ üst köşesi her zaman \(s^2\) olur; çünkü sayılar artarak o noktada tamamlanır. Ardışık köşeler arasındaki fark tam olarak \(s-1\)'dir; bu da karenin bir kenarı boyunca alınan adım sayısıdır.
Bu yüzden dört köşe
$$ s^2,\qquad s^2-(s-1),\qquad s^2-2(s-1),\qquad s^2-3(s-1) $$
şeklindedir. Eşdeğer olarak \(j=0,1,2,3\) için köşeler \(s^2-j(s-1)\) olur. Bu dört değerin toplamı
$$ L(s)=\sum_{j=0}^{3}\bigl(s^2-j(s-1)\bigr)=4s^2-6(s-1)=4s^2-6s+6 $$
olur. Uygulamaların her turda topladığı tam ifade budur.
\(D(s)\), kenarı \(s\) olan tek boyutlu spiral için köşegen toplamı olsun. Merkez tek başına olduğundan taban durum \(D(1)=1\)'dir. Daha büyük her tek kare, bir dış halka eklenerek elde edildiği için tek \(s \ge 3\) için
$$ D(s)=D(s-2)+4s^2-6s+6 $$
eşitliği geçerlidir. Kod içindeki döngü değişmezi de tam olarak budur: kenar uzunluğu \(s\) işlendiğinde eldeki toplam artık \(D(s)\)'ye eşittir. Merkez yalnızca başlangıçta sayıldığı için ikinci kez eklenmez.
\(N=2m+1\) yazalım; burada \(m=(N-1)/2\), merkezin dışındaki halka sayısıdır. \(s=2k+1\) yerleştirildiğinde halka katkısı
$$ L(2k+1)=16k^2+4k+4 $$
olur. Dolayısıyla
$$ D(N)=1+\sum_{k=1}^{m}(16k^2+4k+4) $$
elde edilir. \(\sum k\) ve \(\sum k^2\) için standart toplam formülleri kullanıldığında
$$ D(N)=\frac{16m^3+30m^2+26m+3}{3} =\frac{4N^3+3N^2+8N-9}{6} $$
sonucuna ulaşılır. Uygulamalar bu kapalı biçime ihtiyaç duymaz; çünkü halka halka ilerleyen döngü \(N=1001\) için zaten çok küçüktür. Yine de bu ifade, yinelemenin tam olarak neden doğru olduğunu açıkça gösterir.
\(5 \times 5\) spiralinin köşegen toplamı \(101\)'dir. Bir sonraki halkanın kenarı \(s=7\) olduğundan köşeler
$$ 7^2=49,\qquad 49-6=43,\qquad 49-12=37,\qquad 49-18=31 $$
olur. Yeni halka \(49+43+37+31=160\) katkı yapar; böylece \(7 \times 7\) toplamı \(101+160=261\) çıkar. Bu, uygulamalardaki ikinci doğrulama değeridir.
C++, Python ve Java uygulamaları isteğe bağlı bir tek boyut kabul eder ve varsayılan olarak \(1001\) kullanır. Sıfırdan küçük, sıfır ya da çift girişler reddedilir; çünkü tek bir merkez hücresi olan spiral yalnızca tek kenar uzunluklarında anlamlıdır.
Sonucu yazdırmadan önce uygulama iki bilinen değeri kontrol edebilir: \(D(5)=101\) ve \(D(7)=261\). Bu kontroller hem köşe formülünü hem de döngünün doğru aralıkta çalıştığını sınar.
Hesaplama merkez için \(1\) ile başlar. Ardından \(3,5,7,\dots,N\) biçimindeki tek kenar uzunlukları dolaşılır. Her \(s\) için yeni dış halkanın dört köşesinin toplamı olan \(4s^2-6(s-1)\) mevcut sonuca eklenir.
Ne bir spiral dizisi oluşturulur ne de iç hücreler tek tek hesaplanır. Uygulama yalnızca güncel kenar uzunluğunu ve çalışan toplamı tuttuğu için bellek kullanımı sabit kalır ve matematiksel yineleme doğrudan kodlanmış olur.
Döngü her tek kenar uzunluğunu bir kez ziyaret eder; toplam yineleme sayısı \((N-1)/2\)'dir. Bu nedenle zaman karmaşıklığı \(O(N)\), bellek karmaşıklığı \(O(1)\)'dir.
Spirali gerçekten tablo halinde kurmak \(O(N^2)\) iş ve \(O(N^2)\) bellek gerektirirdi. Buradaki yöntem yalnızca köşe aritmetiğini kullandığı için hem daha hızlı hem de daha sadedir. Kapalı biçim doğrudan kullanılsa süre \(O(1)\) olurdu, ancak bu problem boyutunda yinelemeli çözüm zaten fiilen anlıktır.
La espiral comienza con \(1\) en el centro y escribe los enteros positivos siguiendo un patrón cuadrado en sentido horario. Dada una longitud impar \(N\), hay que calcular la suma de los valores situados en las dos diagonales de la espiral \(N \times N\) sin construir toda la cuadrícula.
En el caso \(5 \times 5\), los valores diagonales son \(1,3,5,7,9,13,17,21,25\), y su suma es \(101\). La misma idea funciona para cualquier \(N\) impar positivo, incluido el tamaño objetivo \(1001\).
La simplificación decisiva es que, cuando la espiral pasa de un cuadrado impar al siguiente, las diagonales solo reciben cuatro valores nuevos: las cuatro esquinas del nuevo anillo exterior. Todos los demás números de ese anillo quedan fuera de ambas diagonales.
Puede verse la espiral como una sucesión de capas cuadradas concéntricas. La capa \(0\) es solo el centro. La capa \(k\) tiene lado \(2k+1\), así que pasar de la capa \(k-1\) a la capa \(k\) significa ampliar la espiral de tamaño \(2k-1\) a tamaño \(2k+1\).
Si ya conocemos la suma diagonal de la espiral interior, la nueva contribución procede exactamente de las cuatro esquinas del anillo que la rodea. Por eso el problema se reduce a describir esas cuatro esquinas con una fórmula cerrada.
Sea \(s\) un lado impar con \(s \ge 3\). La esquina superior derecha del anillo exterior siempre es \(s^2\), porque la numeración creciente termina allí. La diferencia entre esquinas consecutivas es exactamente \(s-1\), el número de pasos a lo largo de un lado del cuadrado.
Por lo tanto, las cuatro esquinas son
$$ s^2,\qquad s^2-(s-1),\qquad s^2-2(s-1),\qquad s^2-3(s-1). $$
De forma uniforme, para \(j=0,1,2,3\), las esquinas son \(s^2-j(s-1)\). Su suma vale
$$ L(s)=\sum_{j=0}^{3}\bigl(s^2-j(s-1)\bigr)=4s^2-6(s-1)=4s^2-6s+6. $$
Esa es exactamente la cantidad que acumulan las implementaciones en cada iteración.
Sea \(D(s)\) la suma de las diagonales de la espiral de lado impar \(s\). El centro da el caso base \(D(1)=1\). Cada cuadrado impar mayor se obtiene añadiendo un anillo exterior, de modo que para todo \(s\) impar con \(s \ge 3\),
$$ D(s)=D(s-2)+4s^2-6s+6. $$
Esta es también la invariante del bucle en el código: una vez procesado el lado \(s\), el acumulado coincide exactamente con \(D(s)\). El centro se cuenta una sola vez en el caso base y no vuelve a aparecer en ningún anillo posterior.
Escribamos \(N=2m+1\), donde \(m=(N-1)/2\) es el número de anillos exteriores alrededor del centro. Sustituyendo \(s=2k+1\) en la contribución de un anillo obtenemos
$$ L(2k+1)=16k^2+4k+4. $$
Por tanto,
$$ D(N)=1+\sum_{k=1}^{m}(16k^2+4k+4). $$
Usando las fórmulas clásicas para \(\sum k\) y \(\sum k^2\), esto se reduce a
$$ D(N)=\frac{16m^3+30m^2+26m+3}{3} =\frac{4N^3+3N^2+8N-9}{6}. $$
Las implementaciones no necesitan esta expresión cerrada porque el recorrido anillo por anillo ya es muy pequeño para \(N=1001\). Sin embargo, la fórmula deja claro por qué la recurrencia es exacta.
La espiral \(5 \times 5\) tiene suma diagonal \(101\). El siguiente anillo tiene lado \(s=7\), así que sus esquinas son
$$ 7^2=49,\qquad 49-6=43,\qquad 49-12=37,\qquad 49-18=31. $$
La nueva contribución es \(49+43+37+31=160\), y por tanto la suma diagonal de la espiral \(7 \times 7\) es \(101+160=261\). Ese mismo valor aparece como segundo punto de comprobación en las implementaciones.
Las implementaciones en C++, Python y Java aceptan opcionalmente un tamaño impar y usan \(1001\) por defecto. Rechazan entradas no positivas o pares, porque una espiral centrada con una única celda central solo existe para lados impares.
Antes de producir el resultado final, la implementación puede verificar dos valores conocidos: \(D(5)=101\) y \(D(7)=261\). Estas comprobaciones validan tanto la fórmula de las esquinas como los límites del bucle.
El cálculo empieza con un acumulado igual a \(1\) por la celda central. Después recorre los lados impares \(3,5,7,\dots,N\). Para cada lado \(s\), añade \(4s^2-6(s-1)\), que es la suma de las cuatro esquinas del nuevo anillo exterior.
No se reserva ninguna matriz para la espiral ni se generan las celdas interiores una a una. La implementación solo guarda el lado actual y el acumulado, así que traduce la recurrencia matemática directamente a una computación en espacio constante.
El bucle visita cada lado impar una vez, por lo que realiza \((N-1)/2\) iteraciones. Eso da un tiempo \(O(N)\) y un espacio \(O(1)\).
Construir literalmente la espiral completa costaría \(O(N^2)\) tiempo y \(O(N^2)\) memoria. El método implementado es más rápido y más limpio porque solo usa la aritmética de las esquinas. Una evaluación directa de la fórmula cerrada sería \(O(1)\), pero para este tamaño de entrada la versión iterativa ya es prácticamente instantánea.
这个数阵从中心的 \(1\) 开始，把正整数按顺时针方向写成一个不断向外扩张的方形螺旋。给定奇数边长 \(N\)，目标是在不构造整个 \(N \times N\) 方阵的前提下，求出两条对角线上的数字总和。
在 \(5 \times 5\) 的例子中，对角线上的数字是 \(1,3,5,7,9,13,17,21,25\)，总和为 \(101\)。同样的推导适用于任意正奇数 \(N\)，包括题目关注的 \(1001\)。
最关键的观察是：螺旋从一个奇数阶方阵扩展到下一个奇数阶方阵时，对角线只会新增四个数，也就是新外环的四个角。外环中的其他数字都不在两条对角线上，因此完全没有必要把整个方阵都生成出来。
可以把整个图形看成一层一层向外包裹的同心正方形。第 \(0\) 层只有中心数字。第 \(k\) 层的边长是 \(2k+1\)，因此从第 \(k-1\) 层扩展到第 \(k\) 层，就是把边长从 \(2k-1\) 增加到 \(2k+1\)。
如果内层螺旋的对角线和已经知道，那么新增加到对角线上的就只有外层正方形的四个顶点。于是问题自然转化为：这些角点的值到底是多少。
设外环边长为奇数 \(s\)，且 \(s \ge 3\)。右上角一定是 \(s^2\)，因为数字沿着外环递增，最后停在这个角上。相邻两个角之间的差恰好是 \(s-1\)，这正是一条边上前进的步数。
因此，四个角依次为
$$ s^2,\qquad s^2-(s-1),\qquad s^2-2(s-1),\qquad s^2-3(s-1). $$
也可以统一写成：当 \(j=0,1,2,3\) 时，角点为 \(s^2-j(s-1)\)。四个角的总和就是
$$ L(s)=\sum_{j=0}^{3}\bigl(s^2-j(s-1)\bigr)=4s^2-6(s-1)=4s^2-6s+6. $$
这正是实现中每处理一层时加入到总和里的公式。
记 \(D(s)\) 为边长为奇数 \(s\) 的螺旋对角线总和。中心单元给出初值 \(D(1)=1\)。任意更大的奇数阶螺旋都可以看成在较小螺旋外面再加一圈，因此当 \(s \ge 3\) 且 \(s\) 为奇数时，有
$$ D(s)=D(s-2)+4s^2-6s+6. $$
这也是代码里的核心不变量：当循环处理完边长 \(s\) 时，当前累计值就精确等于 \(D(s)\)。中心只在初始值里出现一次，之后的每一层都只贡献新的四个角，因此不会重复计数。
令 \(N=2m+1\)，其中 \(m=(N-1)/2\) 表示中心之外一共有多少层外环。把 \(s=2k+1\) 代入单层贡献公式，可以得到
$$ L(2k+1)=16k^2+4k+4. $$
于是总和满足
$$ D(N)=1+\sum_{k=1}^{m}(16k^2+4k+4). $$
再利用 \(\sum k\) 和 \(\sum k^2\) 的标准求和公式，就能化简成闭式
$$ D(N)=\frac{16m^3+30m^2+26m+3}{3} =\frac{4N^3+3N^2+8N-9}{6}. $$
实现本身并不需要直接使用这个闭式，因为对 \(N=1001\) 来说，逐层累加已经非常快了。不过闭式很好地说明了递推为什么正确，也揭示了答案只取决于奇数边长本身。
\(5 \times 5\) 螺旋的对角线和是 \(101\)。下一层的边长是 \(s=7\)，因此四个角分别是
$$ 7^2=49,\qquad 49-6=43,\qquad 49-12=37,\qquad 49-18=31. $$
这一层新增的贡献为 \(49+43+37+31=160\)，所以 \(7 \times 7\) 螺旋的对角线和就是 \(101+160=261\)。这个数正好也是实现中使用的第二个检查值。
C++、Python 和 Java 的实现都允许传入一个可选的奇数边长，默认值是 \(1001\)。如果输入不是正奇数，程序就会拒绝，因为只有奇数边长的方阵才有唯一的中心格。
在输出最终结果之前，实现还可以先验证两个已知值：\(D(5)=101\) 与 \(D(7)=261\)。这两个检查点同时验证了角点公式和循环区间没有偏差。
计算从总和 \(1\) 开始，对应中心数字。随后循环遍历所有奇数边长 \(3,5,7,\dots,N\)。对每个边长 \(s\)，程序加入 \(4s^2-6(s-1)\)，也就是新外环四个角的总和。
整个过程中不会分配螺旋矩阵，也不会逐格生成内部数字。实现只保存当前边长和累计总和，因此空间始终是常数级，并且与数学递推完全一致。
循环对每一个奇数边长执行一次，因此总迭代次数是 \((N-1)/2\)。时间复杂度为 \(O(N)\)，空间复杂度为 \(O(1)\)。
如果真的去构造整个螺旋方阵，则需要 \(O(N^2)\) 的时间和 \(O(N^2)\) 的存储。这里的实现只利用四个角的算术关系，因此明显更高效。若直接套用闭式，时间可以降到 \(O(1)\)，但对于本题规模，当前的逐层方法已经几乎瞬时完成。
Спираль начинается с числа \(1\) в центре, после чего натуральные числа записываются по часовой стрелке, образуя квадратную схему. Для нечетной стороны \(N\) требуется найти сумму чисел на двух диагоналях спирали размера \(N \times N\), не строя всю таблицу целиком.
В случае \(5 \times 5\) на диагоналях стоят числа \(1,3,5,7,9,13,17,21,25\), и их сумма равна \(101\). Тот же подход работает для любого положительного нечетного \(N\), включая целевой размер \(1001\).
Главное упрощение состоит в том, что при переходе от одного нечетного квадрата к следующему на диагонали добавляются только четыре новых числа: четыре угла внешнего кольца. Все остальные числа этого кольца не лежат ни на одной из диагоналей.
Удобно рассматривать спираль как набор вложенных квадратных слоев. Слой \(0\) состоит только из центральной клетки. Слой \(k\) имеет сторону \(2k+1\), поэтому переход от слоя \(k-1\) к слою \(k\) увеличивает размер спирали с \(2k-1\) до \(2k+1\).
Если сумма диагоналей внутренней спирали уже известна, то новый вклад дают ровно четыре угловые клетки окружающего кольца. Значит, задача сводится к явной формуле для этих углов.
Пусть \(s\) — нечетная длина стороны, \(s \ge 3\). Правый верхний угол внешнего кольца всегда равен \(s^2\), потому что именно там заканчивается заполнение очередного квадрата. Разность между соседними углами равна \(s-1\), то есть числу шагов вдоль одной стороны квадрата.
Следовательно, четыре угла имеют вид
$$ s^2,\qquad s^2-(s-1),\qquad s^2-2(s-1),\qquad s^2-3(s-1). $$
Или в единой записи: для \(j=0,1,2,3\) угол равен \(s^2-j(s-1)\). Сумма этих четырех чисел равна
$$ L(s)=\sum_{j=0}^{3}\bigl(s^2-j(s-1)\bigr)=4s^2-6(s-1)=4s^2-6s+6. $$
Именно эту величину реализации добавляют на каждом шаге.
Обозначим через \(D(s)\) сумму диагоналей спирали с нечетной стороной \(s\). Базовый случай задается центром: \(D(1)=1\). Любая большая нечетная спираль получается добавлением одного внешнего кольца, поэтому для нечетного \(s \ge 3\)
$$ D(s)=D(s-2)+4s^2-6s+6. $$
Это и есть инвариант цикла в коде: после обработки стороны \(s\) накопленная сумма точно равна \(D(s)\). Центральная единица учитывается только в базовом случае и больше не появляется.
Запишем \(N=2m+1\), где \(m=(N-1)/2\) — число внешних колец вокруг центра. Подстановка \(s=2k+1\) в формулу вклада кольца дает
$$ L(2k+1)=16k^2+4k+4. $$
Отсюда следует
$$ D(N)=1+\sum_{k=1}^{m}(16k^2+4k+4). $$
Используя стандартные формулы для \(\sum k\) и \(\sum k^2\), получаем закрытую форму
$$ D(N)=\frac{16m^3+30m^2+26m+3}{3} =\frac{4N^3+3N^2+8N-9}{6}. $$
Реализациям эта формула не обязательна, потому что послойный проход и так очень мал для \(N=1001\). Но она показывает, почему рекурсия верна и почему ответ определяется только нечетной длиной стороны.
Для спирали \(5 \times 5\) сумма диагоналей равна \(101\). Следующее кольцо имеет сторону \(s=7\), значит его углы равны
$$ 7^2=49,\qquad 49-6=43,\qquad 49-12=37,\qquad 49-18=31. $$
Новый вклад составляет \(49+43+37+31=160\), поэтому для спирали \(7 \times 7\) получаем \(101+160=261\). Это ровно второй контрольный результат, который используют реализации.
Реализации на C++, Python и Java принимают необязательный нечетный размер и по умолчанию используют \(1001\). Неположительные и четные значения отвергаются, потому что спираль с единственной центральной клеткой существует только для нечетных сторон.
Перед выводом итогового результата реализация может проверить два известных значения: \(D(5)=101\) и \(D(7)=261\). Эти проверки подтверждают и формулу для углов, и правильные границы цикла.
Вычисление начинается с текущей суммы \(1\), соответствующей центру. Затем перебираются все нечетные стороны \(3,5,7,\dots,N\). Для каждой стороны \(s\) прибавляется \(4s^2-6(s-1)\), то есть сумма четырех углов нового внешнего кольца.
Никакой массив для всей спирали не создается, и внутренние клетки не генерируются по отдельности. Хранятся только текущая сторона и накопленная сумма, поэтому алгоритм напрямую следует математической рекурсии и использует постоянную память.
Цикл проходит по каждому нечетному значению стороны ровно один раз, поэтому число итераций равно \((N-1)/2\). Отсюда получаем время \(O(N)\) и память \(O(1)\).
Если бы спираль строилась буквально как таблица, потребовались бы \(O(N^2)\) времени и \(O(N^2)\) памяти. Реализованный метод намного эффективнее, потому что использует только арифметику углов. Прямая подстановка в закрытую формулу дала бы \(O(1)\), но для данного размера входа итеративная версия и так работает практически мгновенно.
تبدأ اللولبية بالعدد \(1\) في المركز، ثم تُكتب الأعداد الصحيحة الموجبة في نمط مربعي يدور مع عقارب الساعة. عند إعطاء طول ضلع فردي \(N\)، يكون المطلوب حساب مجموع القيم الواقعة على القطرين في اللولبية ذات الحجم \(N \times N\) من دون بناء المصفوفة كاملة.
في حالة \(5 \times 5\)، تكون قيم القطرين هي \(1,3,5,7,9,13,17,21,25\)، ومجموعها \(101\). والفكرة نفسها تنطبق على أي \(N\) فردي موجب، بما في ذلك الحجم المستهدف \(1001\).
الفكرة الحاسمة هي أن اللولبية عندما تكبر من مربع فردي إلى المربع الفردي التالي، فإن القطرين لا يستقبلان إلا أربع قيم جديدة فقط، وهي زوايا الحلقة الخارجية الجديدة. أما باقي الأعداد في تلك الحلقة فلا يقع على أي من القطرين.
يمكن النظر إلى اللولبية على أنها سلسلة من الطبقات المربعة المتداخلة. الطبقة \(0\) هي المركز وحده. أما الطبقة \(k\) فطول ضلعها \(2k+1\)، ولذلك فإن الانتقال من الطبقة \(k-1\) إلى الطبقة \(k\) يعني توسيع اللولبية من الحجم \(2k-1\) إلى الحجم \(2k+1\).
إذا كان مجموع القطرين في اللولبية الداخلية معلومًا، فإن الإضافة الجديدة تأتي بالضبط من الزوايا الأربع للحلقة التي تحيط بها. وهكذا تُختزل المسألة إلى إيجاد صيغة صريحة لهذه الزوايا الأربع.
لنأخذ طول ضلع فردي \(s\) بحيث \(s \ge 3\). الزاوية العليا اليمنى للحلقة الخارجية تساوي دائمًا \(s^2\)، لأن العد التصاعدي ينتهي عندها. كما أن الفرق بين زاويتين متتاليتين يساوي \(s-1\)، وهو عدد الخطوات على طول ضلع واحد من المربع.
لذلك تكون الزوايا الأربع هي
$$ s^2,\qquad s^2-(s-1),\qquad s^2-2(s-1),\qquad s^2-3(s-1). $$
وبصياغة موحدة، عندما يكون \(j=0,1,2,3\) فإن الزاوية تساوي \(s^2-j(s-1)\). ومجموع هذه القيم الأربع هو
$$ L(s)=\sum_{j=0}^{3}\bigl(s^2-j(s-1)\bigr)=4s^2-6(s-1)=4s^2-6s+6. $$
وهذا هو المقدار نفسه الذي تجمعه التنفيذات في كل دورة.
لنرمز إلى مجموع القطرين في اللولبية ذات الضلع الفردي \(s\) بالرمز \(D(s)\). تعطي الخلية المركزية الحالة الأساسية \(D(1)=1\). وكل لولبية فردية أكبر تُبنى بإضافة حلقة خارجية واحدة، ولذلك فعندما يكون \(s \ge 3\) وفرديًا نحصل على
$$ D(s)=D(s-2)+4s^2-6s+6. $$
وهذه بالضبط هي الثابتة التي يحافظ عليها الدوران في الشيفرة: بعد إنهاء معالجة الضلع \(s\)، يكون المجموع الجاري مساويًا تمامًا لـ \(D(s)\). العدد المركزي يُحسب مرة واحدة فقط في البداية ولا يُعاد إدخاله لاحقًا.
نكتب \(N=2m+1\)، حيث \(m=(N-1)/2\) هو عدد الحلقات الخارجية خارج المركز. إذا وضعنا \(s=2k+1\) في مساهمة الحلقة الواحدة فسنحصل على
$$ L(2k+1)=16k^2+4k+4. $$
ومن ثم
$$ D(N)=1+\sum_{k=1}^{m}(16k^2+4k+4). $$
وباستخدام الصيغ القياسية لـ \(\sum k\) و \(\sum k^2\)، نحصل على الصيغة المغلقة
$$ D(N)=\frac{16m^3+30m^2+26m+3}{3} =\frac{4N^3+3N^2+8N-9}{6}. $$
التنفيذات لا تحتاج إلى هذه الصيغة مباشرة، لأن المرور طبقة بعد طبقة صغير جدًا أصلًا عندما يكون \(N=1001\). لكن هذه الصيغة توضح بجلاء لماذا تكون العلاقة الرجعية صحيحة ولماذا يعتمد الجواب فقط على طول الضلع الفردي.
مجموع القطرين في اللولبية \(5 \times 5\) يساوي \(101\). الحلقة التالية لها ضلع \(s=7\)، ولذلك تكون زواياها
$$ 7^2=49,\qquad 49-6=43,\qquad 49-12=37,\qquad 49-18=31. $$
إذن مساهمة الحلقة الجديدة هي \(49+43+37+31=160\)، وبالتالي يصبح مجموع القطرين في اللولبية \(7 \times 7\) مساويًا لـ \(101+160=261\). وهذه هي قيمة التحقق الثانية المستخدمة في التنفيذات.
تسمح تنفيذات C++ وPython وJava بتمرير حجم فردي اختياري، وتستخدم \(1001\) افتراضيًا. ويتم رفض القيم غير الموجبة أو الزوجية، لأن اللولبية ذات المركز الوحيد لا تُعرَّف إلا عندما يكون طول الضلع فرديًا.
قبل طباعة النتيجة النهائية، يمكن للتنفيذ أن يتحقق من قيمتين معروفتين: \(D(5)=101\) و \(D(7)=261\). هذان الاختباران يؤكدان صحة صيغة الزوايا وصحة حدود الحلقة التكرارية.
تبدأ العملية بمجموع جارٍ يساوي \(1\) من أجل المركز. بعد ذلك تمر الشيفرة على الأطوال الفردية \(3,5,7,\dots,N\). ولكل طول \(s\)، تضيف المقدار \(4s^2-6(s-1)\)، وهو مجموع الزوايا الأربع للحلقة الخارجية الجديدة.
لا تُنشأ مصفوفة تمثل اللولبية كاملة، ولا تُولَّد الخلايا الداخلية واحدة واحدة. التنفيذ يحتفظ فقط بطول الضلع الحالي وبالمجموع الجاري، ولذلك يترجم العلاقة الرياضية مباشرةً إلى حساب ذي ذاكرة ثابتة.
تزور الحلقة كل طول ضلع فردي مرة واحدة، ولذلك يكون عدد التكرارات \((N-1)/2\). ومن هنا يكون الزمن \(O(N)\) والحيز \(O(1)\).
أما إذا بُنِيت اللولبية كاملةً بشكل صريح، فسيتطلب ذلك زمنًا \(O(N^2)\) وذاكرة \(O(N^2)\). والطريقة المطبقة هنا أسرع وأبسط لأنها تعتمد فقط على حساب زوايا الحلقات. ولو استُخدمت الصيغة المغلقة مباشرةً لأصبح الزمن \(O(1)\)، لكن النسخة التكرارية الحالية سريعة جدًا بالفعل لهذا الحجم من الإدخال.