A hollow square lamina is a square frame: an outer square of side length \(o\) surrounds a smaller concentric square hole of side length \(i\). The number of tiles used by that frame is the area difference \(o^2-i^2\). Because the hole must stay centered with an integer border width, the two side lengths must have the same parity and satisfy \(o-i\ge2\).
For each tile total \(t\le 10^6\), let \(N(t)\) be the number of different laminae that use exactly \(t\) tiles, where different outer/inner side pairs count as different arrangements. The goal is to count how many tile totals satisfy
$$1\le N(t)\le 10.$$
The implementations solve the problem by enumerating every valid lamina exactly once, recording how often each tile total appears, and then counting the totals whose multiplicity lies between one and ten. The mathematics is therefore about describing the valid state space cleanly and proving that the loops cover it without omissions or duplicates.
Each lamina is determined by a pair \((o,i)\) with \(o>i\ge1\), \(o\equiv i\pmod2\), and tile count
$$T(o,i)=o^2-i^2=(o-i)(o+i).$$
If we write the border thickness as \(k=(o-i)/2\ge1\), then \(o=i+2k\), and the same quantity becomes
$$T(o,i)=4k(i+k).$$
This reformulation exposes two useful invariants. First, every admissible tile total is a multiple of \(4\). Second, a distinct arrangement is exactly a distinct pair of an inner side length and a thickness, or equivalently a distinct pair \((o,i)\).
For a fixed outer side length \(o\), the smallest possible lamina is the thinnest one, obtained by taking \(i=o-2\). Its tile count is
$$T_{\min}(o)=o^2-(o-2)^2=4o-4.$$
If this minimum already exceeds the limit \(L\), then no lamina with that outer side length can contribute. So the only outer squares worth considering are those with
$$4o-4\le L.$$
That is exactly why the outer loop stops at the first \(o\) for which the thinnest ring would already use too many tiles.
Once \(o\) is fixed, the hole must remain centered, so the inner side length must keep the same parity as \(o\). The valid inner sizes are therefore
$$i=o-2,\ o-4,\ o-6,\dots$$
down to the smallest positive value of matching parity. This is not a programming convenience; it is the exact arithmetic description of all legal laminae. Every valid centered square frame appears once in this list, and no impossible half-tile border width is ever generated.
For fixed \(o\), decreasing \(i\) makes the hole smaller and the frame thicker, so the tile count must increase. The code relies on the explicit identity
$$T(o,i-2)-T(o,i)=\bigl(o^2-(i-2)^2\bigr)-\bigl(o^2-i^2\bigr)=4(i-1)\gt0.$$
Therefore the sequence of tile counts for a fixed outer square is strictly increasing as the inner loop proceeds. Once some \(i\) gives \(T(o,i)>L\), every later inner value in that same loop will also exceed \(L\), so breaking immediately is mathematically correct.
Define
$$N(t)=\#\{(o,i): o>i\ge1,\ o\equiv i\pmod2,\ o^2-i^2=t\}.$$
The double loop computes this function directly. Each admissible pair \((o,i)\) contributes one unit to the frequency of the tile total \(t=T(o,i)\). After the enumeration is finished, the required answer is simply
$$\#\{t\le L:1\le N(t)\le10\}.$$
So Problem 174 is not asking for the number of laminae themselves. It asks for the number of tile totals that can be realized in a small number of distinct ways.
The tile total \(32\) illustrates why a frequency table is needed. We have
$$6^2-2^2=36-4=32,$$
and also
$$9^2-7^2=81-49=32.$$
Both pairs obey the parity condition and describe different laminae, so \(N(32)=2\). During enumeration, the implementations encounter both pairs separately and increment the same counter twice. Any tile total whose counter ends in the range from \(1\) to \(10\) contributes one to the final answer.
The C++, Python, and Java implementations allocate an array of length \(L+1\), initially filled with zeros. Entry \(t\) records how many different laminae use exactly \(t\) tiles.
The outer loop starts at \(o=3\), the smallest outer square that can surround a positive inner hole, and runs while \(4o-4\le L\). For each outer side length, the inner side starts at \(o-2\) and decreases by \(2\), which preserves the parity condition automatically.
For each pair \((o,i)\), the implementation computes \(t=o^2-i^2\). If \(t\le L\), the corresponding frequency entry is incremented. If \(t>L\), the inner loop stops immediately, because the monotonicity argument above guarantees that all later values of \(i\) would produce even larger tile totals.
This means the double loop is not an unstructured brute force search. It is a precise enumeration of the admissible pairs, with a mathematically justified early exit inside each fixed-outer sweep.
After all laminae have been generated, the implementation scans the frequency table from \(1\) to \(L\). Every tile total whose frequency lies between \(1\) and the allowed maximum is counted. In the Project Euler instance, that maximum is \(10\), so the program counts the tile totals that have one through ten distinct arrangements.
The C++ version also allows the limit and the upper multiplicity bound to be varied, but all three implementations follow the same mathematical strategy.
Let \(A(L)\) be the number of admissible pairs \((o,i)\) with \(o^2-i^2\le L\). The enumeration phase visits each such pair exactly once, so its running time is \(O(A(L))\). The final pass over the frequency table contributes another \(O(L)\).
Hence the total running time is
$$O(A(L)+L),$$
while the memory usage is
$$O(L),$$
because the dominant data structure is the frequency array of size \(L+1\). For \(L=10^6\), this is easily practical: the code reduces the problem to one enumeration pass and one linear tally.
Eine hohle quadratische Lamina ist ein quadratischer Rahmen: Ein äußeres Quadrat mit Seitenlänge \(o\) umschließt ein kleineres konzentrisches quadratisches Loch mit Seitenlänge \(i\). Die Anzahl der verwendeten Steine ist die Flächendifferenz \(o^2-i^2\). Damit das Loch zentriert bleibt und die Rahmenbreite ganzzahlig ist, müssen \(o\) und \(i\) dieselbe Parität haben und \(o-i\ge2\) erfüllen.
Für jede Steinzahl \(t\le 10^6\) sei \(N(t)\) die Anzahl verschiedener Laminas mit genau \(t\) Steinen, wobei verschiedene Paare aus äußerer und innerer Seitenlänge als verschiedene Anordnungen gelten. Gesucht ist die Anzahl der Steinzahlen mit
$$1\le N(t)\le 10.$$
Die Implementierungen versuchen nicht, geeignete Steinzahlen direkt zu charakterisieren. Stattdessen erzeugen sie jede zulässige Lamina genau einmal, zählen für jede Steinzahl ihre Häufigkeit und fragen erst am Ende, welche Steinzahlen zwischen einer und zehn Darstellungen besitzen.
Jede Lamina wird durch ein Paar \((o,i)\) mit \(o>i\ge1\), \(o\equiv i\pmod2\) und
$$T(o,i)=o^2-i^2=(o-i)(o+i)$$
beschrieben. Schreibt man die Rahmendicke als \(k=(o-i)/2\ge1\), also \(o=i+2k\), so erhält man auch
$$T(o,i)=4k(i+k).$$
Damit werden zwei Invarianten sofort sichtbar: Jede zulässige Steinzahl ist ein Vielfaches von \(4\), und jede verschiedene Anordnung entspricht genau einem bestimmten Paar \((o,i)\) beziehungsweise einem bestimmten inneren Quadrat und einer bestimmten Dicke.
Für feste äußere Seitenlänge \(o\) ist die kleinste mögliche Lamina die dünnste, also die Wahl \(i=o-2\). Ihre Steinzahl ist
$$T_{\min}(o)=o^2-(o-2)^2=4o-4.$$
Wenn bereits dieses Minimum größer als das Limit \(L\) ist, kann keine Lamina mit dieser äußeren Seitenlänge mehr beitragen. Deshalb müssen nur die Werte mit
$$4o-4\le L$$
durchlaufen werden. Genau diese Schranke benutzt die äußere Schleife.
Bei festem \(o\) muss das Loch zentriert bleiben, also muss \(i\) dieselbe Parität wie \(o\) behalten. Die zulässigen inneren Seitenlängen sind daher
$$i=o-2,\ o-4,\ o-6,\dots$$
bis zum kleinsten positiven Wert mit passender Parität. Das ist keine willkürliche Implementationsentscheidung, sondern die exakte Beschreibung aller gültigen Laminas. Jede legale Lamina erscheint genau einmal, und unmögliche halbe Rahmenbreiten werden gar nicht erst betrachtet.
Für festes \(o\) wird das Loch kleiner und der Rahmen dicker, wenn \(i\) sinkt. Die Steinzahl wächst also streng monoton. Algebraisch gilt
$$T(o,i-2)-T(o,i)=\bigl(o^2-(i-2)^2\bigr)-\bigl(o^2-i^2\bigr)=4(i-1)\gt0.$$
Sobald also ein bestimmter innerer Wert schon \(T(o,i)>L\) liefert, werden alle späteren Werte in derselben Schleife ebenfalls zu groß sein. Darum ist der sofortige Abbruch der inneren Schleife mathematisch korrekt.
Definiere
$$N(t)=\#\{(o,i): o>i\ge1,\ o\equiv i\pmod2,\ o^2-i^2=t\}.$$
Genau diese Funktion berechnet die Doppelschleife. Jedes zulässige Paar \((o,i)\) erhöht den Zähler der zugehörigen Steinzahl um eins. Nach Abschluss der Enumeration ist die gesuchte Antwort einfach
$$\#\{t\le L:1\le N(t)\le10\}.$$
Die Aufgabe fragt also nicht nach der Anzahl aller Laminas, sondern nach der Anzahl der Steinzahlen, die sich auf wenige verschiedene Arten als Lamina realisieren lassen.
Die Steinzahl \(32\) zeigt gut, warum eine Häufigkeitstabelle nötig ist. Es gilt
$$6^2-2^2=36-4=32,$$
und außerdem
$$9^2-7^2=81-49=32.$$
Beide Paare erfüllen die Paritätsbedingung und beschreiben verschiedene Laminas, also ist \(N(32)=2\). Während der Enumeration werden beide Paare getrennt gefunden und erhöhen denselben Zähler. Jede Steinzahl, deren Zähler am Ende zwischen \(1\) und \(10\) liegt, trägt eins zum Ergebnis bei.
Die Implementierungen in C++, Python und Java reservieren ein Feld der Länge \(L+1\), das anfangs nur Nullen enthält. Der Eintrag \(t\) speichert, wie viele verschiedene Laminas genau \(t\) Steine verbrauchen.
Die äußere Schleife beginnt bei \(o=3\), dem kleinsten Quadrat, das überhaupt ein positives inneres Loch umschließen kann, und läuft solange \(4o-4\le L\) gilt. Für jede äußere Seitenlänge startet die innere Seitenlänge bei \(o-2\) und sinkt jeweils um \(2\), wodurch die Paritätsbedingung automatisch erhalten bleibt.
Für jedes Paar \((o,i)\) berechnet die Implementierung \(t=o^2-i^2\). Gilt \(t\le L\), wird der passende Häufigkeitseintrag erhöht. Gilt \(t>L\), endet die innere Schleife sofort, weil die Monotonie aus dem mathematischen Teil zeigt, dass spätere innere Werte nur noch größere Steinzahlen erzeugen würden.
Die Doppelschleife ist daher keine blinde Brute-Force-Suche, sondern eine strukturierte Enumeration des exakt zulässigen Zustandsraums.
Nach der Enumeration wird das Häufigkeitsfeld einmal von \(1\) bis \(L\) durchlaufen. Jede Steinzahl, deren Häufigkeit zwischen \(1\) und der erlaubten Obergrenze liegt, wird mitgezählt. In der Project-Euler-Instanz ist diese Obergrenze \(10\), also zählen die Programme Steinzahlen mit genau einem bis zehn verschiedenen Rahmen.
Die C++-Version erlaubt zusätzlich veränderliche Grenzwerte, doch die mathematische Methode ist in allen drei Sprachen dieselbe.
Sei \(A(L)\) die Anzahl der zulässigen Paare \((o,i)\) mit \(o^2-i^2\le L\). Die Enumerationsphase besucht jedes solche Paar genau einmal und benötigt daher \(O(A(L))\) Zeit. Der abschließende Durchlauf über das Häufigkeitsfeld kostet weitere \(O(L)\).
Damit ergibt sich insgesamt
$$O(A(L)+L)$$
Zeit und
$$O(L)$$
Speicher, weil das Feld der Länge \(L+1\) die dominierende Datenstruktur ist. Für \(L=10^6\) ist das problemlos praktikabel: Die Lösung reduziert die Aufgabe auf einen einzigen Zähldurchlauf über alle zulässigen Laminas und eine lineare Auswertung.
Boşluklu kare lamina, kare biçimli bir çerçevedir: dışta kenarı \(o\) olan bir kare, merkezde kenarı \(i\) olan daha küçük bir kare boşluğu çevreler. Kullanılan karo sayısı alan farkı olan \(o^2-i^2\) değeridir. Boşluğun tam merkezde kalması ve çerçeve kalınlığının tam sayı olması için \(o\) ile \(i\) aynı paritede olmalı ve \(o-i\ge2\) sağlanmalıdır.
Her \(t\le 10^6\) karo sayısı için \(N(t)\), tam \(t\) karo kullanan farklı lamina sayısı olsun; burada farklı dış/iç kenar çiftleri farklı yerleşimler sayılır. İstenen şey, şu koşulu sağlayan karo sayılarının adedidir:
$$1\le N(t)\le 10.$$
Uygulamalar uygun karo sayılarını doğrudan karakterize etmeye çalışmaz. Bunun yerine her geçerli laminayı tam bir kez üretir, her karo toplamı için kaç farklı üretim olduğunu sayar ve en sonda çokluğu 1 ile 10 arasında kalan toplamları sayar. Dolayısıyla matematik, geçerli durum uzayını doğru tanımlamak ve döngülerin onu eksiksiz ve tekrarsız taradığını göstermek üzerinedir.
Her lamina, \(o>i\ge1\), \(o\equiv i\pmod2\) koşullarını sağlayan bir \((o,i)\) çiftiyle belirlenir ve karo sayısı
$$T(o,i)=o^2-i^2=(o-i)(o+i)$$
şeklindedir. Çerçeve kalınlığını \(k=(o-i)/2\ge1\) diye yazarsak \(o=i+2k\) olur ve aynı ifade
$$T(o,i)=4k(i+k)$$
biçimine dönüşür. Bu yazım iki önemli değişmezi açık eder: her geçerli karo sayısı \(4\)'ün katıdır ve her farklı yerleşim tam olarak belirli bir \((o,i)\) çiftine, yani belirli bir iç kare ile kalınlığa karşılık gelir.
Sabit bir \(o\) dış kenarı için mümkün olan en küçük lamina, en ince olanıdır; bu da \(i=o-2\) seçimidir. Bu durumda karo sayısı
$$T_{\min}(o)=o^2-(o-2)^2=4o-4$$
olur. Eğer bu minimum bile limit \(L\)'yi aşıyorsa, aynı dış kenar uzunluğu için başka hiçbir lamina katkı veremez. O hâlde yalnızca
$$4o-4\le L$$
koşulunu sağlayan dış kareleri dolaşmak gerekir. Dış döngünün durma koşulu tam olarak budur.
\(o\) sabitken boşluğun merkezde kalması için \(i\), \(o\) ile aynı paritede kalmalıdır. Bu yüzden geçerli iç kenarlar
$$i=o-2,\ o-4,\ o-6,\dots$$
şeklindedir ve uygun paritedeki en küçük pozitif değere kadar iner. Bu bir programlama kolaylığı değildir; geçerli bütün laminanın tam aritmetik tarifidir. Her yasal kare çerçeve listede tam bir kez görünür, yarım karo kalınlığına karşılık gelen imkansız durumlar ise hiç üretilmez.
Sabit \(o\) için \(i\) küçüldükçe boşluk küçülür, çerçeve kalınlaşır ve karo sayısı artar. Kodun kullandığı açık özdeşlik şudur:
$$T(o,i-2)-T(o,i)=\bigl(o^2-(i-2)^2\bigr)-\bigl(o^2-i^2\bigr)=4(i-1)\gt0.$$
Dolayısıyla sabit bir dış kare için karo sayıları iç döngü ilerledikçe sıkı biçimde artar. Bir \(i\) değeri için \(T(o,i)>L\) olduğunda, aynı döngüde daha sonra gelecek tüm iç kenarlar da limiti aşacaktır. Bu yüzden anında `break` yapılması matematiksel olarak tam doğrudur.
Şimdi
$$N(t)=\#\{(o,i): o>i\ge1,\ o\equiv i\pmod2,\ o^2-i^2=t\}$$
tanımını yapalım. Çift döngü doğrudan bu fonksiyonu hesaplar. Her geçerli \((o,i)\) çifti, ürettiği \(t=T(o,i)\) toplamının frekansını bir artırır. Tüm sayım tamamlandıktan sonra aranan cevap yalnızca
$$\#\{t\le L:1\le N(t)\le10\}$$
olur. Yani Problem 174, laminanın sayısını değil, az sayıda farklı biçimde elde edilebilen karo toplamlarının sayısını sorar.
\(32\) karo sayısı, neden bir frekans tablosuna ihtiyaç duyulduğunu iyi gösterir. Şunlar vardır:
$$6^2-2^2=36-4=32,$$
ve ayrıca
$$9^2-7^2=81-49=32.$$
Her iki çift de parite koşulunu sağlar ve farklı laminaları temsil eder; dolayısıyla \(N(32)=2\) olur. Tarama sırasında uygulamalar bu iki çifti ayrı ayrı görür ve aynı sayaç hücresini iki kez artırır. Son sayaç değeri \(1\) ile \(10\) arasında kalan her karo sayısı, nihai yanıta bir katkı yapar.
C++, Python ve Java uygulamaları önce uzunluğu \(L+1\) olan ve başlangıçta sıfırlardan oluşan bir dizi ayırır. \(t\) indisindeki değer, tam \(t\) karo kullanan farklı laminaların sayısını tutar.
Dış döngü, pozitif bir iç boşluğu çevreleyebilen en küçük dış kare olan \(o=3\) ile başlar ve \(4o-4\le L\) kaldığı sürece devam eder. Her dış kenar için iç kenar \(o-2\)'den başlar ve her seferinde \(2\) azalır; böylece parite koşulu otomatik olarak korunur.
Her \((o,i)\) çifti için uygulama \(t=o^2-i^2\) hesabını yapar. Eğer \(t\le L\) ise ilgili frekans artırılır. Eğer \(t>L\) ise iç döngü hemen durdurulur; çünkü yukarıdaki monotonluk hesabı, bundan sonraki tüm \(i\) değerlerinin daha da büyük karo toplamları vereceğini garanti eder.
Bu nedenle görünen çift döngü gelişi güzel bir kaba kuvvet değildir; geçerli durum uzayının yapılandırılmış ve erken durmalı bir taramasıdır.
Tüm laminalar üretildikten sonra frekans dizisi \(1\)'den \(L\)'ye kadar bir kez taranır. Frekansı \(1\) ile izin verilen üst sınır arasında olan her karo toplamı sayılır. Project Euler örneğinde bu üst sınır \(10\) olduğundan, program bir ile on farklı yerleşimi olan karo toplamlarını sayar.
C++ sürümü limit ve üst sınırın değişmesine de izin verir; ancak üç dilde de kullanılan matematiksel yöntem aynıdır.
\(A(L)\), \(o^2-i^2\le L\) koşulunu sağlayan geçerli \((o,i)\) çiftlerinin sayısı olsun. Sayım aşaması her böyle çifti tam bir kez ziyaret ettiği için \(O(A(L))\) zamanda çalışır. Son frekans taraması da ek olarak \(O(L)\) zaman alır.
Böylece toplam süre
$$O(A(L)+L)$$
ve bellek kullanımı
$$O(L)$$
olur; çünkü baskın veri yapısı uzunluğu \(L+1\) olan frekans dizisidir. \(L=10^6\) için bu yaklaşım pratiktir: problem bir tarama ve bir doğrusal sayım aşamasına indirgenir.
Una lamina cuadrada hueca es un marco cuadrado: un cuadrado exterior de lado \(o\) rodea un hueco cuadrado concéntrico más pequeño de lado \(i\). El número de baldosas usadas es la diferencia de áreas \(o^2-i^2\). Para que el hueco quede centrado con un grosor entero, \(o\) e \(i\) deben tener la misma paridad y satisfacer \(o-i\ge2\).
Para cada total de baldosas \(t\le 10^6\), sea \(N(t)\) el número de laminae distintas que usan exactamente \(t\) baldosas, contando como distintas las parejas diferentes de lado exterior e interior. Hay que contar cuántos valores de \(t\) cumplen
$$1\le N(t)\le 10.$$
Las implementaciones no intentan adivinar directamente qué totales de baldosas son válidos. En lugar de eso, enumeran cada lamina legal exactamente una vez, registran cuántas veces aparece cada total y solo al final cuentan los totales cuya multiplicidad está entre uno y diez. Por eso la parte matemática consiste en describir correctamente el espacio de estados y justificar que los bucles lo recorren sin duplicados ni omisiones.
Cada lamina queda determinada por una pareja \((o,i)\) con \(o>i\ge1\), \(o\equiv i\pmod2\), y número de baldosas
$$T(o,i)=o^2-i^2=(o-i)(o+i).$$
Si escribimos el grosor del marco como \(k=(o-i)/2\ge1\), entonces \(o=i+2k\) y la misma cantidad se convierte en
$$T(o,i)=4k(i+k).$$
Esta forma muestra dos invariantes útiles. Primero, todo total admisible es múltiplo de \(4\). Segundo, una disposición distinta es exactamente una elección distinta del cuadrado interior y del grosor, o de forma equivalente una pareja distinta \((o,i)\).
Para un lado exterior fijo \(o\), la lamina más pequeña posible es la más delgada, obtenida con \(i=o-2\). Su número de baldosas es
$$T_{\min}(o)=o^2-(o-2)^2=4o-4.$$
Si incluso este mínimo ya supera el límite \(L\), entonces ningún marco con ese lado exterior puede contribuir. Por tanto solo hay que considerar los valores que satisfacen
$$4o-4\le L.$$
Esa es exactamente la condición de parada del bucle exterior.
Una vez fijado \(o\), el hueco debe permanecer concéntrico, así que \(i\) debe conservar la misma paridad que \(o\). Los valores válidos del lado interior son entonces
$$i=o-2,\ o-4,\ o-6,\dots$$
hasta el menor valor positivo con la paridad correcta. Esto no es un detalle accidental de implementación: es la descripción exacta de todas las laminae legales. Cada marco cuadrado válido aparece una sola vez, y nunca se generan grosores imposibles de media baldosa.
Para un \(o\) fijo, al disminuir \(i\) el hueco se hace más pequeño y el marco más grueso, así que el número de baldosas aumenta estrictamente. La identidad utilizada por el código es
$$T(o,i-2)-T(o,i)=\bigl(o^2-(i-2)^2\bigr)-\bigl(o^2-i^2\bigr)=4(i-1)\gt0.$$
Por lo tanto, una vez que cierto valor de \(i\) produce \(T(o,i)>L\), todos los valores posteriores del mismo bucle también excederán el límite. Por eso es correcto interrumpir el bucle interior en ese punto.
Definimos
$$N(t)=\#\{(o,i): o>i\ge1,\ o\equiv i\pmod2,\ o^2-i^2=t\}.$$
El doble bucle calcula esta función directamente. Cada pareja admisible \((o,i)\) añade una unidad a la frecuencia del total \(t=T(o,i)\). Cuando termina la enumeración, la respuesta pedida es simplemente
$$\#\{t\le L:1\le N(t)\le10\}.$$
Así, el problema no pide cuántas laminae existen en total, sino cuántos totales de baldosas pueden realizarse de pocas maneras distintas.
El valor \(32\) es un buen ejemplo de por qué hace falta una tabla de frecuencias. Tenemos
$$6^2-2^2=36-4=32,$$
y también
$$9^2-7^2=81-49=32.$$
Ambas parejas cumplen la condición de paridad y describen laminae diferentes, luego \(N(32)=2\). Durante el recorrido, las implementaciones encuentran ambas configuraciones por separado e incrementan dos veces la misma entrada de frecuencia. Todo total cuyo contador final quede entre \(1\) y \(10\) aporta uno al resultado final.
Las implementaciones en C++, Python y Java reservan un arreglo de longitud \(L+1\), inicialmente lleno de ceros. La entrada \(t\) guarda cuántas laminae distintas usan exactamente \(t\) baldosas.
El bucle exterior comienza en \(o=3\), el menor cuadrado que puede rodear un hueco interior positivo, y continúa mientras \(4o-4\le L\). Para cada lado exterior, el lado interior empieza en \(o-2\) y disminuye de \(2\) en \(2\), manteniendo automáticamente la paridad correcta.
Para cada pareja \((o,i)\), la implementación calcula \(t=o^2-i^2\). Si \(t\le L\), incrementa la frecuencia correspondiente. Si \(t>L\), el bucle interior se detiene de inmediato, porque el argumento de monotonía demuestra que los siguientes valores de \(i\) producirían aún más baldosas.
Por eso el doble bucle no es una fuerza bruta ciega, sino una enumeración exacta del espacio permitido con una salida temprana plenamente justificada.
Después de generar todas las laminae, la implementación recorre la tabla de frecuencias desde \(1\) hasta \(L\). Se cuenta cada total cuya frecuencia cae entre \(1\) y el máximo permitido. En la instancia de Project Euler ese máximo es \(10\), de modo que el programa cuenta los totales de baldosas con entre una y diez disposiciones distintas.
La versión en C++ además permite variar el límite y la multiplicidad máxima, pero la estrategia matemática es la misma en los tres lenguajes.
Sea \(A(L)\) el número de parejas admisibles \((o,i)\) con \(o^2-i^2\le L\). La fase de enumeración visita cada una exactamente una vez, así que cuesta \(O(A(L))\) tiempo. El recorrido final de la tabla añade otros \(O(L)\).
En consecuencia, el tiempo total es
$$O(A(L)+L),$$
mientras que la memoria usada es
$$O(L),$$
porque la estructura dominante es el arreglo de frecuencias de tamaño \(L+1\). Para \(L=10^6\), esto resulta perfectamente manejable.
空心方形 lamina 可以看成一个正方形边框：边长为 \(o\) 的外层正方形包围着一个边长为 \(i\) 的同心内层正方形空洞。它所使用的瓷砖数就是面积差 \(o^2-i^2\)。为了让空洞保持居中且边框宽度为整数，\(o\) 与 \(i\) 必须同奇同偶，并且满足 \(o-i\ge2\)。
对每一个 \(t\le 10^6\)，记 \(N(t)\) 为恰好使用 \(t\) 块瓷砖的不同 lamina 数量；只要外层和内层边长不同，就算不同的排列。题目要求统计满足
$$1\le N(t)\le 10$$
的瓷砖总数 \(t\) 有多少个。
三个实现都没有尝试直接从 \(t\) 反推它能否形成多少种 lamina。它们采用的办法更直接：把所有合法的同心正方形对 \((o,i)\) 各枚举一次，为对应的瓷砖总数做频次累加，然后再统计哪些总数的出现次数落在 1 到 10 之间。因此，真正需要说明的是：合法对象到底是什么，循环为什么恰好遍历了所有合法对象，而且不会重复。
每一个 lamina 都对应一个二元组 \((o,i)\)，其中 \(o>i\ge1\)、\(o\equiv i\pmod2\)，并且所需瓷砖数为
$$T(o,i)=o^2-i^2=(o-i)(o+i).$$
如果把边框厚度写成 \(k=(o-i)/2\ge1\)，也就是 \(o=i+2k\)，那么同一个数量还可以写成
$$T(o,i)=4k(i+k).$$
这个改写非常有用。第一，它立刻告诉我们所有合法的瓷砖总数都一定是 \(4\) 的倍数。第二，它说明“不同排列”其实就是“不同的内层边长与厚度组合”，等价地说，就是不同的 \((o,i)\) 对。
对于固定的外层边长 \(o\)，最省砖的情况一定是最薄的一圈，也就是内层边长取 \(i=o-2\)。这时的瓷砖数为
$$T_{\min}(o)=o^2-(o-2)^2=4o-4.$$
如果连这个最小值都已经大于上限 \(L\)，那么同样的外层边长下，任何更厚的边框都会更大，自然不可能再有合法方案。于是外层循环只需要处理满足
$$4o-4\le L$$
的那些 \(o\)。这正是实现中外层循环的停止条件。
一旦外层边长 \(o\) 固定，为了保持同心且边框厚度为整数，内层边长 \(i\) 必须与 \(o\) 同奇同偶。因此合法的内层边长序列必然是
$$i=o-2,\ o-4,\ o-6,\dots$$
一直减到同奇偶性的最小正整数为止。这里每次减 2 并不是编码上的巧合，而是题目几何约束的精确算术表达。这样遍历时，每个合法 lamina 恰好出现一次，而所有不可能的“半格宽边框”情况都会被自动排除。
对固定的 \(o\) 来说，\(i\) 越小，内层空洞越小，边框越厚，所以瓷砖数一定越大。实现依赖的关键等式是
$$T(o,i-2)-T(o,i)=\bigl(o^2-(i-2)^2\bigr)-\bigl(o^2-i^2\bigr)=4(i-1)\gt0.$$
这说明在固定外层边长的一次扫描中，随着内层边长不断减小，瓷砖数是严格递增的。因此，一旦某个 \(i\) 已经给出了 \(T(o,i)>L\)，后面更小的内层边长只会产生更大的值，完全没有继续检查的必要，这就是内层循环可以立刻停止的数学理由。
定义
$$N(t)=\#\{(o,i): o>i\ge1,\ o\equiv i\pmod2,\ o^2-i^2=t\}.$$
双重循环实际上就是在直接构造这个函数。每当找到一个满足 \(T(o,i)\le L\) 的合法二元组 \((o,i)\)，对应的频次数组位置就加一。所有枚举结束后，题目真正要求的就是
$$\#\{t\le L:1\le N(t)\le10\}.$$
换句话说，本题不是在问“总共有多少个 lamina”，而是在问“有多少种瓷砖总数，能够由 1 到 10 种不同的 lamina 形成”。
\(32\) 是一个很好的例子，因为它对应不止一种形状。我们有
$$6^2-2^2=36-4=32,$$
同时也有
$$9^2-7^2=81-49=32.$$
这两组边长都满足同奇同偶条件，而且表示的是不同的 lamina，所以 \(N(32)=2\)。程序在枚举时会分别遇到这两组 \((o,i)\)，并把同一个频次位置加两次。最终频次介于 1 和 10 之间的每个 \(t\)，都会为答案贡献 1。
C++、Python 和 Java 实现都会先分配一个长度为 \(L+1\) 的数组，并全部初始化为 0。数组下标 \(t\) 表示“恰好用 \(t\) 块瓷砖的 lamina 有多少种”。
外层循环从 \(o=3\) 开始，因为这是最小的、还能包住一个正面积内洞的外层正方形。只要 \(4o-4\le L\) 仍然成立，循环就继续进行。对每个外层边长，内层边长从 \(o-2\) 开始，每次减去 2，这样就自动保证了奇偶性条件。
对每一组 \((o,i)\)，实现都会计算 \(t=o^2-i^2\)。如果 \(t\le L\)，就把频次数组的对应位置加一；如果 \(t>L\)，内层循环立即结束，因为上面的单调性证明已经说明，后续更小的 \(i\) 只会产生更大的瓷砖总数。
因此，这个看起来很简单的双循环其实并不是“盲目试遍所有组合”，而是对合法状态空间的一次精确枚举，并且在每个固定外层边长上都带有严格正确的提前终止。
所有 lamina 枚举完成后，程序再从 \(1\) 扫描到 \(L\)。凡是频次落在 \(1\) 到允许上界之间的总数都会被计入答案。在 Project Euler 174 中，这个上界就是 \(10\)，所以最终统计的是恰好有 1 到 10 种不同构造方式的瓷砖总数。
C++ 版本还允许把上限和最大类型数设成别的值，但三种语言实现的核心数学逻辑完全相同。
设 \(A(L)\) 表示满足 \(o^2-i^2\le L\) 的合法二元组 \((o,i)\) 的数量。枚举阶段恰好访问每个这样的二元组一次，所以这部分时间复杂度是 \(O(A(L))\)。最后对频次数组做一次线性扫描，需要 \(O(L)\) 时间。
因此总时间复杂度为
$$O(A(L)+L),$$
空间复杂度为
$$O(L),$$
因为主导数据结构就是长度为 \(L+1\) 的频次数组。对 \(L=10^6\) 这个规模来说，这样的做法完全可行。
Полая квадратная ламина представляет собой квадратную рамку: внешний квадрат со стороной \(o\) окружает меньшую концентрическую квадратную пустоту со стороной \(i\). Число использованных плиток равно разности площадей \(o^2-i^2\). Чтобы отверстие оставалось по центру, а толщина рамки была целым числом, стороны \(o\) и \(i\) должны иметь одинаковую четность и удовлетворять условию \(o-i\ge2\).
Для каждого числа плиток \(t\le 10^6\) обозначим через \(N(t)\) количество различных ламин, использующих ровно \(t\) плиток; разные пары внешней и внутренней стороны считаются разными конфигурациями. Нужно посчитать, для скольких \(t\) выполнено
$$1\le N(t)\le 10.$$
Реализации не пытаются напрямую угадывать, какие значения \(t\) встречаются нужное число раз. Вместо этого они перечисляют каждую допустимую ламину ровно один раз, увеличивают счетчик соответствующего числа плиток, а потом просто смотрят, какие значения появились от одного до десяти раз. Поэтому основная математика здесь состоит в точном описании допустимых пар \((o,i)\) и в обосновании того, что циклы обходят их без пропусков и повторов.
Каждая ламина задается парой \((o,i)\), где \(o>i\ge1\), \(o\equiv i\pmod2\), а число плиток равно
$$T(o,i)=o^2-i^2=(o-i)(o+i).$$
Если обозначить толщину рамки через \(k=(o-i)/2\ge1\), то \(o=i+2k\), и та же формула принимает вид
$$T(o,i)=4k(i+k).$$
В этой записи сразу видны два инварианта. Во-первых, любое допустимое число плиток кратно \(4\). Во-вторых, различная конфигурация ламины - это в точности различный выбор внутренней стороны и толщины, то есть различная пара \((o,i)\).
При фиксированном значении \(o\) наименьшая возможная ламина получается у самой тонкой рамки, то есть при \(i=o-2\). Тогда
$$T_{\min}(o)=o^2-(o-2)^2=4o-4.$$
Если уже это минимальное значение превосходит предел \(L\), то никакая ламина с такой внешней стороной больше не подойдет. Следовательно, нужно рассматривать только те \(o\), для которых
$$4o-4\le L.$$
Именно это условие используется во внешнем цикле.
Когда внешняя сторона \(o\) фиксирована, отверстие должно оставаться концентрическим, а значит \(i\) обязана иметь ту же четность, что и \(o\). Поэтому допустимые внутренние стороны образуют последовательность
$$i=o-2,\ o-4,\ o-6,\dots$$
до наименьшего положительного значения нужной четности. Это не случайный прием программирования, а точное перечисление всех допустимых квадратных рамок. Каждая легальная ламина встречается ровно один раз, а невозможные полуцелые толщины даже не рассматриваются.
Для фиксированного \(o\) уменьшение \(i\) делает отверстие меньше, а рамку толще, поэтому число плиток строго растет. Код опирается на тождество
$$T(o,i-2)-T(o,i)=\bigl(o^2-(i-2)^2\bigr)-\bigl(o^2-i^2\bigr)=4(i-1)\gt0.$$
Значит, как только некоторое значение \(i\) дало \(T(o,i)>L\), все последующие значения внутри того же цикла также превысят предел. Поэтому немедленный выход из внутреннего цикла полностью обоснован математически.
Введем
$$N(t)=\#\{(o,i): o>i\ge1,\ o\equiv i\pmod2,\ o^2-i^2=t\}.$$
Именно эту функцию и строит двойной цикл. Каждая допустимая пара \((o,i)\) увеличивает счетчик того значения \(t=T(o,i)\), которое она порождает. После завершения перечисления ответ имеет вид
$$\#\{t\le L:1\le N(t)\le10\}.$$
Иными словами, задача спрашивает не количество самих ламин, а количество таких чисел плиток, которые можно получить небольшим числом различных способов.
Значение \(32\) хорошо показывает, зачем нужен массив частот. Имеем
$$6^2-2^2=36-4=32,$$
а также
$$9^2-7^2=81-49=32.$$
Обе пары удовлетворяют условию четности и описывают разные ламины, значит \(N(32)=2\). Во время перебора реализации встретят обе пары отдельно и дважды увеличат один и тот же счетчик. Любое значение \(t\), чей итоговый счетчик лежит между \(1\) и \(10\), добавляет единицу к ответу.
Реализации на C++, Python и Java создают массив длины \(L+1\), заполненный нулями. Элемент с индексом \(t\) хранит число различных ламин, использующих ровно \(t\) плиток.
Внешний цикл начинается с \(o=3\), то есть с минимального квадрата, который еще может окружать положительное внутреннее отверстие, и продолжается, пока выполняется \(4o-4\le L\). Для каждого внешнего квадрата внутренняя сторона стартует с \(o-2\) и уменьшается на \(2\), автоматически сохраняя нужную четность.
Для каждой пары \((o,i)\) программа вычисляет \(t=o^2-i^2\). Если \(t\le L\), соответствующая частота увеличивается. Если \(t>L\), внутренний цикл немедленно завершается, поскольку доказанная выше монотонность гарантирует, что более поздние значения \(i\) дадут только еще большие числа плиток.
Поэтому двойной цикл не является бессистемным перебором: это точное перечисление допустимого пространства состояний с корректным ранним выходом.
После перечисления всех ламин код один раз проходит массив частот от \(1\) до \(L\). Каждое значение, чья частота лежит между \(1\) и заданной верхней границей, учитывается в ответе. В задаче Project Euler эта верхняя граница равна \(10\), так что программа считает числа плиток с одной, двумя, ..., десятью различными конфигурациями.
Версия на C++ дополнительно позволяет менять предел и максимальную кратность, но математический алгоритм во всех трех языках одинаков.
Пусть \(A(L)\) обозначает число допустимых пар \((o,i)\), для которых \(o^2-i^2\le L\). Фаза перечисления посещает каждую такую пару ровно один раз, поэтому занимает \(O(A(L))\) времени. Заключительный проход по массиву частот добавляет еще \(O(L)\).
Следовательно, полная временная сложность равна
$$O(A(L)+L),$$
а потребление памяти равно
$$O(L),$$
поскольку доминирующей структурой данных является массив частот размера \(L+1\). Для \(L=10^6\) такая схема легко укладывается в практические ограничения.
الـ lamina المربعة المجوفة هي إطار مربع: مربع خارجي طول ضلعه \(o\) يحيط بفتحة مربعة متراكزة أصغر طول ضلعها \(i\). عدد البلاطات المستخدمة يساوي فرق المساحتين \(o^2-i^2\). ولكي تبقى الفتحة في المركز ويكون عرض الإطار عددًا صحيحًا، يجب أن يكون \(o\) و\(i\) من نفس الزوجية وأن يحققا \(o-i\ge2\).
لكل عدد بلاطات \(t\le 10^6\)، لنرمز بـ \(N(t)\) إلى عدد الأشكال المختلفة التي تستخدم بالضبط \(t\) بلاطات، مع اعتبار كل زوج مختلف من الضلع الخارجي والداخلي ترتيبًا مختلفًا. المطلوب هو عدّ قيم \(t\) التي تحقق
$$1\le N(t)\le 10.$$
التنفيذات لا تحاول وصف قيم \(t\) المناسبة مباشرة. الفكرة الأبسط والأدق هي تعداد كل lamina صالحة مرة واحدة فقط، ثم زيادة عداد مجموع البلاطات الموافق لها، وبعد ذلك حساب القيم التي ظهر لها ما بين ترتيب واحد وعشرة ترتيبات. لذلك فإن لبّ البرهان الرياضي هنا هو تحديد فضاء الحالات المسموح بدقة، وشرح لماذا تمر الحلقات على كل حالة صالحة مرة واحدة من دون تكرار أو سهو.
كل lamina توصف بزوج \((o,i)\) يحقق \(o>i\ge1\) و\(o\equiv i\pmod2\)، ويكون عدد البلاطات فيها
$$T(o,i)=o^2-i^2=(o-i)(o+i).$$
إذا كتبنا سماكة الإطار على صورة \(k=(o-i)/2\ge1\)، أي \(o=i+2k\)، فإن نفس الكمية تصبح
$$T(o,i)=4k(i+k).$$
هذه الصياغة تكشف حقيقتين مهمتين فورًا. الأولى أن كل عدد بلاطات صالح هو مضاعف لـ \(4\). والثانية أن كل ترتيب مختلف يقابل بالضبط اختيارًا مختلفًا لطول الضلع الداخلي والسماكة، أو بصورة مكافئة زوجًا مختلفًا \((o,i)\).
عند تثبيت الضلع الخارجي \(o\)، فإن أصغر lamina ممكنة هي الأرفع، أي عندما يكون \(i=o-2\). عندها يكون عدد البلاطات
$$T_{\min}(o)=o^2-(o-2)^2=4o-4.$$
إذا كان هذا الحد الأدنى نفسه أكبر من السقف \(L\)، فلن توجد أي lamina بهذا الضلع الخارجي يمكنها أن تدخل في العد. لذا يكفي أن نفحص القيم التي تحقق
$$4o-4\le L.$$
وهذا بالتحديد هو شرط التوقف المستخدم في الحلقة الخارجية.
بعد تثبيت \(o\)، يجب أن تبقى الفتحة متراكزة، وهذا يفرض أن يحافظ \(i\) على نفس زوجية \(o\). لذلك تكون القيم الصالحة للضلع الداخلي على الصورة
$$i=o-2,\ o-4,\ o-6,\dots$$
حتى أصغر قيمة موجبة من نفس الزوجية. هذا ليس تفصيلًا برمجيًا عابرًا، بل هو الوصف الحسابي الدقيق لكل lamina قانونية. كل إطار مربع صالح يظهر مرة واحدة بالضبط، ولا تُولَّد أي حالات مستحيلة ذات سماكة نصف بلاطة.
عند تثبيت \(o\)، فإن تصغير \(i\) يجعل الفتحة أصغر والإطار أسمك، ولذلك يزداد عدد البلاطات ازديادًا صارمًا. الهوية التي تعتمد عليها الشيفرة هي
$$T(o,i-2)-T(o,i)=\bigl(o^2-(i-2)^2\bigr)-\bigl(o^2-i^2\bigr)=4(i-1)\gt0.$$
إذن، ما إن تعطي قيمة ما من \(i\) عددًا أكبر من \(L\)، فإن كل القيم اللاحقة في الحلقة نفسها ستعطي أعدادًا أكبر أيضًا. لهذا السبب يكون إيقاف الحلقة الداخلية فورًا قرارًا صحيحًا رياضيًا، لا مجرد تحسين تجريبي.
لنعرّف
$$N(t)=\#\{(o,i): o>i\ge1,\ o\equiv i\pmod2,\ o^2-i^2=t\}.$$
الحلقة المزدوجة تبني هذه الدالة مباشرة. كل زوج صالح \((o,i)\) يزيد تكرار القيمة \(t=T(o,i)\) بمقدار واحد. وبعد انتهاء التعداد تصبح الإجابة المطلوبة هي
$$\#\{t\le L:1\le N(t)\le10\}.$$
بعبارة أخرى، المسألة لا تسأل عن عدد الأشكال نفسها، بل عن عدد قيم البلاطات التي يمكن تحقيقها بعدد صغير من الأشكال المختلفة.
القيمة \(32\) مثال جيد يوضح لماذا نحتاج إلى جدول تكرارات. لدينا
$$6^2-2^2=36-4=32,$$
وكذلك
$$9^2-7^2=81-49=32.$$
كلا الزوجين يحقق شرط الزوجية ويمثل lamina مختلفًا، وبالتالي \(N(32)=2\). أثناء التعداد ستصادف التنفيذات هذين الزوجين كلًّا على حدة، وستزيد الخانة نفسها في جدول التكرارات مرتين. وكل قيمة ينتهي عدادها بين \(1\) و\(10\) تضيف واحدًا إلى الجواب النهائي.
تنشئ تطبيقات C++ وPython وJava مصفوفة طولها \(L+1\) مملوءة بالأصفار في البداية. الخانة ذات الفهرس \(t\) تخزن عدد الأشكال المختلفة التي تستخدم بالضبط \(t\) بلاطات.
تبدأ الحلقة الخارجية من \(o=3\)، وهو أصغر مربع يمكنه أن يحيط بفتحة داخلية موجبة المساحة، وتستمر ما دام \(4o-4\le L\). ولكل ضلع خارجي، يبدأ الضلع الداخلي من \(o-2\) ثم ينقص بمقدار \(2\) في كل مرة، وبذلك يُحفَظ شرط الزوجية تلقائيًا.
لكل زوج \((o,i)\)، تحسب الشيفرة \(t=o^2-i^2\). إذا كان \(t\le L\)، تزيد التكرار الموافق. وإذا كان \(t>L\)، تتوقف الحلقة الداخلية مباشرة، لأن برهان الرتابة أعلاه يضمن أن القيم التالية من \(i\) ستنتج أعداد بلاطات أكبر لا أصغر.
لذلك فالحلقة المزدوجة ليست بحثًا أعمى بالقوة الغاشمة، بل تعدادًا منظمًا ودقيقًا لفضاء الحالات المسموح به مع شرط توقف مبكر مبرهن.
بعد الانتهاء من توليد جميع الأشكال، تمسح الشيفرة جدول التكرارات من \(1\) إلى \(L\). كل قيمة يقع تكرارها بين \(1\) والحد الأعلى المسموح به تُحتسب ضمن الجواب. في مسألة Project Euler يكون هذا الحد الأعلى هو \(10\)، لذلك تُحصى أعداد البلاطات التي لها من ترتيب واحد إلى عشرة ترتيبات مختلفة.
نسخة C++ تسمح أيضًا بتغيير الحد الأعلى وحدّ البلاطات، لكن الفكرة الرياضية الأساسية واحدة في اللغات الثلاث.
لنرمز بـ \(A(L)\) إلى عدد الأزواج الصالحة \((o,i)\) التي تحقق \(o^2-i^2\le L\). مرحلة التعداد تزور كل زوج من هذه الأزواج مرة واحدة فقط، ولذلك زمنها \(O(A(L))\). ثم تضيف عملية المسح النهائية لجدول التكرارات زمنًا قدره \(O(L)\).
إذًا يكون الزمن الكلي
$$O(A(L)+L),$$
أما الذاكرة فهي
$$O(L),$$
لأن البنية المسيطرة هي مصفوفة التكرارات ذات الطول \(L+1\). وعند \(L=10^6\) يكون هذا النهج عمليًا تمامًا.