Problem 983 asks for the smallest squared radius \(R(n)^2\) that allows a sufficiently large consonant family of equal circles. The implementations realize the configuration on the integer lattice: every chosen direction is a lattice point on the circle \(x^2+y^2=R(n)^2\), the actual circle centers are built from subset sums of those directions, and every nontrivial crossing of the chosen circles must occur at one of the designated crossing points produced by the same subset-sum construction.
The key simplification is that the code does not search directly for \(n\) unrelated circles. Instead it builds two parity classes of subset sums, one class for circle centers and one class for allowed crossings. If \(d\) directions are chosen, each parity class contains \(2^{d-1}\) points, so for \(n>2\) the search dimension is
$$d=\min\{t\ge 1:2^{t-1}\ge n\}.$$
The answer is then found by increasing \(m=1,2,3,\dots\) until the circle \(x^2+y^2=m\) supports such a \(d\)-direction construction.
The whole method is built around equal-radius lattice vectors, subset sums, and a sharp characterization of which circle crossings are legitimate.
For \(n\le 2\), the problem is trivial and the implementations immediately return \(R(n)^2=1\). For larger \(n\), the construction uses \(d\) selected vectors \(v_1,\dots,v_d\), all with the same squared length \(m\). From them it forms the two parity classes
$$E=\left\{\sum_{i\in A} v_i:\ |A|\equiv 0 \pmod 2\right\},\qquad O=\left\{\sum_{i\in A} v_i:\ |A|\equiv 1 \pmod 2\right\}.$$
Here \(E\) is the family of circle centers actually counted by the search, while \(O\) is the family of crossing points that those circles are allowed to share. Both sets have size \(2^{d-1}\), which is why the least admissible \(d\) is the smallest one with \(2^{d-1}\ge n\).
Fix \(m\) and write
$$\Lambda_m=\{(x,y)\in\mathbb{Z}^2:x^2+y^2=m\}.$$
Every chosen direction must come from \(\Lambda_m\). Because \(v\) and \(-v\) generate the same geometric direction up to parity reversal, the search keeps only one representative from each antipodal pair \(\{v,-v\}\). Therefore \(m\) is immediately impossible if \(\Lambda_m\) contains fewer than \(d\) antipodal pairs.
The factorization test used in the implementations is the standard two-squares criterion. If
$$m=2^a\prod_i p_i^{\alpha_i}\prod_j q_j^{2\beta_j},\qquad p_i\equiv 1 \pmod 4,\quad q_j\equiv 3 \pmod 4,$$
then
$$|\Lambda_m|=4\prod_i(\alpha_i+1),\qquad \text{antipodal pairs}=\frac{|\Lambda_m|}{2}=2\prod_i(\alpha_i+1).$$
If any prime \(q\equiv 3 \pmod 4\) appears to an odd power, then \(\Lambda_m\) is empty and the search skips \(m\) at once.
Take any even subset sum \(e\in E\). If the subset defining \(e\) does not contain \(i\), then \(e+v_i\in O\); if it does contain \(i\), then \(e-v_i\in O\). Since every \(v_i\) lies on \(x^2+y^2=m\), each point of \(O\) produced this way lies on the circle of radius \(\sqrt m\) centered at \(e\). So every circle centered at a point of \(E\) comes with \(d\) intended crossing points from \(O\).
The same relation can be read backwards: every odd subset sum \(o\in O\) differs from \(d\) even subset sums by vectors in \(\Lambda_m\), so each odd point lies on \(d\) circles of the family. The subset-sum construction therefore creates a bipartite incidence pattern isomorphic to the \(d\)-dimensional cube: toggling one chosen vector changes parity and moves by exactly one lattice vector of length \(\sqrt m\).
The implementations require the map \(A\mapsto \sum_{i\in A}v_i\) to be injective separately on even subsets and on odd subsets. Equivalently, they reject any nontrivial relation
$$\sum_{i\in A}v_i=\sum_{i\in B}v_i\quad \text{with}\quad |A|\equiv |B|\pmod 2,\ A\ne B.$$
If such a collision existed inside \(E\), two circles that are supposed to be different would collapse to the same center. If it existed inside \(O\), two designated crossings would merge. This injectivity check is the first exact validation step performed after the directions have been chosen.
The deeper condition is that no point outside \(O\) may lie on two circles centered in \(E\). For an even center \(e\in E\) and a lattice vector \(u\in \Lambda_m\), consider the point \(z=e+u\), which certainly lies on the circle centered at \(e\). If \(z\in O\), then this is one of the intended crossings and it is allowed to belong to several circles. If \(z\notin O\), then the translated circle \(z+\Lambda_m\) must not hit a second point of \(E\). The exact condition checked by the code is
$$z\notin O\ \Longrightarrow\ |(z+\Lambda_m)\cap E|<2.$$
This is the decisive consonance test: every genuine multiple crossing of the chosen circles must come from the designated odd subset sums, and nowhere else.
To reject hopeless branches early, the implementations precompute
$$\Delta_m=\{a-b:\ a,b\in \Lambda_m,\ a\ne b\}.$$
If two even centers lie on the same translated radius-\(\sqrt m\) circle, then their difference belongs to \(\Delta_m\). Differences of even subset sums are signed sums of an even number of chosen directions. Two-term differences correspond to intended odd crossings, so the first genuinely dangerous obstructions arise from four selected directions. During depth-first search, every newly created 4-tuple is tested through the sixteen sums
$$\pm v_i\pm v_j\pm v_k\pm v_\ell,$$
and the branch is pruned as soon as a nonzero value lands in \(\Delta_m\). This is not the whole proof of validity, but it is an extremely effective necessary filter before the full subset-sum test.
For \(n=4\), the implementations need \(d=3\) because \(2^{3-1}=4\). Take \(m=5\), for which
$$\Lambda_5=\{(\pm 2,\pm 1),(\pm 1,\pm 2)\}.$$
Choose three representatives, for example
$$v_1=(2,1),\qquad v_2=(2,-1),\qquad v_3=(1,2).$$
Then the even subset sums are
$$E=\{(0,0),(4,0),(3,3),(3,1)\},$$
and the odd subset sums are
$$O=\{(2,1),(2,-1),(1,2),(5,2)\}.$$
So we obtain four circles of radius \(\sqrt 5\), centered at the points of \(E\). The circle centered at \((0,0)\) passes through \((2,1)\), \((2,-1)\), and \((1,2)\); the circle centered at \((4,0)\) passes through \((2,1)\), \((2,-1)\), and \((5,2)\); and similarly for the other two even centers. The odd points are exactly the intended shared crossings, and the full validation confirms that no other point lies on two of these four circles. That is why the checkpoint value is \(R(4)^2=5\).
The C++, Python, and Java implementations first convert \(n\) into the required dimension \(d\), with the trivial shortcut \(R(n)^2=1\) for \(n\le 2\). They then scan \(m=1,2,3,\dots\). For each \(m\), they use the prime-factorization formula above to count antipodal pairs quickly, and discard \(m\) immediately if there are fewer than \(d\) available directions.
When \(m\) survives the arithmetic filter, the implementations enumerate all lattice points on \(x^2+y^2=m\), collapse them into antipodal pairs, and keep one canonical representative from each pair. A depth-first search then tries all \(d\)-element choices of those representatives. The precomputed displacement set \(\Delta_m\) is used at every step: whenever a new 4-tuple already creates a forbidden signed sum, the branch is abandoned before any expensive subset-sum work is done.
The three languages use the same mathematical search. The C++ implementation additionally parallelizes the top-level DFS branches over the choice of the first representative, while the Python and Java implementations run the same search serially.
Once \(d\) directions have been selected, the implementations generate all \(2^d\) subset sums, split them into \(E\) and \(O\), and test injectivity inside each parity class. If that passes, they run the translated-circle condition \(z\notin O \Rightarrow |(z+\Lambda_m)\cap E|<2\). The first \(m\) that passes every test is returned, so by construction it is the minimal value \(R(n)^2\).
The built-in checkpoints confirm the first nontrivial cases \(R(2)^2=1\) and \(R(4)^2=5\); the C++ version also checks monotonicity for small \(n\).
The outer loop over \(m\) is open-ended in theory, because the algorithm stops only when it reaches the first feasible squared radius. For one fixed \(m\), the trial-division factorization and the enumeration of lattice points both cost \(O(\sqrt m)\) in the current implementations.
Let \(L=|\Lambda_m|\) and \(u=L/2\). Building the displacement set \(\Delta_m\) costs \(O(L^2)\) time and memory. The search over direction choices is combinatorial in the worst case, up to \(O\!\left(\binom{u}{d}\right)\) branches, although the 4-vector pruning removes most of them in practice. For a complete candidate, generating all subset sums costs \(O(d\,2^d)\), while the translated-circle verification costs \(O(2^{d-1}L^2)\).
For the actual target \(n=500\), the dimension is \(d=10\), so each parity class has \(512\) points. The exponential part is therefore tied to a very small dimension; the practical difficulty is finding a good \(m\) and pruning the combinatorial search aggressively enough.
Problem 983 fragt nach dem kleinsten quadratischen Radius \(R(n)^2\), für den sich eine hinreichend große konsonante Familie gleich großer Kreise konstruieren lässt. Die Implementierungen realisieren diese Konfiguration auf dem ganzzahligen Gitter: Jede gewählte Richtung ist ein Gitterpunkt auf dem Kreis \(x^2+y^2=R(n)^2\), die eigentlichen Kreismittelpunkte entstehen als Teilmengensummen dieser Richtungen, und jede nichttriviale Mehrfachkreuzung der gewählten Kreise muss selbst zu den durch dieselbe Konstruktion erzeugten Kreuzungspunkten gehören.
Der wesentliche Trick besteht darin, nicht \(n\) unabhängige Kreise zu suchen. Stattdessen werden zwei Paritätsklassen von Teilmengensummen aufgebaut: eine Klasse liefert die Kreismittelpunkte, die andere die erlaubten Schnittpunkte. Wählt man \(d\) Richtungen, so enthalten beide Klassen jeweils \(2^{d-1}\) Punkte. Deshalb verwenden die Implementierungen für \(n>2\) die Dimension
$$d=\min\{t\ge 1:2^{t-1}\ge n\}.$$
Danach wird \(m=1,2,3,\dots\) so lange erhöht, bis der Kreis \(x^2+y^2=m\) eine solche \(d\)-dimensionale Konstruktion zulässt.
Die gesamte Methode verbindet gleich lange Gittervektoren, Teilmengensummen und eine präzise Bedingung dafür, welche Kreisüberschneidungen erlaubt sind.
Für \(n\le 2\) ist das Problem trivial; die Implementierungen geben sofort \(R(n)^2=1\) zurück. Für größere \(n\) werden \(d\) Vektoren \(v_1,\dots,v_d\) mit derselben quadratischen Länge \(m\) gewählt. Daraus entstehen die beiden Paritätsklassen
$$E=\left\{\sum_{i\in A} v_i:\ |A|\equiv 0 \pmod 2\right\},\qquad O=\left\{\sum_{i\in A} v_i:\ |A|\equiv 1 \pmod 2\right\}.$$
Die Menge \(E\) ist die tatsächlich gezählte Familie von Kreismittelpunkten, \(O\) ist die Menge der erlaubten Schnittpunkte. Beide Mengen besitzen \(2^{d-1}\) Elemente; daher reicht die kleinste Dimension mit \(2^{d-1}\ge n\).
Für ein festes \(m\) sei
$$\Lambda_m=\{(x,y)\in\mathbb{Z}^2:x^2+y^2=m\}.$$
Jede gewählte Richtung stammt aus \(\Lambda_m\). Da \(v\) und \(-v\) geometrisch dieselbe Richtung bis auf einen Paritätswechsel liefern, behält die Suche aus jedem Gegenpaar \(\{v,-v\}\) nur einen Repräsentanten. Also ist \(m\) sofort ausgeschlossen, wenn \(\Lambda_m\) weniger als \(d\) Gegenpaare enthält.
Die in den Implementierungen verwendete Vorprüfung ist der klassische Zwei-Quadrate-Satz. Gilt
$$m=2^a\prod_i p_i^{\alpha_i}\prod_j q_j^{2\beta_j},\qquad p_i\equiv 1 \pmod 4,\quad q_j\equiv 3 \pmod 4,$$
dann folgt
$$|\Lambda_m|=4\prod_i(\alpha_i+1),\qquad \text{Gegenpaare}=\frac{|\Lambda_m|}{2}=2\prod_i(\alpha_i+1).$$
Tritt ein Primfaktor \(q\equiv 3 \pmod 4\) mit ungeradem Exponenten auf, dann ist \(\Lambda_m\) leer und dieses \(m\) kann sofort verworfen werden.
Sei \(e\in E\) eine gerade Teilmengensumme. Falls die zugrunde liegende Teilmenge \(i\) nicht enthält, dann ist \(e+v_i\in O\); enthält sie \(i\), dann ist \(e-v_i\in O\). Weil jedes \(v_i\) auf \(x^2+y^2=m\) liegt, befinden sich diese Punkte von \(O\) alle auf dem Kreis mit Radius \(\sqrt m\) um \(e\). Jeder Mittelpunkt aus \(E\) besitzt also \(d\) vorgesehene Schnittpunkte aus \(O\).
Umgekehrt unterscheidet sich jedes \(o\in O\) von \(d\) geraden Teilmengensummen durch Vektoren aus \(\Lambda_m\), also liegt jeder ungerade Punkt auf \(d\) Kreisen der Familie. Die so entstehende Inzidenzstruktur ist genau die des \(d\)-dimensionalen Würfelgraphen: Das Umschalten einer gewählten Richtung ändert die Parität und verschiebt um genau einen Gittervektor der Länge \(\sqrt m\).
Die Implementierungen verlangen, dass die Zuordnung \(A\mapsto \sum_{i\in A}v_i\) getrennt auf den geraden und auf den ungeraden Teilmengen injektiv ist. Anders gesagt, jede nichttriviale Relation
$$\sum_{i\in A}v_i=\sum_{i\in B}v_i\quad \text{mit}\quad |A|\equiv |B|\pmod 2,\ A\ne B$$
wird verworfen. Eine Kollision in \(E\) würde zwei verschiedene Kreise auf denselben Mittelpunkt zusammenfallen lassen; eine Kollision in \(O\) würde zwei vorgesehene Kreuzungspunkte identifizieren. Diese Injektivität ist der erste exakte Test, sobald eine Richtungsmenge gewählt wurde.
Die tiefere Bedingung lautet: Kein Punkt außerhalb von \(O\) darf auf zwei Kreisen mit Mittelpunkten in \(E\) liegen. Für \(e\in E\) und \(u\in\Lambda_m\) betrachtet man daher den Punkt \(z=e+u\), der sicher auf dem Kreis um \(e\) liegt. Ist \(z\in O\), dann handelt es sich um einen vorgesehenen Schnittpunkt, der auf mehreren Kreisen liegen darf. Ist \(z\notin O\), dann darf der verschobene Kreis \(z+\Lambda_m\) keinen zweiten Punkt aus \(E\) treffen. Genau geprüft wird
$$z\notin O\ \Longrightarrow\ |(z+\Lambda_m)\cap E|<2.$$
Das ist der eigentliche Konsonanztest: Jede Mehrfachkreuzung der gewählten Kreise muss aus den ungeraden Teilmengensummen stammen und nirgendwo sonst auftreten.
Um aussichtslose Suchzweige früh zu verwerfen, berechnen die Implementierungen
$$\Delta_m=\{a-b:\ a,b\in \Lambda_m,\ a\ne b\}.$$
Liegen zwei gerade Mittelpunkte auf demselben verschobenen Radius-\(\sqrt m\)-Kreis, dann gehört ihre Differenz zu \(\Delta_m\). Differenzen gerader Teilmengensummen sind signierte Summen aus einer geraden Anzahl gewählter Richtungen. Zweiterm-Differenzen entsprechen den vorgesehenen ungeraden Schnittpunkten; die ersten wirklich gefährlichen Störungen entstehen daher mit vier gewählten Richtungen. Während der Tiefensuche werden für jedes neue 4-Tupel die sechzehn Summen
$$\pm v_i\pm v_j\pm v_k\pm v_\ell$$
getestet, und der Zweig wird sofort abgeschnitten, sobald ein von null verschiedener Wert in \(\Delta_m\) liegt. Das ist noch nicht der vollständige Gültigkeitsbeweis, aber ein sehr starker notwendiger Filter vor dem teuren Teilmengensummen-Test.
Für \(n=4\) brauchen die Implementierungen \(d=3\), denn \(2^{3-1}=4\). Setze \(m=5\); dann ist
$$\Lambda_5=\{(\pm 2,\pm 1),(\pm 1,\pm 2)\}.$$
Wähle beispielsweise
$$v_1=(2,1),\qquad v_2=(2,-1),\qquad v_3=(1,2).$$
Die geraden Teilmengensummen sind dann
$$E=\{(0,0),(4,0),(3,3),(3,1)\},$$
und die ungeraden Teilmengensummen lauten
$$O=\{(2,1),(2,-1),(1,2),(5,2)\}.$$
Damit erhält man vier Kreise mit Radius \(\sqrt 5\), zentriert in den Punkten aus \(E\). Der Kreis um \((0,0)\) geht durch \((2,1)\), \((2,-1)\) und \((1,2)\); der Kreis um \((4,0)\) geht durch \((2,1)\), \((2,-1)\) und \((5,2)\); entsprechend arbeiten auch die beiden übrigen Mittelpunkte. Die ungeraden Punkte sind also genau die vorgesehenen gemeinsamen Kreuzungen, und die vollständige Validierung bestätigt, dass kein anderer Punkt auf zwei dieser vier Kreise liegt. Deshalb ist der Checkpointwert \(R(4)^2=5\).
Die C++-, Python- und Java-Implementierungen wandeln \(n\) zuerst in die benötigte Dimension \(d\) um und benutzen für \(n\le 2\) sofort die triviale Antwort \(R(n)^2=1\). Danach durchlaufen sie \(m=1,2,3,\dots\). Für jedes \(m\) wird mittels Primfaktorzerlegung die Zahl der Gegenpaare schnell bestimmt; liegt sie unter \(d\), wird \(m\) ohne weitere Arbeit verworfen.
Übersteht \(m\) den arithmetischen Vorfilter, so werden alle Gitterpunkte auf \(x^2+y^2=m\) erzeugt, zu Gegenpaaren zusammengefasst und auf kanonische Repräsentanten reduziert. Eine Tiefensuche probiert dann alle \(d\)-elementigen Auswahlen dieser Repräsentanten aus. Bei jedem Schritt wird die vorberechnete Menge \(\Delta_m\) genutzt: Erzeugt ein neues 4-Tupel bereits eine verbotene signierte Summe, so wird der Suchzweig abgeschnitten, bevor überhaupt Teilmengensummen berechnet werden.
Mathematisch führen alle drei Sprachen dieselbe Suche aus. Die C++-Implementierung parallelisiert zusätzlich die obersten Suchzweige nach der Wahl des ersten Repräsentanten; Python und Java führen dieselbe Logik seriell aus.
Sobald \(d\) Richtungen gewählt sind, erzeugen die Implementierungen alle \(2^d\) Teilmengensummen, trennen sie in \(E\) und \(O\) und prüfen die Injektivität in beiden Paritätsklassen. Besteht ein Kandidat diesen Test, folgt die Bedingung \(z\notin O \Rightarrow |(z+\Lambda_m)\cap E|<2\). Das erste \(m\), das alle Prüfungen besteht, wird zurückgegeben und ist daher konstruktiv das minimale \(R(n)^2\).
Die eingebauten Checkpoints bestätigen die ersten nichttrivialen Fälle \(R(2)^2=1\) und \(R(4)^2=5\); die C++-Version testet zusätzlich Monotonie für kleine \(n\).
Die äußere Schleife über \(m\) ist theoretisch unbeschränkt, weil der Algorithmus erst beim ersten zulässigen quadratischen Radius stoppt. Für ein festes \(m\) kosten sowohl die Trial-Division-Faktorisierung als auch die Erzeugung der Gitterpunkte in den vorliegenden Implementierungen \(O(\sqrt m)\).
Schreibt man \(L=|\Lambda_m|\) und \(u=L/2\), dann benötigt der Aufbau von \(\Delta_m\) \(O(L^2)\) Zeit und Speicher. Die Suche über die Richtungswahlen ist im Worst Case kombinatorisch, bis zu \(O\!\left(\binom{u}{d}\right)\) Zweigen, wobei das 4-Vektor-Pruning die Praxis stark verbessert. Für einen vollständigen Kandidaten kostet das Erzeugen aller Teilmengensummen \(O(d\,2^d)\), und die Prüfung der verschobenen Kreise kostet \(O(2^{d-1}L^2)\).
Für das eigentliche Ziel \(n=500\) ist \(d=10\), also besitzt jede Paritätsklasse \(512\) Punkte. Der exponentielle Anteil hängt damit an einer sehr kleinen Dimension; die praktische Schwierigkeit liegt darin, ein geeignetes \(m\) zu finden und die kombinatorische Suche genug zu beschneiden.
Problem 983, yeterince büyük bir konsonant eş yarıçaplı çember ailesini mümkün kılan en küçük \(R(n)^2\) değerini sorar. Uygulamalar bu yapıyı tam sayı kafesinde kuruyor: seçilen her yön, \(x^2+y^2=R(n)^2\) çemberi üzerindeki bir kafes noktasıdır; gerçek çember merkezleri bu yönlerin altküme toplamlarından üretilir; seçilen çemberlerin her gerçek çoklu kesişimi de yine aynı altküme-toplam yapısından gelen özel kesişim noktalarından biri olmak zorundadır.
Temel sadeleştirme, doğrudan birbirinden bağımsız \(n\) çember aramamak. Bunun yerine altküme toplamları iki parity sınıfına ayrılır: bir sınıf çember merkezlerini, diğeri ise izin verilen kesişim noktalarını verir. \(d\) yön seçildiğinde her iki sınıfta da \(2^{d-1}\) nokta vardır. Bu yüzden uygulamaların kullandığı boyut, \(n>2\) için
$$d=\min\{t\ge 1:2^{t-1}\ge n\}$$
olur. Bundan sonra arama, \(m=1,2,3,\dots\) değerlerini sırayla deneyip \(x^2+y^2=m\) çemberinin böyle bir \(d\)-yönlü yapı taşıdığı ilk noktada durur.
Tüm yöntem, eş uzunluklu kafes vektörleri, altküme toplamları ve hangi çember kesişimlerinin meşru olduğuna dair kesin bir koşul üzerine kurulur.
\(n\le 2\) için problem önemsizdir; uygulamalar doğrudan \(R(n)^2=1\) döndürür. Daha büyük \(n\) için kare uzunluğu \(m\) olan \(d\) adet vektör \(v_1,\dots,v_d\) seçilir. Bunlardan iki parity sınıfı tanımlanır:
$$E=\left\{\sum_{i\in A} v_i:\ |A|\equiv 0 \pmod 2\right\},\qquad O=\left\{\sum_{i\in A} v_i:\ |A|\equiv 1 \pmod 2\right\}.$$
Burada \(E\), aranan çember ailesinin merkezleridir; \(O\) ise bu çemberlerin paylaşmasına izin verilen kesişim noktalarıdır. Her iki kümenin büyüklüğü de \(2^{d-1}\) olduğu için, gerekli en küçük boyut tam olarak \(2^{d-1}\ge n\) koşulunu sağlayan ilk \(d\) değeridir.
Sabit bir \(m\) için
$$\Lambda_m=\{(x,y)\in\mathbb{Z}^2:x^2+y^2=m\}$$
olsun. Seçilecek her yön \(\Lambda_m\) içinden gelmek zorundadır. \(v\) ile \(-v\) yalnızca parity rolünü değiştirerek aynı geometrik yönü verdiği için arama, her antipodal çift \(\{v,-v\}\) içinden yalnızca tek temsilci tutar. Dolayısıyla \(\Lambda_m\) içinde \(d\) taneden az antipodal çift varsa bu \(m\) hemen elenir.
Uygulamalardaki hızlı eleme, iki kare teoremine dayanır. Eğer
$$m=2^a\prod_i p_i^{\alpha_i}\prod_j q_j^{2\beta_j},\qquad p_i\equiv 1 \pmod 4,\quad q_j\equiv 3 \pmod 4,$$
ise
$$|\Lambda_m|=4\prod_i(\alpha_i+1),\qquad \text{antipodal çift sayısı}=\frac{|\Lambda_m|}{2}=2\prod_i(\alpha_i+1)$$
olur. \(3 \pmod 4\) sınıfından bir asal tek kuvvetle gelirse \(\Lambda_m\) boştur ve bu \(m\) hiç denenmeden geçilir.
\(e\in E\) bir çift-altküme toplamı olsun. Eğer \(e\)'yi veren altküme \(i\)'yi içermiyorsa \(e+v_i\in O\), içeriyorsa \(e-v_i\in O\) olur. Bütün \(v_i\)'ler \(x^2+y^2=m\) üzerinde bulunduğu için bu noktaların hepsi, merkezi \(e\) olan ve yarıçapı \(\sqrt m\) olan çemberin üzerindedir. Yani \(E\)'deki her merkez, \(O\)'dan gelen tam \(d\) tane amaçlanan kesişim noktası üretir.
Tersi yönde de aynı yapı vardır: her \(o\in O\), \(d\) farklı \(E\) noktasından \(\Lambda_m\) içindeki vektörlerle ayrılır; dolayısıyla her tek-altküme toplamı, ailenin \(d\) farklı çemberi üzerinde yer alır. Böylece ortaya çıkan ilişki tam olarak \(d\)-boyutlu hiperküp grafiğinin bipartit yapısıdır: seçilen vektörlerden birini açıp kapatmak parity'yi değiştirir ve uzunluğu \(\sqrt m\) olan tek bir kafes vektörü kadar hareket ettirir.
Uygulamalar, \(A\mapsto \sum_{i\in A}v_i\) dönüşümünün çift altkümeler üzerinde ayrı, tek altkümeler üzerinde ayrı injektif olmasını ister. Yani
$$\sum_{i\in A}v_i=\sum_{i\in B}v_i\quad \text{ve}\quad |A|\equiv |B|\pmod 2,\ A\ne B$$
şeklindeki her gayritrivial eşitlik reddedilir. \(E\) içinde böyle bir çakışma olursa iki farklı çember aynı merkezde çöker; \(O\) içinde olursa iki ayrı kesişim noktası üst üste biner. Seçilen yönler için yapılan ilk kesin doğrulama budur.
Daha derin koşul şudur: \(O\) dışında hiçbir nokta, merkezi \(E\)'de olan iki çemberin ortak noktası olamaz. Bunun için \(e\in E\) ve \(u\in \Lambda_m\) alınır; \(z=e+u\) noktası zaten merkezi \(e\) olan çember üzerindedir. Eğer \(z\in O\) ise bu amaçlanan bir kesişimdir ve birden fazla çember üzerinde olması normaldir. Ama \(z\notin O\) ise, merkezi \(z\) olan ötelenmiş yarıçap-\(\sqrt m\) çemberi \(E\)'den ikinci bir noktaya değmemelidir. Kodun kontrol ettiği tam ifade
$$z\notin O\ \Longrightarrow\ |(z+\Lambda_m)\cap E|<2$$
şeklindedir. Konsonansın özü budur: çoklu kesişimler yalnızca tek-altküme toplamlarından gelmeli, başka hiçbir yerde ortaya çıkmamalıdır.
Ümitsiz dalları erken kesmek için uygulamalar
$$\Delta_m=\{a-b:\ a,b\in \Lambda_m,\ a\ne b\}$$
kümesini önceden kurar. Eğer \(E\)'deki iki merkez aynı ötelenmiş yarıçap-\(\sqrt m\) çemberi üzerindeyse farkları \(\Delta_m\)'de olmak zorundadır. Çift-altküme toplamları arasındaki farklar, seçilmiş yönlerin çift sayıda terim içeren işaretli toplamlarıdır. İki terimli farklar, amaçlanan tek-parity kesişimlere karşılık gelir; bu yüzden gerçekten tehlikeli ilk durum dört yönle ortaya çıkar. Derinlik araması sırasında her yeni 4'lü için
$$\pm v_i\pm v_j\pm v_k\pm v_\ell$$
toplamlarının on altısı denenir ve sıfır olmayan bir sonuç \(\Delta_m\)'ye düşerse dal hemen kesilir. Bu, tek başına tam kanıt değildir; ama pahalı altküme-toplam doğrulamasından önce çok güçlü bir zorunlu filtredir.
\(n=4\) için uygulamaların ihtiyacı olan boyut \(d=3\)'tür; çünkü \(2^{3-1}=4\). \(m=5\) alalım. O zaman
$$\Lambda_5=\{(\pm 2,\pm 1),(\pm 1,\pm 2)\}$$
olur. Örneğin
$$v_1=(2,1),\qquad v_2=(2,-1),\qquad v_3=(1,2)$$
seçilebilir. Bu durumda çift-altküme toplamları
$$E=\{(0,0),(4,0),(3,3),(3,1)\}$$
ve tek-altküme toplamları
$$O=\{(2,1),(2,-1),(1,2),(5,2)\}$$
olur. Böylece yarıçapı \(\sqrt 5\) olan dört çember elde edilir; merkezleri \(E\)'deki noktalardır. \((0,0)\) merkezli çember \((2,1)\), \((2,-1)\) ve \((1,2)\) noktalarından geçer; \((4,0)\) merkezli çember ise \((2,1)\), \((2,-1)\) ve \((5,2)\) noktalarından geçer; diğer iki merkez de aynı şekilde çalışır. Yani \(O\), amaçlanan ortak kesişimlerin tam kümesidir ve tam doğrulama başka ortak nokta olmadığını onaylar. Bu yüzden kontrol değeri \(R(4)^2=5\)'tir.
C++, Python ve Java uygulamaları önce \(n\)'i gerekli boyut \(d\)'ye dönüştürür ve \(n\le 2\) için doğrudan \(R(n)^2=1\) sonucunu kullanır. Sonra \(m=1,2,3,\dots\) sırayla denenir. Her \(m\) için asal çarpanlardan antipodal çift sayısı hızlıca hesaplanır; bu sayı \(d\)'den küçükse başka hiçbir işlem yapılmadan sonraki \(m\)'ye geçilir.
\(m\) ilk aritmetik elemeden geçerse, \(x^2+y^2=m\) üzerindeki bütün kafes noktaları üretilir, antipodal çiftlere ayrılır ve her çiftten kanonik bir temsilci alınır. Sonra derinlik öncelikli arama, bu temsilciler arasından \(d\) tanesinin bütün seçimlerini dener. Her adımda önceden kurulan \(\Delta_m\) kullanılır: yeni oluşan bir 4'lü bile yasak bir işaretli toplam veriyorsa pahalı altküme-toplam hesabına geçmeden dal bırakılır.
Üç dil de aynı matematiksel aramayı uygular. C++ sürümü buna ek olarak ilk temsilci seçimine göre en üst dalları paralelleştirir; Python ve Java sürümleri aynı aramayı seri biçimde yürütür.
\(d\) yön seçildiğinde uygulamalar tüm \(2^d\) altküme toplamlarını üretir, bunları \(E\) ve \(O\) olarak ayırır ve her iki parity sınıfında tekillik testini yapar. Bu aşama geçilirse \(z\notin O \Rightarrow |(z+\Lambda_m)\cap E|<2\) koşulu uygulanır. Bütün testleri geçen ilk \(m\), tanım gereği minimal \(R(n)^2\) olarak döndürülür.
Yerleşik kontroller, ilk anlamlı örnekler olan \(R(2)^2=1\) ve \(R(4)^2=5\) değerlerini doğrular; C++ sürümü ayrıca küçük \(n\) için monotonluğu da sınar.
\(m\) üzerindeki dış döngü teorik olarak açık uçludur; çünkü algoritma, ilk uygun kare yarıçapa ulaşınca durur. Sabit bir \(m\) için bakıldığında, mevcut uygulamalarda trial-division asal çarpanlama ve kafes noktalarını üretme maliyeti \(O(\sqrt m)\) düzeyindedir.
\(L=|\Lambda_m|\) ve \(u=L/2\) yazalım. \(\Delta_m\) kümesini kurmak \(O(L^2)\) zaman ve bellek ister. Yön seçimi araması en kötü durumda \(O\!\left(\binom{u}{d}\right)\) dallıdır; fakat 4-vektör budaması pratikte bunu ciddi biçimde küçültür. Bir aday tamamen seçildiğinde tüm altküme toplamlarını üretmek \(O(d\,2^d)\), ötelenmiş çember koşulunu sınamak ise \(O(2^{d-1}L^2)\) maliyetlidir.
Asıl hedef olan \(n=500\) için boyut \(d=10\)'dur; yani her parity sınıfında \(512\) nokta vardır. Bu yüzden üstel kısım çok küçük bir boyuta bağlıdır; pratik zorluk, uygun \(m\)'yi bulmak ve kombinatorik aramayı yeterince agresif budamaktır.
El problema 983 pide el menor radio cuadrado \(R(n)^2\) que permite construir una familia suficientemente grande de circunferencias consonantes con el mismo radio. Las implementaciones realizan la construcción en la red entera: cada dirección elegida es un punto reticular de la circunferencia \(x^2+y^2=R(n)^2\), los centros reales de las circunferencias se obtienen como sumas de subconjuntos de esas direcciones, y toda intersección múltiple no trivial de las circunferencias elegidas debe ser uno de los puntos de cruce designados por la misma construcción de sumas.
La simplificación decisiva es que no se buscan \(n\) circunferencias independientes. Se generan dos clases de paridad de sumas de subconjuntos: una clase proporciona los centros y la otra los cruces permitidos. Si se escogen \(d\) direcciones, cada clase contiene \(2^{d-1}\) puntos, así que para \(n>2\) la dimensión usada por las implementaciones es
$$d=\min\{t\ge 1:2^{t-1}\ge n\}.$$
Luego se prueba \(m=1,2,3,\dots\) hasta que la circunferencia \(x^2+y^2=m\) soporte una construcción válida con esa dimensión.
Todo el método combina vectores reticulares de la misma longitud, sumas de subconjuntos y una condición precisa que decide qué cruces de circunferencias son legítimos.
Para \(n\le 2\), el problema es trivial y las implementaciones devuelven inmediatamente \(R(n)^2=1\). Para \(n\) mayor se eligen \(d\) vectores \(v_1,\dots,v_d\), todos con norma cuadrada \(m\). A partir de ellos se definen
$$E=\left\{\sum_{i\in A} v_i:\ |A|\equiv 0 \pmod 2\right\},\qquad O=\left\{\sum_{i\in A} v_i:\ |A|\equiv 1 \pmod 2\right\}.$$
El conjunto \(E\) es la familia de centros que realmente cuenta la búsqueda, mientras que \(O\) es el conjunto de puntos donde esas circunferencias pueden cruzarse. Ambos tienen tamaño \(2^{d-1}\), y por eso basta el menor \(d\) con \(2^{d-1}\ge n\).
Fijado \(m\), escribimos
$$\Lambda_m=\{(x,y)\in\mathbb{Z}^2:x^2+y^2=m\}.$$
Cada dirección elegida debe pertenecer a \(\Lambda_m\). Como \(v\) y \(-v\) representan la misma dirección geométrica salvo un cambio de paridad, la búsqueda conserva un solo representante de cada par antipodal \(\{v,-v\}\). En consecuencia, si \(\Lambda_m\) contiene menos de \(d\) pares antipodales, ese \(m\) se descarta inmediatamente.
La criba aritmética usada por las implementaciones es el criterio clásico de suma de dos cuadrados. Si
$$m=2^a\prod_i p_i^{\alpha_i}\prod_j q_j^{2\beta_j},\qquad p_i\equiv 1 \pmod 4,\quad q_j\equiv 3 \pmod 4,$$
entonces
$$|\Lambda_m|=4\prod_i(\alpha_i+1),\qquad \text{pares antipodales}=\frac{|\Lambda_m|}{2}=2\prod_i(\alpha_i+1).$$
Si un primo \(q\equiv 3 \pmod 4\) aparece con exponente impar, entonces \(\Lambda_m\) es vacío y ese valor de \(m\) no puede funcionar.
Tomemos un centro par \(e\in E\). Si el subconjunto que define \(e\) no contiene a \(i\), entonces \(e+v_i\in O\); si sí lo contiene, entonces \(e-v_i\in O\). Como cada \(v_i\) pertenece a \(x^2+y^2=m\), todos esos puntos de \(O\) están sobre la circunferencia de radio \(\sqrt m\) centrada en \(e\). Así, cada circunferencia con centro en \(E\) lleva consigo exactamente \(d\) cruces previstos de \(O\).
La misma relación vista al revés dice que todo \(o\in O\) difiere de \(d\) puntos de \(E\) por vectores de \(\Lambda_m\), de modo que cada punto impar está contenido en \(d\) circunferencias de la familia. La estructura de incidencia es, por tanto, la del grafo hipercubo de dimensión \(d\): cambiar una sola dirección elegida cambia la paridad y desplaza por un vector reticular de longitud \(\sqrt m\).
Las implementaciones exigen que la aplicación \(A\mapsto \sum_{i\in A}v_i\) sea inyectiva por separado sobre los subconjuntos pares y sobre los impares. Es decir, se rechaza cualquier relación no trivial
$$\sum_{i\in A}v_i=\sum_{i\in B}v_i\quad \text{con}\quad |A|\equiv |B|\pmod 2,\ A\ne B.$$
Una colisión dentro de \(E\) haría que dos circunferencias supuestamente distintas compartieran el mismo centro; una colisión dentro de \(O\) fusionaría dos cruces previstos. Esa es la primera comprobación exacta que se hace cuando ya se ha elegido un conjunto de direcciones.
La condición más importante es que ningún punto fuera de \(O\) puede pertenecer a dos circunferencias con centro en \(E\). Para ello, dado \(e\in E\) y \(u\in \Lambda_m\), se considera \(z=e+u\), que seguro está sobre la circunferencia centrada en \(e\). Si \(z\in O\), se trata de un cruce previsto y puede estar en varias circunferencias. Si \(z\notin O\), entonces la circunferencia trasladada \(z+\Lambda_m\) no debe contener un segundo punto de \(E\). La condición exacta comprobada por el código es
$$z\notin O\ \Longrightarrow\ |(z+\Lambda_m)\cap E|<2.$$
Ese es el núcleo de la consonancia: todos los cruces múltiples auténticos de la familia elegida deben venir de los puntos impares designados, y no de otros puntos del plano.
Para descartar ramas imposibles de manera temprana, las implementaciones precalculan
$$\Delta_m=\{a-b:\ a,b\in \Lambda_m,\ a\ne b\}.$$
Si dos centros pares están sobre una misma circunferencia trasladada de radio \(\sqrt m\), su diferencia pertenece a \(\Delta_m\). Las diferencias entre sumas pares son sumas con signo de un número par de direcciones elegidas. Las diferencias de dos términos corresponden a cruces impares legítimos; por eso las primeras obstrucciones realmente peligrosas aparecen con cuatro direcciones. Durante la búsqueda en profundidad, cada nuevo 4-tuplo se prueba con las dieciséis combinaciones
$$\pm v_i\pm v_j\pm v_k\pm v_\ell,$$
y la rama se corta en cuanto un valor no nulo cae en \(\Delta_m\). No es la demostración completa de validez, pero sí un filtro necesario muy potente antes de la verificación final.
Para \(n=4\), las implementaciones necesitan \(d=3\), porque \(2^{3-1}=4\). Tomemos \(m=5\); entonces
$$\Lambda_5=\{(\pm 2,\pm 1),(\pm 1,\pm 2)\}.$$
Una elección válida es
$$v_1=(2,1),\qquad v_2=(2,-1),\qquad v_3=(1,2).$$
Las sumas pares quedan
$$E=\{(0,0),(4,0),(3,3),(3,1)\},$$
y las sumas impares son
$$O=\{(2,1),(2,-1),(1,2),(5,2)\}.$$
Así aparecen cuatro circunferencias de radio \(\sqrt 5\) centradas en los puntos de \(E\). La centrada en \((0,0)\) pasa por \((2,1)\), \((2,-1)\) y \((1,2)\); la centrada en \((4,0)\) pasa por \((2,1)\), \((2,-1)\) y \((5,2)\); las otras dos funcionan del mismo modo. Los puntos de \(O\) son exactamente los cruces compartidos que se querían, y la verificación completa confirma que no aparece ningún otro cruce doble. Por eso el valor de control es \(R(4)^2=5\).
Las implementaciones en C++, Python y Java convierten primero \(n\) en la dimensión necesaria \(d\), con el atajo trivial \(R(n)^2=1\) para \(n\le 2\). Después recorren \(m=1,2,3,\dots\). Para cada \(m\), usan la factorización prima para contar rápidamente los pares antipodales, y si ese número es menor que \(d\), descartan el candidato sin trabajo adicional.
Cuando \(m\) supera el filtro aritmético, las implementaciones enumeran todos los puntos reticulares de \(x^2+y^2=m\), los agrupan en pares antipodales y conservan un representante canónico de cada uno. Una búsqueda en profundidad prueba todas las elecciones de \(d\) representantes. En cada paso se usa \(\Delta_m\): si un nuevo 4-tuplo ya produce una suma con signo prohibida, la rama se abandona antes de calcular las sumas de subconjuntos.
Las tres versiones aplican la misma búsqueda matemática. La implementación en C++ además paraleliza las ramas superiores correspondientes a la elección del primer representante; las versiones en Python y Java ejecutan la misma lógica en serie.
Una vez elegidas las \(d\) direcciones, las implementaciones generan las \(2^d\) sumas de subconjuntos, las separan en \(E\) y \(O\), y comprueban la inyectividad dentro de cada clase de paridad. Si eso pasa, aplican la condición \(z\notin O \Rightarrow |(z+\Lambda_m)\cap E|<2\). El primer \(m\) que supera todas las pruebas se devuelve, así que por construcción es el valor mínimo \(R(n)^2\).
Las comprobaciones internas validan los primeros casos no triviales \(R(2)^2=1\) y \(R(4)^2=5\); la versión en C++ añade además una comprobación de monotonía para valores pequeños de \(n\).
El bucle exterior sobre \(m\) no tiene una cota teórica cerrada de antemano, porque el algoritmo se detiene solo al encontrar el primer radio cuadrado factible. Para un \(m\) fijo, tanto la factorización por prueba de divisores como la enumeración de puntos reticulares cuestan \(O(\sqrt m)\) en las implementaciones actuales.
Si \(L=|\Lambda_m|\) y \(u=L/2\), construir \(\Delta_m\) cuesta \(O(L^2)\) en tiempo y memoria. La búsqueda sobre las elecciones de direcciones es combinatoria en el peor caso, hasta \(O\!\left(\binom{u}{d}\right)\) ramas, aunque la poda por 4-vectores reduce mucho el coste práctico. Para un candidato completo, generar todas las sumas de subconjuntos cuesta \(O(d\,2^d)\), y la verificación de circunferencias trasladadas cuesta \(O(2^{d-1}L^2)\).
En el objetivo real \(n=500\), la dimensión es \(d=10\), de modo que cada clase de paridad contiene \(512\) puntos. La parte exponencial queda, por tanto, ligada a una dimensión pequeña; la dificultad práctica está en encontrar un \(m\) adecuado y podar la búsqueda combinatoria con suficiente agresividad.
第 983 题要求的是最小的平方半径 \(R(n)^2\)，使得可以构造出一个足够大的“共振式”同半径圆族。实现代码采用的是整数格点版本：每一个被选中的方向，都是圆 \(x^2+y^2=R(n)^2\) 上的一个整点；真正的圆心不是随便放置的，而是这些方向向量的子集和；同时，所允许出现的多重交点，也必须来自同一个子集和构造，而不能在平面上额外冒出来。
代码并不是直接去找 \(n\) 个彼此无关的圆，而是把所有子集和按奇偶性分成两类：一类作为圆心，另一类作为合法交点。若选了 \(d\) 个方向，那么这两类各自都有 \(2^{d-1}\) 个点。因此，对 \(n>2\) 而言，程序真正使用的维数是
$$d=\min\{t\ge 1:2^{t-1}\ge n\}.$$
随后程序按 \(m=1,2,3,\dots\) 递增搜索，直到圆 \(x^2+y^2=m\) 能支持这样一个 \(d\) 维构造为止。
整个方法把三件事绑在一起：固定长度的格点向量、这些向量的子集和，以及“哪些圆交点是合法的”这一条非常严格的判定条件。
当 \(n\le 2\) 时，问题是平凡的，代码直接返回 \(R(n)^2=1\)。当 \(n\) 更大时，构造会选择 \(d\) 个向量 \(v_1,\dots,v_d\)，它们的平方长度都等于同一个 \(m\)。然后定义两类子集和
$$E=\left\{\sum_{i\in A} v_i:\ |A|\equiv 0 \pmod 2\right\},\qquad O=\left\{\sum_{i\in A} v_i:\ |A|\equiv 1 \pmod 2\right\}.$$
这里 \(E\) 是真正被计数的圆心集合，\(O\) 是这些圆允许共享的交点集合。两者大小都正好是 \(2^{d-1}\)，这就是为什么程序只需要找到满足 \(2^{d-1}\ge n\) 的最小 \(d\)。
对固定的 \(m\)，记
$$\Lambda_m=\{(x,y)\in\mathbb{Z}^2:x^2+y^2=m\}.$$
所有被选中的方向都必须来自 \(\Lambda_m\)。由于 \(v\) 与 \(-v\) 在几何上只是同一条方向的相反取向，代码在搜索时只保留每个对踵对 \(\{v,-v\}\) 中的一个代表。所以，如果 \(\Lambda_m\) 的对踵对数量少于 \(d\)，那么这个 \(m\) 连尝试都没有必要。
实现里的快速数论过滤正是经典的“两平方和”判据。若
$$m=2^a\prod_i p_i^{\alpha_i}\prod_j q_j^{2\beta_j},\qquad p_i\equiv 1 \pmod 4,\quad q_j\equiv 3 \pmod 4,$$
则有
$$|\Lambda_m|=4\prod_i(\alpha_i+1),\qquad \text{对踵对数}=\frac{|\Lambda_m|}{2}=2\prod_i(\alpha_i+1).$$
如果某个 \(3 \pmod 4\) 的素数出现了奇数次幂，那么 \(\Lambda_m\) 为空，这个 \(m\) 会被立刻跳过。
取任意一个偶子集和 \(e\in E\)。如果定义 \(e\) 的那个子集不含 \(i\)，那么 \(e+v_i\in O\)；如果含 \(i\)，那么 \(e-v_i\in O\)。因为每个 \(v_i\) 都在 \(x^2+y^2=m\) 上，所以这些得到的奇点都位于以 \(e\) 为圆心、半径为 \(\sqrt m\) 的圆上。也就是说，\(E\) 中的每一个圆心都会自然带出 \(d\) 个“应该存在”的交点。
反过来看也一样：任意 \(o\in O\) 与 \(d\) 个不同的 \(E\) 中点只相差 \(\Lambda_m\) 内的向量，因此每个奇点都会落在这族圆中的 \(d\) 个圆上。于是得到的关联结构正好是 \(d\) 维超立方体的二分图结构：切换一个方向，就会改变奇偶类，并沿着一个长度为 \(\sqrt m\) 的格点向量移动。
代码要求映射 \(A\mapsto \sum_{i\in A}v_i\) 在偶子集上单独单射，在奇子集上也单独单射。换句话说，凡是出现
$$\sum_{i\in A}v_i=\sum_{i\in B}v_i\quad \text{且}\quad |A|\equiv |B|\pmod 2,\ A\ne B$$
这样的非平凡关系，候选解就会被判掉。因为若在 \(E\) 内碰撞，就意味着两个本应不同的圆心重合；若在 \(O\) 内碰撞，就意味着两个本应不同的合法交点被压成同一点。这个检查是方向选定后执行的第一个严格正确性测试。
更关键的条件是：除 \(O\) 之外，平面上不能再有点同时落在两个以 \(E\) 中点为圆心的圆上。为此，对任意 \(e\in E\) 和 \(u\in \Lambda_m\)，看点 \(z=e+u\)。它肯定位于以 \(e\) 为圆心的圆上。如果 \(z\in O\)，那是构造本来就允许的交点；如果 \(z\notin O\)，那么以 \(z\) 为中心平移出来的圆 \(z+\Lambda_m\) 就绝不能再碰到第二个 \(E\) 中点。代码精确检查的是
$$z\notin O\ \Longrightarrow\ |(z+\Lambda_m)\cap E|<2.$$
这就是“consonant”条件在实现中的核心形式：真正的多重圆交点只能来自奇子集和，而不能在别处偷偷出现。
为了尽早剪掉必败分支，程序预先构造
$$\Delta_m=\{a-b:\ a,b\in \Lambda_m,\ a\ne b\}.$$
如果两个偶圆心落在同一个平移后的半径 \(\sqrt m\) 圆上，那么它们的差必然属于 \(\Delta_m\)。而两个偶子集和之差，一定是若干选中方向的带符号和，并且非零项个数为偶数。两项差对应的是本来就合法的奇交点，所以真正危险的最早情形出现在四个方向上。于是深搜每加入一个新向量，都会检查所有新形成的四元组以及十六种符号组合
$$\pm v_i\pm v_j\pm v_k\pm v_\ell,$$
只要某个非零和落进 \(\Delta_m\)，这条搜索分支就立即丢弃。它不是最终正确性的全部证明，但却是一个非常强的必要条件过滤器。
对 \(n=4\) 来说，程序需要 \(d=3\)，因为 \(2^{3-1}=4\)。取 \(m=5\)，则
$$\Lambda_5=\{(\pm 2,\pm 1),(\pm 1,\pm 2)\}.$$
可以选择
$$v_1=(2,1),\qquad v_2=(2,-1),\qquad v_3=(1,2).$$
这时偶子集和为
$$E=\{(0,0),(4,0),(3,3),(3,1)\},$$
奇子集和为
$$O=\{(2,1),(2,-1),(1,2),(5,2)\}.$$
于是得到四个半径为 \(\sqrt 5\) 的圆，它们的圆心正是 \(E\) 中的四个点。以 \((0,0)\) 为圆心的圆经过 \((2,1)\)、\((2,-1)\)、\((1,2)\)；以 \((4,0)\) 为圆心的圆经过 \((2,1)\)、\((2,-1)\)、\((5,2)\)；另外两个偶圆心也完全类似。也就是说，\(O\) 正好就是这四个圆之间允许共享的交点集合，而完整验证进一步确认不会出现别的双重交点，因此检查点的确是 \(R(4)^2=5\)。
C++、Python 和 Java 三个实现都会先把 \(n\) 转成所需维数 \(d\)，并在 \(n\le 2\) 时直接返回平凡答案 \(R(n)^2=1\)。随后按顺序扫描 \(m=1,2,3,\dots\)。对每个 \(m\)，先用素因子分解快速计算对踵对数量；若这个数量小于 \(d\)，就不再做任何进一步工作。
一旦某个 \(m\) 通过数论过滤，程序就枚举 \(x^2+y^2=m\) 上的所有整点，把它们按对踵对分组，并从每一对中选出一个规范代表。随后深度优先搜索所有可能的 \(d\) 元选择。每走一步，都会使用预先构造好的 \(\Delta_m\)：如果新出现的四元组已经产生了禁止的带符号和，那么这条分支会在昂贵的子集和验证之前就被终止。
三种语言实现的数学逻辑是相同的。C++ 版本另外把第一层代表方向的选择并行化；Python 和 Java 版本则用串行方式完成同样的搜索。
当 \(d\) 个方向被选定后，程序生成全部 \(2^d\) 个子集和，拆成 \(E\) 和 \(O\)，并分别检查两类内部是否保持单射。若通过，就执行条件 \(z\notin O \Rightarrow |(z+\Lambda_m)\cap E|<2\)。第一个通过所有测试的 \(m\) 会被返回，因此它按定义就是最小的 \(R(n)^2\)。
内置检查确认了最先出现的非平凡值 \(R(2)^2=1\) 和 \(R(4)^2=5\)；C++ 版本还额外验证了小范围内的单调性。
外层对 \(m\) 的搜索在理论上没有先验上界，因为算法只会在遇到第一个可行平方半径时停止。对于单个固定的 \(m\)，当前实现中的试除分解和整点枚举都需要 \(O(\sqrt m)\) 级别的时间。
记 \(L=|\Lambda_m|\)，\(u=L/2\)。构造位移集合 \(\Delta_m\) 需要 \(O(L^2)\) 的时间和内存。方向选择的深搜在最坏情况下有 \(O\!\left(\binom{u}{d}\right)\) 个分支，不过四向量剪枝会在实践中消掉大部分分支。对一个完整候选而言，生成所有子集和的代价是 \(O(d\,2^d)\)，而平移圆验证的代价是 \(O(2^{d-1}L^2)\)。
对实际目标 \(n=500\)，维数为 \(d=10\)，因此每个奇偶类各有 \(512\) 个点。也就是说，指数部分只绑定在很小的维度上；真正的实践难点是找到合适的 \(m\)，并让组合搜索尽可能早地被剪掉。
В задаче 983 требуется найти минимальный квадрат радиуса \(R(n)^2\), при котором существует достаточно большое согласованное семейство окружностей одинакового радиуса. Реализации строят такую конфигурацию на целочисленной решетке: каждое выбранное направление является решеточной точкой на окружности \(x^2+y^2=R(n)^2\), реальные центры окружностей получаются как суммы по подмножествам этих направлений, а каждое нетривиальное кратное пересечение должно само быть одной из специальных точек, порожденных той же схемой сумм.
Главное упрощение состоит в том, что код не ищет \(n\) независимых окружностей напрямую. Он строит два класса подмножественных сумм по четности: один класс задает центры окружностей, другой задает разрешенные точки пересечения. Если выбрано \(d\) направлений, то в каждом классе ровно \(2^{d-1}\) точек. Поэтому для \(n>2\) используется размерность
$$d=\min\{t\ge 1:2^{t-1}\ge n\}.$$
После этого алгоритм перебирает \(m=1,2,3,\dots\), пока окружность \(x^2+y^2=m\) не окажется пригодной для такой \(d\)-мерной конструкции.
Вся идея опирается на три вещи: решеточные векторы одинаковой длины, суммы по подмножествам и точную проверку того, какие пересечения окружностей допустимы.
При \(n\le 2\) задача тривиальна, и реализации сразу возвращают \(R(n)^2=1\). Для больших \(n\) выбираются \(d\) векторов \(v_1,\dots,v_d\), каждый с квадратом длины \(m\). По ним определяются два класса
$$E=\left\{\sum_{i\in A} v_i:\ |A|\equiv 0 \pmod 2\right\},\qquad O=\left\{\sum_{i\in A} v_i:\ |A|\equiv 1 \pmod 2\right\}.$$
Множество \(E\) — это именно центры окружностей, которые считает поиск, а \(O\) — множество разрешенных точек их пересечения. Оба множества имеют мощность \(2^{d-1}\), поэтому нужен минимальный \(d\), для которого \(2^{d-1}\ge n\).
Для фиксированного \(m\) обозначим
$$\Lambda_m=\{(x,y)\in\mathbb{Z}^2:x^2+y^2=m\}.$$
Каждое выбранное направление должно лежать в \(\Lambda_m\). Поскольку \(v\) и \(-v\) задают одну и ту же геометрическую ось с точностью до смены четности, поиск оставляет только одного представителя из каждой антиподальной пары \(\{v,-v\}\). Значит, если в \(\Lambda_m\) меньше \(d\) антиподальных пар, такое \(m\) отбрасывается сразу.
Быстрая арифметическая проверка в коде — это классический критерий суммы двух квадратов. Если
$$m=2^a\prod_i p_i^{\alpha_i}\prod_j q_j^{2\beta_j},\qquad p_i\equiv 1 \pmod 4,\quad q_j\equiv 3 \pmod 4,$$
то
$$|\Lambda_m|=4\prod_i(\alpha_i+1),\qquad \text{антиподальных пар}=\frac{|\Lambda_m|}{2}=2\prod_i(\alpha_i+1).$$
Если какой-либо простой множитель \(q\equiv 3 \pmod 4\) входит в нечетной степени, то \(\Lambda_m\) пусто, и этот кандидат \(m\) даже не рассматривается дальше.
Возьмем любой четный центр \(e\in E\). Если подмножество, задающее \(e\), не содержит \(i\), то \(e+v_i\in O\); если содержит, то \(e-v_i\in O\). Так как каждый \(v_i\) лежит на \(x^2+y^2=m\), все эти точки из \(O\) находятся на окружности радиуса \(\sqrt m\) с центром в \(e\). Значит, каждая окружность с центром из \(E\) автоматически получает \(d\) предусмотренных точек пересечения из \(O\).
То же самое верно в обратную сторону: каждое \(o\in O\) отличается от \(d\) точек из \(E\) на векторы из \(\Lambda_m\), поэтому любая нечетная сумма лежит ровно на \(d\) окружностях семейства. Иначе говоря, возникает двудольная структура, изоморфная графу \(d\)-мерного куба: переключение одного выбранного направления меняет четность и сдвигает на один решеточный вектор длины \(\sqrt m\).
Реализации требуют, чтобы отображение \(A\mapsto \sum_{i\in A}v_i\) было инъективным отдельно на четных подмножествах и отдельно на нечетных. Иначе говоря, отбрасывается любое нетривиальное равенство
$$\sum_{i\in A}v_i=\sum_{i\in B}v_i\quad \text{при}\quad |A|\equiv |B|\pmod 2,\ A\ne B.$$
Столкновение внутри \(E\) означало бы, что два различных центра окружностей совпали; столкновение внутри \(O\) означало бы слияние двух разных разрешенных точек пересечения. Это первая точная проверка после выбора направлений.
Главное условие состоит в том, что ни одна точка вне \(O\) не должна лежать сразу на двух окружностях с центрами в \(E\). Поэтому для \(e\in E\) и \(u\in \Lambda_m\) рассматривается точка \(z=e+u\), которая заведомо лежит на окружности с центром \(e\). Если \(z\in O\), то это разрешенная точка пересечения, и она может принадлежать нескольким окружностям. Если же \(z\notin O\), то сдвинутая окружность \(z+\Lambda_m\) не должна содержать второй точки из \(E\). Именно это и проверяет код:
$$z\notin O\ \Longrightarrow\ |(z+\Lambda_m)\cap E|<2.$$
Это и есть сущность согласованности: все настоящие многократные пересечения выбранных окружностей обязаны приходить только из нечетных подмножественных сумм.
Чтобы отсеивать безнадежные ветви как можно раньше, реализации заранее строят
$$\Delta_m=\{a-b:\ a,b\in \Lambda_m,\ a\ne b\}.$$
Если две четные суммы лежат на одной и той же сдвинутой окружности радиуса \(\sqrt m\), их разность обязана лежать в \(\Delta_m\). Разности четных подмножественных сумм — это знакопеременные суммы четного числа выбранных направлений. Двухчленные разности соответствуют законным нечетным пересечениям, поэтому первые действительно опасные препятствия возникают на четырех направлениях. Во время DFS каждая новая четверка проверяется по шестнадцати суммам
$$\pm v_i\pm v_j\pm v_k\pm v_\ell,$$
и как только ненулевое значение попадает в \(\Delta_m\), ветвь немедленно отбрасывается. Это еще не полная проверка корректности, но очень сильный необходимый фильтр.
Для \(n=4\) реализации берут \(d=3\), поскольку \(2^{3-1}=4\). Выберем \(m=5\); тогда
$$\Lambda_5=\{(\pm 2,\pm 1),(\pm 1,\pm 2)\}.$$
Подходит, например, выбор
$$v_1=(2,1),\qquad v_2=(2,-1),\qquad v_3=(1,2).$$
Четные суммы равны
$$E=\{(0,0),(4,0),(3,3),(3,1)\},$$
а нечетные суммы равны
$$O=\{(2,1),(2,-1),(1,2),(5,2)\}.$$
Тем самым получаются четыре окружности радиуса \(\sqrt 5\) с центрами в точках из \(E\). Окружность с центром в \((0,0)\) проходит через \((2,1)\), \((2,-1)\) и \((1,2)\); окружность с центром в \((4,0)\) проходит через \((2,1)\), \((2,-1)\) и \((5,2)\); аналогично работают и две остальные. Значит, точки из \(O\) — это именно те пересечения, которые и должны быть общими, а полная проверка подтверждает отсутствие других двойных пересечений. Поэтому контрольное значение равно \(R(4)^2=5\).
Реализации на C++, Python и Java сначала переводят \(n\) в требуемую размерность \(d\), а для \(n\le 2\) сразу используют тривиальный ответ \(R(n)^2=1\). Затем они перебирают \(m=1,2,3,\dots\). Для каждого \(m\) по разложению на простые множители быстро вычисляется число антиподальных пар; если оно меньше \(d\), кандидат отбрасывается без дальнейших вычислений.
Если \(m\) прошло арифметический фильтр, реализации перечисляют все решеточные точки на \(x^2+y^2=m\), объединяют их в антиподальные пары и выбирают по одному каноническому представителю из каждой пары. Затем DFS перебирает все выборы из \(d\) представителей. На каждом шаге используется множество \(\Delta_m\): если новая четверка уже порождает запрещенную знакопеременную сумму, ветвь обрывается еще до полного вычисления сумм по подмножествам.
Во всех трех языках математическая логика одна и та же. Дополнительно версия на C++ распараллеливает верхний уровень DFS по выбору первого представителя, тогда как Python и Java выполняют тот же поиск последовательно.
Когда \(d\) направлений уже выбраны, реализации строят все \(2^d\) подмножественные суммы, делят их на \(E\) и \(O\), а затем проверяют инъективность внутри каждого класса четности. Если это выполнено, запускается проверка \(z\notin O \Rightarrow |(z+\Lambda_m)\cap E|<2\). Первое \(m\), прошедшее все тесты, возвращается как минимальное значение \(R(n)^2\).
Встроенные проверки подтверждают первые нетривиальные случаи \(R(2)^2=1\) и \(R(4)^2=5\); версия на C++ дополнительно проверяет монотонность для малых \(n\).
Внешний цикл по \(m\) теоретически не ограничен заранее, потому что алгоритм останавливается только на первом допустимом квадрате радиуса. Для фиксированного \(m\) и пробное деление при факторизации, и перечисление решеточных точек имеют в текущих реализациях стоимость \(O(\sqrt m)\).
Пусть \(L=|\Lambda_m|\) и \(u=L/2\). Построение \(\Delta_m\) требует \(O(L^2)\) времени и памяти. Перебор выборов направлений в худшем случае имеет комбинаторную стоимость \(O\!\left(\binom{u}{d}\right)\), хотя отсечение по четверкам сильно уменьшает реальное время. Для полного кандидата генерация всех подмножественных сумм стоит \(O(d\,2^d)\), а проверка сдвинутых окружностей стоит \(O(2^{d-1}L^2)\).
Для целевого значения \(n=500\) размерность равна \(d=10\), поэтому в каждом классе четности по \(512\) точек. Экспоненциальная часть привязана к очень малой размерности; практическая трудность заключается в поиске подходящего \(m\) и в эффективном отсечении комбинаторного перебора.
تطلب المسألة 983 أصغر قيمة لـ \(R(n)^2\) تسمح ببناء عائلة كبيرة بما يكفي من الدوائر المتناغمة ذات نصف القطر نفسه. تعتمد الحلول هنا على شبكة الأعداد الصحيحة: كل اتجاه مختار هو نقطة شبكية على الدائرة \(x^2+y^2=R(n)^2\)، ومراكز الدوائر الفعلية تُبنى من مجاميع المجموعات الجزئية لهذه الاتجاهات، وأي تقاطع متعدد غير تافه بين الدوائر المختارة يجب أن يكون هو نفسه نقطة تقاطع مميزة ناتجة عن البناء نفسه.
الفكرة الحاسمة هي أن الشيفرات لا تبحث مباشرة عن \(n\) دوائر مستقلة. بدلًا من ذلك تُقسِّم مجاميع المجموعات الجزئية إلى فئتين بحسب الزوجية: فئة تعطي مراكز الدوائر، وفئة تعطي نقاط التقاطع المسموح بها. إذا اخترنا \(d\) اتجاهات، فكل فئة تحتوي على \(2^{d-1}\) نقطة، ولذلك تستخدم الحلول عند \(n>2\) البعد
$$d=\min\{t\ge 1:2^{t-1}\ge n\}.$$
بعد ذلك يُجرَّب \(m=1,2,3,\dots\) تصاعديًا حتى تصبح الدائرة \(x^2+y^2=m\) مناسبة لمثل هذا البناء ذي البعد \(d\).
يقوم الأساس الرياضي كله على ثلاثة عناصر: متجهات شبكية متساوية الطول، ومجاميع مجموعات جزئية، وشرط دقيق يحدد أي تقاطعات للدوائر تُعد مقبولة.
عندما يكون \(n\le 2\) تكون المسألة تافهة، ولذلك تعيد الحلول مباشرة \(R(n)^2=1\). أما عندما يكبر \(n\)، فتُختار \(d\) متجهات \(v_1,\dots,v_d\) ولكل منها الطول التربيعي نفسه \(m\). ثم نعرّف المجموعتين
$$E=\left\{\sum_{i\in A} v_i:\ |A|\equiv 0 \pmod 2\right\},\qquad O=\left\{\sum_{i\in A} v_i:\ |A|\equiv 1 \pmod 2\right\}.$$
المجموعة \(E\) هي عائلة مراكز الدوائر التي تحسبها الخوارزمية فعلًا، أما \(O\) فهي عائلة نقاط التقاطع التي يُسمح لهذه الدوائر أن تشترك فيها. ولكل من المجموعتين حجم يساوي \(2^{d-1}\)، ولهذا يكفي أصغر \(d\) يحقق \(2^{d-1}\ge n\).
لعدد ثابت \(m\) نكتب
$$\Lambda_m=\{(x,y)\in\mathbb{Z}^2:x^2+y^2=m\}.$$
كل اتجاه مختار يجب أن يأتي من \(\Lambda_m\). وبما أن \(v\) و\(-v\) يعطيان المحور الهندسي نفسه مع تبادل في دور الزوجية، فإن البحث يحتفظ بممثل واحد فقط من كل زوج متقابل \(\{v,-v\}\). لذلك إذا كان عدد الأزواج المتقابلة في \(\Lambda_m\) أقل من \(d\)، فإن هذا \(m\) يُرفض مباشرة.
المرشح العددي السريع في الحلول هو معيار مجموع مربعين. فإذا كان
$$m=2^a\prod_i p_i^{\alpha_i}\prod_j q_j^{2\beta_j},\qquad p_i\equiv 1 \pmod 4,\quad q_j\equiv 3 \pmod 4,$$
فإن
$$|\Lambda_m|=4\prod_i(\alpha_i+1),\qquad N_{\mathrm{opp}}(m)=\frac{|\Lambda_m|}{2}=2\prod_i(\alpha_i+1).$$
أما إذا ظهر عدد أولي \(q\equiv 3 \pmod 4\) بأس فردي، فإن \(\Lambda_m\) تكون خالية أصلًا، ولهذا يُتجاوز هذا \(m\) فورًا.
خذ أي مركز زوجي \(e\in E\). إذا لم تكن المجموعة الجزئية التي تُنتج \(e\) تحتوي على \(i\)، فإن \(e+v_i\in O\)، وإذا كانت تحتوي عليه فإن \(e-v_i\in O\). وبما أن كل \(v_i\) يقع على \(x^2+y^2=m\)، فإن كل نقطة من هذا النوع في \(O\) تقع على الدائرة ذات نصف القطر \(\sqrt m\) والمركز \(e\). إذًا فكل دائرة مركزها في \(E\) تأتي طبيعيًا مع \(d\) نقاط تقاطع مقصودة من \(O\).
وبالنظر بالعكس، فإن كل \(o\in O\) يختلف عن \(d\) نقاط من \(E\) بمتجهات من \(\Lambda_m\)، وهذا يعني أن كل نقطة فردية تقع على \(d\) دوائر من العائلة. وهكذا تنشأ بنية ثنائية تقابل تمامًا مخطط المكعب ذي البعد \(d\): تغيير اتجاه واحد فقط يبدل الزوجية وينقلنا بمتجه شبكي طوله \(\sqrt m\).
تشترط الحلول أن يكون التطبيق \(A\mapsto \sum_{i\in A}v_i\) حقنيًا على المجموعات الزوجية وحدها، وحقنيًا أيضًا على المجموعات الفردية وحدها. أي إن أي علاقة غير تافهة من الشكل
$$\sum_{i\in A}v_i=\sum_{i\in B}v_i,\qquad |A|\equiv |B|\pmod 2,\ A\ne B$$
تؤدي إلى رفض المرشح. فإذا وقع هذا التصادم داخل \(E\)، فذلك يعني أن دائرتين مختلفتين تنهاران إلى المركز نفسه. وإذا وقع داخل \(O\)، فهذا يدمج نقطتي تقاطع كان ينبغي أن تبقيا مختلفتين. وهذا هو أول اختبار دقيق بعد اختيار الاتجاهات.
الشرط الأعمق هو أن أي نقطة خارج \(O\) لا يجوز أن تقع على دائرتين مركزاهما في \(E\). ولهذا، لكل \(e\in E\) و\(u\in \Lambda_m\)، ننظر إلى النقطة \(z=e+u\)، وهي بالتأكيد على الدائرة ذات المركز \(e\). إذا كانت \(z\in O\)، فهذا تقاطع مقصود ومسموح له بأن يقع على أكثر من دائرة. أما إذا كانت \(z\notin O\)، فيجب أن لا تحتوي الدائرة المزاحة \(z+\Lambda_m\) على نقطة ثانية من \(E\). والشرط الذي تتحقق منه الشيفرة حرفيًا هو
$$z\notin O\ \Longrightarrow\ |(z+\Lambda_m)\cap E|<2.$$
وهذا هو جوهر شرط التناغم: كل تقاطع متعدد حقيقي يجب أن يأتي من النقاط الفردية المخصصة، لا من نقاط أخرى في المستوى.
لكي تُستبعد الفروع الميؤوس منها مبكرًا، تبني الحلول مسبقًا المجموعة
$$\Delta_m=\{a-b:\ a,b\in \Lambda_m,\ a\ne b\}.$$
إذا وقعت نقطتان زوجيتان على الدائرة المزاحة نفسها ذات نصف القطر \(\sqrt m\)، فلا بد أن يكون فرقُهما عنصرًا في \(\Delta_m\). وفروق المجاميع الزوجية هي مجاميع موقعة لعدد زوجي من الاتجاهات المختارة. الفروق ذات الحدين تمثل تقاطعات فردية مشروعة، ولذلك تبدأ العوائق الخطرة فعلًا عند أربعة اتجاهات. أثناء البحث العمقي تُفحَص لكل رباعية جديدة التركيبات الست عشرة
$$\pm v_i\pm v_j\pm v_k\pm v_\ell,$$
وبمجرد أن تقع قيمة غير صفرية داخل \(\Delta_m\)، يُقطَع ذلك الفرع فورًا. هذا ليس البرهان الكامل على الصحة، لكنه مرشح ضروري قوي جدًا قبل الفحص النهائي الكامل.
عند \(n=4\) تحتاج الحلول إلى \(d=3\)، لأن \(2^{3-1}=4\). خذ \(m=5\)، وعندها
$$\Lambda_5=\{(\pm 2,\pm 1),(\pm 1,\pm 2)\}.$$
يمكن اختيار
$$v_1=(2,1),\qquad v_2=(2,-1),\qquad v_3=(1,2).$$
فتكون المجاميع الزوجية
$$E=\{(0,0),(4,0),(3,3),(3,1)\},$$
والمجاميع الفردية
$$O=\{(2,1),(2,-1),(1,2),(5,2)\}.$$
وبذلك نحصل على أربع دوائر نصف قطرها \(\sqrt 5\) ومراكزها هي نقاط \(E\). الدائرة التي مركزها \((0,0)\) تمر بالنقاط \((2,1)\) و\((2,-1)\) و\((1,2)\)، والدائرة التي مركزها \((4,0)\) تمر بالنقاط \((2,1)\) و\((2,-1)\) و\((5,2)\)، وتعمل الدائرتان الأخريان بالطريقة نفسها. إذن فإن نقاط \(O\) هي بالضبط نقاط التقاطع المشتركة المقصودة، والفحص الكامل يؤكد عدم وجود أي تقاطع مزدوج آخر، ولهذا تكون قيمة الفحص \(R(4)^2=5\).
تبدأ تطبيقات C++ وPython وJava بتحويل \(n\) إلى البعد المطلوب \(d\)، مع استخدام الجواب التافه \(R(n)^2=1\) فورًا إذا كان \(n\le 2\). بعد ذلك تمر على \(m=1,2,3,\dots\). ولكل \(m\)، تُحسب بسرعة قيمة عدد الأزواج المتقابلة من خلال التحليل إلى عوامل أولية؛ فإذا كانت أقل من \(d\)، يُرفض المرشح مباشرة.
إذا اجتاز \(m\) الفلتر العددي، تُحصى كل النقاط الشبكية على \(x^2+y^2=m\)، وتُجمَع في أزواج متقابلة، ثم يُحتفَظ بممثل قانوني واحد من كل زوج. بعد ذلك يجرّب بحث عمقي جميع الاختيارات الممكنة لـ \(d\) ممثلين. وفي كل خطوة تُستخدم المجموعة \(\Delta_m\): فإذا كانت رباعية جديدة تولّد بالفعل مجموعًا موقعًا ممنوعًا، يُهمَل الفرع قبل حساب مجاميع المجموعات الجزئية كلها.
البحث الرياضي واحد في اللغات الثلاث. وتمتاز نسخة C++ فقط بأنها توازي الفروع العليا الخاصة باختيار الممثل الأول، بينما تنفذ نسختا Python وJava المنطق نفسه على نحو تسلسلي.
بعد اختيار \(d\) اتجاهات، تُولِّد الحلول كل \(2^d\) من مجاميع المجموعات الجزئية، ثم تقسِّمها إلى \(E\) و\(O\)، وتفحص الحقن داخل كل فئة. وإذا نجح هذا الاختبار، يُطبَّق الشرط \(z\notin O \Rightarrow |(z+\Lambda_m)\cap E|<2\). وأول \(m\) ينجح في جميع الاختبارات يُعاد بوصفه أصغر قيمة لـ \(R(n)^2\).
تتحقق الاختبارات المضمنة من أول الحالات غير التافهة \(R(2)^2=1\) و\(R(4)^2=5\)، كما تضيف نسخة C++ اختبارًا إضافيًا للرتابة عند قيم صغيرة من \(n\).
الحلقة الخارجية على \(m\) غير محدودة سلفًا من الناحية النظرية، لأن الخوارزمية لا تتوقف إلا عند أول مربع نصف قطر صالح. أما عند تثبيت \(m\)، فإن التحليل بالعوامل الأولية بطريقة القسمة التجريبية، وكذلك تعداد النقاط الشبكية، يكلفان \(O(\sqrt m)\) في هذه التطبيقات.
إذا كتبنا \(L=|\Lambda_m|\) و\(u=L/2\)، فإن بناء \(\Delta_m\) يحتاج إلى \(O(L^2)\) زمنًا وذاكرة. والبحث في اختيارات الاتجاهات ذو طبيعة تركيبية في أسوأ الأحوال، حتى \(O\!\left(\binom{u}{d}\right)\) فرعًا، وإن كان تقليم الرباعيات يقلل ذلك كثيرًا عمليًا. وبالنسبة إلى مرشح كامل، فإن توليد جميع مجاميع المجموعات الجزئية يكلف \(O(d\,2^d)\)، أما فحص الدوائر المزاحة فيكلف \(O(2^{d-1}L^2)\).
بالنسبة إلى الهدف الفعلي \(n=500\)، يكون \(d=10\)، وبالتالي تحتوي كل فئة زوجية على \(512\) نقطة. لذلك فإن الجزء الأسي مربوط ببعد صغير جدًا؛ أما الصعوبة العملية فهي العثور على \(m\) مناسب، ثم تقليم البحث التركيبي بما يكفي.