We seek the number of integers \(n \lt 5 \times 10^7\) for which the equation \(x^2 - y^2 - z^2 = n\) has exactly one solution in positive integers, under the extra condition that \(x\), \(y\), and \(z\) are consecutive terms of an arithmetic progression. Because the progression condition ties the three variables together, the real task is not an unrestricted three-variable search but a structured counting problem over admissible factorizations of \(n\).
The C++, Python, and Java implementations do not test each \(n\) separately. Instead they enumerate every valid progression once, convert it into the corresponding value of \(n\), and keep only the information needed to distinguish “zero solutions”, “one solution”, and “more than one solution”.
The key step is to rewrite the arithmetic progression in terms of its middle term and common difference, then convert the resulting quadratic expression into a product with simple congruence and inequality constraints.
If \(x\), \(y\), and \(z\) are in arithmetic progression with positive common difference \(d\), then we may write
$$x = y + d,\qquad z = y - d,\qquad d \ge 1,\qquad y \gt d.$$
Substituting into the equation gives
$$n = (y+d)^2 - y^2 - (y-d)^2 = 4yd - y^2 = y(4d-y).$$
So every solution is encoded by a positive middle term \(y\) and a second positive integer \(4d-y\).
Introduce the variables
$$u = y,\qquad v = 4d-y.$$
Then the equation becomes simply
$$n = uv.$$
This transformation is reversible. From an admissible pair \((u,v)\) we recover
$$d = \frac{u+v}{4},\qquad x = u+d = \frac{5u+v}{4},\qquad z = u-d = \frac{3u-v}{4}.$$
Therefore a pair \((u,v)\) corresponds to a valid solution exactly when
$$u \ge 1,\qquad v \ge 1,\qquad u+v \equiv 0 \pmod 4,$$
and, because \(z \gt 0\),
$$\frac{u+v}{4} \lt u \qquad\Longleftrightarrow\qquad v \lt 3u.$$
So the number of representations of \(n\) is precisely the number of factor pairs \((u,v)\) satisfying
$$uv=n,\qquad u+v \equiv 0 \pmod 4,\qquad 1 \le v \lt 3u.$$
Starting from a progression solution, the formulas above produce one admissible pair \((u,v)\). Starting from an admissible pair, the inverse formulas produce integers \(d\), \(x\), and \(z\), and the inequalities guarantee \(d \ge 1\) and \(z \gt 0\). No two different admissible pairs generate the same triple, so counting solutions to the original equation is exactly the same as counting these constrained factorizations.
That is the decisive simplification: a quadratic Diophantine problem in three variables becomes a sieve over products \(uv\) with one modular condition and one linear bound.
For \(n=3\), the admissible factorizations are extremely limited. The pair \((u,v)=(3,1)\) satisfies \(uv=3\), \(u+v=4\), and \(v\lt 3u\). Then
$$d=\frac{3+1}{4}=1,\qquad (x,y,z)=(4,3,2).$$
No other factor pair of 3 passes the same tests, so \(n=3\) is counted.
For \(n=15\), however, there are two admissible pairs: \((u,v)=(3,5)\) and \((u,v)=(5,3)\). They lead to the two progressions
$$ (x,y,z)=(5,3,1),\qquad (x,y,z)=(7,5,3). $$
Thus 15 does not qualify for Problem 136, because its number of solutions is 2 rather than 1.
Once the representation count is rephrased in terms of \((u,v)\), the algorithm is natural. For each positive \(u\), every admissible \(v\) must satisfy
$$v \le \left\lfloor\frac{N-1}{u}\right\rfloor$$
to keep \(n=uv\) below the limit \(N=5\times 10^7\), and also
$$v \le 3u-1$$
because \(v\lt 3u\) and \(v\) is integral. The congruence \(u+v\equiv 0\pmod 4\) means that valid values of \(v\) form a single arithmetic progression modulo 4. So for each \(u\), the implementation jumps directly through the compatible \(v\)-values, marks the product \(uv\), and increases its representation count.
Because the problem only asks whether the count is exactly 1, there is no reason to store large multiplicities. As soon as a value of \(n\) has been seen twice, it is already known not to be a singleton, so the stored count can be saturated at 2.
The C++, Python, and Java implementations allocate a counter table for \(0,1,\dots,N-1\), where \(N=5\times 10^7\). They then loop over every positive candidate for the middle term and compute the largest companion factor allowed by the product bound and the inequality \(v\lt 3u\).
For each fixed middle term, the first compatible companion factor is the smallest positive integer in the residue class \(v \equiv -u \pmod 4\). Advancing by 4 preserves the integrality of \(d=(u+v)/4\), so every loop iteration corresponds to one genuine arithmetic progression solution. The value \(n=uv\) is formed and the counter for that \(n\) is increased, but only up to 2.
The implementations do not need the exact number of representations once it exceeds 1. They only need to distinguish the three states “not seen yet”, “seen exactly once”, and “seen at least twice”. That is why a byte-sized table is enough even at the full bound: each cell stores a tiny saturated count rather than an unrestricted integer.
After the sieve phase, the algorithm performs one linear pass through the table and counts how many entries are equal to 1. That total is the required answer.
One implementation also includes a small checkpoint: below 100 there are 25 qualifying values. This is a useful sanity check because it validates the derivation and the congruence logic before the full \(5\times 10^7\) computation is attempted.
Let \(N\) be the search bound. For a fixed \(u\), the number of admissible companion factors is
$$O\!\left(\min\!\left(u,\frac{N}{u}\right)\right),$$
up to the constant factor coming from the step size 4. Summing over all \(u\) gives
$$\sum_{u=1}^{N-1} O\!\left(\min\!\left(u,\frac{N}{u}\right)\right)=O(N\log N).$$
So the sieve phase runs in \(O(N\log N)\) time, and the final pass over the counter table is \(O(N)\). The memory usage is \(O(N)\) bytes for the saturated counter array. At \(N=5\times 10^7\), that is large but still practical in the compiled implementations, and it is exactly why the algorithm avoids storing full solution lists.
Gesucht ist die Anzahl der ganzen Zahlen \(n \lt 5 \times 10^7\), für die die Gleichung \(x^2 - y^2 - z^2 = n\) unter positiven ganzen Zahlen genau eine Lösung besitzt, wobei \(x\), \(y\) und \(z\) aufeinanderfolgende Glieder einer arithmetischen Folge sind. Wegen dieser Zusatzbedingung ist das Problem keine freie Suche in drei Variablen, sondern ein strukturiertes Zählproblem über zulässige Faktorisierungen von \(n\).
Die Implementierungen prüfen also nicht jedes \(n\) einzeln. Stattdessen erzeugen sie jede gültige Folge genau einmal, berechnen daraus den zugehörigen Wert von \(n\) und speichern nur die Information, ob \(n\) noch keine, genau eine oder bereits mehrere Darstellungen besitzt.
Der entscheidende Schritt besteht darin, die arithmetische Folge durch ihr mittleres Glied und ihre Differenz zu beschreiben und den quadratischen Ausdruck danach in ein Produkt mit einfachen Kongruenz- und Ungleichungsbedingungen umzuschreiben.
Wenn \(x\), \(y\) und \(z\) in einer arithmetischen Folge mit positiver Differenz \(d\) liegen, kann man schreiben
$$x = y + d,\qquad z = y - d,\qquad d \ge 1,\qquad y \gt d.$$
Einsetzen in die Gleichung liefert
$$n = (y+d)^2 - y^2 - (y-d)^2 = 4yd - y^2 = y(4d-y).$$
Jede Lösung wird also durch das positive Mittelglied \(y\) und die zweite positive Zahl \(4d-y\) codiert.
Führen wir die Variablen
$$u = y,\qquad v = 4d-y$$
ein. Dann wird die Gleichung einfach zu
$$n = uv.$$
Diese Transformation ist umkehrbar. Aus einem zulässigen Paar \((u,v)\) erhält man
$$d = \frac{u+v}{4},\qquad x = u+d = \frac{5u+v}{4},\qquad z = u-d = \frac{3u-v}{4}.$$
Ein Paar \((u,v)\) entspricht also genau dann einer gültigen Lösung, wenn
$$u \ge 1,\qquad v \ge 1,\qquad u+v \equiv 0 \pmod 4,$$
und wegen \(z \gt 0\) außerdem
$$\frac{u+v}{4} \lt u \qquad\Longleftrightarrow\qquad v \lt 3u.$$
Damit ist die Anzahl der Darstellungen von \(n\) genau die Anzahl der Teilerpaare \((u,v)\) mit
$$uv=n,\qquad u+v \equiv 0 \pmod 4,\qquad 1 \le v \lt 3u.$$
Ausgehend von einer Lösung in arithmetischer Folge erzeugen die Formeln oben genau ein zulässiges Paar \((u,v)\). Umgekehrt liefern die inversen Formeln aus jedem zulässigen Paar ganze Zahlen \(d\), \(x\) und \(z\), und die Ungleichungen garantieren \(d \ge 1\) sowie \(z \gt 0\). Zwei verschiedene zulässige Paare können daher nicht dieselbe Dreierfolge erzeugen. Das Zählen der ursprünglichen Lösungen ist also exakt dasselbe wie das Zählen dieser eingeschränkten Faktorisierungen.
Genau darin liegt die Vereinfachung: Aus einer quadratischen diophantischen Gleichung in drei Variablen wird ein Sieb über Produkte \(uv\) mit einer modularen Bedingung und einer linearen Schranke.
Für \(n=3\) sind die zulässigen Faktorisierungen sehr rar. Das Paar \((u,v)=(3,1)\) erfüllt \(uv=3\), \(u+v=4\) und \(v\lt 3u\). Dann ist
$$d=\frac{3+1}{4}=1,\qquad (x,y,z)=(4,3,2).$$
Kein anderes Teilerpaar von 3 erfüllt dieselben Bedingungen, also wird \(n=3\) gezählt.
Für \(n=15\) gibt es dagegen zwei zulässige Paare: \((u,v)=(3,5)\) und \((u,v)=(5,3)\). Daraus entstehen die beiden Folgen
$$ (x,y,z)=(5,3,1),\qquad (x,y,z)=(7,5,3). $$
Deshalb zählt 15 nicht zu den gesuchten Werten, denn die Zahl der Lösungen ist 2 und nicht 1.
Sobald die Darstellungsanzahl über \((u,v)\) formuliert ist, ergibt sich der Algorithmus direkt. Für jedes positive \(u\) muss jedes zulässige \(v\) die Bedingung
$$v \le \left\lfloor\frac{N-1}{u}\right\rfloor$$
erfüllen, damit \(n=uv\) unter der Grenze \(N=5\times 10^7\) bleibt, und zusätzlich
$$v \le 3u-1,$$
weil \(v\lt 3u\) gilt und \(v\) ganzzahlig ist. Die Kongruenz \(u+v\equiv 0\pmod 4\) bedeutet, dass die gültigen Werte von \(v\) genau eine Restklasse modulo 4 bilden. Die Implementierung springt für jedes \(u\) also direkt durch diese passenden \(v\)-Werte, markiert das Produkt \(uv\) und erhöht den Darstellungszähler.
Da nur gefragt ist, ob der Zähler genau 1 ist, müssen große Vielfachheiten nicht gespeichert werden. Sobald ein Wert von \(n\) zum zweiten Mal erreicht wurde, ist bereits klar, dass er nicht mehr eindeutig ist, also genügt eine Sättigung bei 2.
Die C++-, Python- und Java-Implementierungen legen zunächst eine Zähltafel für \(0,1,\dots,N-1\) mit \(N=5\times 10^7\) an. Danach laufen sie alle positiven Kandidaten für das Mittelglied durch und berechnen den größten zugehörigen Faktor, der sowohl die Produktschranke als auch die Ungleichung \(v\lt 3u\) erfüllt.
Für jedes feste Mittelglied ist der erste kompatible Faktor der kleinste positive Vertreter der Restklasse \(v \equiv -u \pmod 4\). Jeder Sprung um 4 erhält die Ganzzahligkeit von \(d=(u+v)/4\), daher entspricht jede Schleifeniteration genau einer echten Lösung in arithmetischer Folge. Der Wert \(n=uv\) wird gebildet, und sein Zähler wird erhöht, aber nur bis maximal 2.
Sobald die Zahl der Darstellungen größer als 1 ist, braucht die Implementierung ihren exakten Wert nicht mehr. Es genügt, die drei Zustände „noch nicht gesehen“, „genau einmal gesehen“ und „mindestens zweimal gesehen“ zu unterscheiden. Deshalb reicht ein byteweiser Zähler auch bei der vollen Schranke aus.
Nach der Siebphase folgt ein linearer Durchlauf über die Tabelle. Dabei wird gezählt, wie viele Einträge gleich 1 sind. Genau diese Anzahl ist die gesuchte Antwort.
Eine Implementierung enthält zusätzlich einen kleinen Kontrollwert: Unterhalb von 100 gibt es 25 zulässige Werte. Dieser Test ist nützlich, weil er die Herleitung und die Kongruenzlogik überprüft, bevor die volle Rechnung bis \(5\times 10^7\) gestartet wird.
Sei \(N\) die Suchgrenze. Für ein festes \(u\) ist die Anzahl der zulässigen Begleitfaktoren
$$O\!\left(\min\!\left(u,\frac{N}{u}\right)\right),$$
bis auf den konstanten Faktor, der von der Schrittweite 4 stammt. Aufsummiert über alle \(u\) ergibt das
$$\sum_{u=1}^{N-1} O\!\left(\min\!\left(u,\frac{N}{u}\right)\right)=O(N\log N).$$
Die Siebphase benötigt also \(O(N\log N)\) Zeit, und der abschließende Durchlauf über die Zähltafel ist \(O(N)\). Der Speicherverbrauch beträgt \(O(N)\) Bytes für das gesättigte Zählerfeld. Bei \(N=5\times 10^7\) ist das groß, aber in den kompilierten Implementierungen noch praktikabel, und genau deshalb speichert der Algorithmus keine vollständigen Lösungslisten.
Aranan şey, \(n \lt 5 \times 10^7\) koşulunu sağlayan sayılardan kaç tanesinin \(x^2 - y^2 - z^2 = n\) denklemi için pozitif tamsayılarda tam olarak bir çözüme sahip olduğudur; ayrıca \(x\), \(y\) ve \(z\) bir aritmetik dizinin ardışık terimleri olmalıdır. Bu ek koşul üç değişkenli serbest bir aramayı büyük ölçüde daraltır ve problemi, \(n\)'nin belirli çarpan çiftlerini sayma meselesine dönüştürür.
C++, Python ve Java uygulamaları her \(n\)'yi ayrı ayrı test etmez. Bunun yerine geçerli her ilerlemeyi tam bir kez üretir, ondan ilgili \(n\) değerini çıkarır ve yalnızca “hiç çözüm yok”, “tam bir çözüm var” ve “birden fazla çözüm var” ayrımını tutar.
Asıl fikir, aritmetik ilerlemeyi orta terim ve ortak fark üzerinden yazmak, sonra ortaya çıkan ikinci dereceden ifadeyi basit bir kongrüans ve eşitsizlik şartı taşıyan bir çarpıma dönüştürmektir.
\(x\), \(y\) ve \(z\) pozitif ortak farkı \(d\) olan bir aritmetik ilerlemenin terimleri ise
$$x = y + d,\qquad z = y - d,\qquad d \ge 1,\qquad y \gt d$$
yazılabilir. Bunu denkleme yerleştirince
$$n = (y+d)^2 - y^2 - (y-d)^2 = 4yd - y^2 = y(4d-y)$$
elde edilir. Demek ki her çözüm, pozitif orta terim \(y\) ile ikinci bir pozitif sayı \(4d-y\) tarafından kodlanır.
Şimdi
$$u = y,\qquad v = 4d-y$$
değişkenlerini tanımlayalım. Böylece denklem
$$n = uv$$
haline gelir. Bu dönüşüm tersinir. Geçerli bir \((u,v)\) çifti verildiğinde
$$d = \frac{u+v}{4},\qquad x = u+d = \frac{5u+v}{4},\qquad z = u-d = \frac{3u-v}{4}$$
geri elde edilir. O halde bir \((u,v)\) çifti ancak ve ancak
$$u \ge 1,\qquad v \ge 1,\qquad u+v \equiv 0 \pmod 4$$
ve ayrıca \(z \gt 0\) olduğu için
$$\frac{u+v}{4} \lt u \qquad\Longleftrightarrow\qquad v \lt 3u$$
şartlarını sağladığında geçerli bir çözüme karşılık gelir. Sonuç olarak \(n\)'nin temsil sayısı,
$$uv=n,\qquad u+v \equiv 0 \pmod 4,\qquad 1 \le v \lt 3u$$
koşullarını sağlayan çarpan çiftlerinin sayısıdır.
Bir aritmetik ilerleme çözümünden başlanırsa yukarıdaki formüller tek bir uygun \((u,v)\) çifti üretir. Ters yönde, uygun bir \((u,v)\) çifti verildiğinde ters formüller bize tamsayı \(d\), \(x\) ve \(z\) değerlerini verir; eşitsizlikler de \(d \ge 1\) ve \(z \gt 0\) koşullarını güvenceye alır. Farklı iki uygun çift aynı üçlüye gidemez. Bu yüzden özgün denklemin çözümlerini saymakla bu kısıtlı çarpan çiftlerini saymak tamamen aynı şeydir.
Problemdeki belirleyici sadeleşme budur: üç değişkenli ikinci dereceden diofant denklemi, tek bir modüler koşul ve tek bir doğrusal sınır içeren bir \(uv\) eleğine dönüşür.
\(n=3\) için uygun çarpanlaşmalar son derece sınırlıdır. \((u,v)=(3,1)\) çifti \(uv=3\), \(u+v=4\) ve \(v\lt 3u\) koşullarını sağlar. Buradan
$$d=\frac{3+1}{4}=1,\qquad (x,y,z)=(4,3,2)$$
çıkar. 3'ün başka hiçbir çarpan çifti aynı testlerden geçmez; dolayısıyla \(n=3\) sayılır.
\(n=15\) için ise iki uygun çift vardır: \((u,v)=(3,5)\) ve \((u,v)=(5,3)\). Bunlar iki farklı ilerleme üretir:
$$ (x,y,z)=(5,3,1),\qquad (x,y,z)=(7,5,3). $$
Bu nedenle 15, Problem 136 için uygun değildir; çünkü çözüm sayısı 1 değil 2'dir.
Temsil sayısı \((u,v)\) üzerinden ifade edildiğinde algoritma doğal biçimde ortaya çıkar. Her pozitif \(u\) için geçerli bir \(v\) hem
$$v \le \left\lfloor\frac{N-1}{u}\right\rfloor$$
koşulunu sağlamalıdır ki \(n=uv\) değeri \(N=5\times 10^7\) sınırının altında kalsın; hem de
$$v \le 3u-1$$
olmalıdır; çünkü \(v\lt 3u\) ve \(v\) tam sayıdır. Ayrıca \(u+v\equiv 0\pmod 4\) kongrüansı, uygun \(v\) değerlerinin mod 4'e göre tek bir artık sınıfı oluşturduğunu söyler. Bu yüzden uygulama her \(u\) için yalnızca uyumlu \(v\) değerleri arasında 4'er 4'er ilerler, \(uv\) çarpımını işaretler ve temsil sayısını artırır.
Problem yalnızca sayının tam olarak 1 olup olmadığını sorduğu için büyük çoklukları saklamaya gerek yoktur. Bir \(n\) değeri ikinci kez görüldüğünde artık tekil olmadığı kesinleşir; bu yüzden sayaç 2'de doyurulabilir.
C++, Python ve Java uygulamaları önce \(0,1,\dots,N-1\) için bir sayaç tablosu ayırır; burada \(N=5\times 10^7\)'dir. Sonra orta terim olabilecek bütün pozitif değerler üzerinden geçer ve hem çarpım sınırı hem de \(v\lt 3u\) eşitsizliği altında izin verilen en büyük eşlikçi çarpanı hesaplar.
Her sabit orta terim için ilk uygun eşlikçi çarpan, \(v \equiv -u \pmod 4\) artık sınıfındaki en küçük pozitif sayıdır. 4 ekleyerek ilerlemek \(d=(u+v)/4\) ifadesinin tamsayı kalmasını korur; dolayısıyla döngünün her adımı gerçek bir aritmetik ilerleme çözümüne karşılık gelir. Sonra \(n=uv\) hesaplanır ve o \(n\) için sayaç yalnızca 2'ye kadar artırılır.
Temsil sayısı 1'i geçtiğinde uygulamanın tam değeri bilmesine gerek kalmaz. Yalnızca üç durumu ayırt etmek gerekir: “henüz görülmedi”, “tam bir kez görüldü” ve “en az iki kez görüldü”. Bu nedenle tam sınırda bile byte boyutunda bir sayaç tablosu yeterlidir.
Elek aşamasından sonra algoritma tablo üzerinde tek bir doğrusal geçiş yapar ve değeri 1 olan kaç hücre bulunduğunu sayar. Aranan cevap tam olarak budur.
Uygulamalardan biri küçük bir kontrol de içerir: 100'ün altında 25 uygun değer vardır. Bu kontrol, tam \(5\times 10^7\) hesabına geçmeden önce türetmenin ve kongrüans mantığının doğru kurulduğunu sınar.
Arama sınırı \(N\) olsun. Sabit bir \(u\) için uygun eşlikçi çarpan sayısı
$$O\!\left(\min\!\left(u,\frac{N}{u}\right)\right)$$
mertebesindedir; burada mod 4 nedeniyle gelen 4'lük adım yalnızca sabit çarpan etkisindedir. Bütün \(u\) değerleri üzerinden toplanınca
$$\sum_{u=1}^{N-1} O\!\left(\min\!\left(u,\frac{N}{u}\right)\right)=O(N\log N)$$
elde edilir. Bu yüzden elek aşaması \(O(N\log N)\) zamanda çalışır, son tablo taraması ise \(O(N)\)'dir. Bellek kullanımı, doygun sayaç dizisi için \(O(N)\) bayttır. \(N=5\times 10^7\) için bu büyük olsa da derlenmiş uygulamalarda yönetilebilir düzeydedir; algoritmanın tam çözüm listeleri saklamamasının nedeni de budur.
Hay que contar cuántos enteros \(n \lt 5 \times 10^7\) tienen exactamente una solución positiva de la ecuación \(x^2 - y^2 - z^2 = n\), bajo la condición adicional de que \(x\), \(y\) y \(z\) sean términos consecutivos de una progresión aritmética. Esa restricción acopla las tres variables y convierte el problema en un conteo muy estructurado de factorizaciones admisibles de \(n\).
Las implementaciones en C++, Python y Java no recorren cada \(n\) por separado. En su lugar generan cada progresión válida una sola vez, calculan el valor de \(n\) asociado y conservan únicamente la información necesaria para distinguir entre “ninguna solución”, “exactamente una solución” y “más de una solución”.
La idea central es escribir la progresión aritmética mediante su término central y su diferencia común, y después transformar la expresión cuadrática resultante en un producto sujeto a una congruencia y a una desigualdad lineal.
Si \(x\), \(y\) y \(z\) forman una progresión aritmética con diferencia positiva \(d\), entonces podemos escribir
$$x = y + d,\qquad z = y - d,\qquad d \ge 1,\qquad y \gt d.$$
Al sustituir en la ecuación obtenemos
$$n = (y+d)^2 - y^2 - (y-d)^2 = 4yd - y^2 = y(4d-y).$$
Así, cada solución queda codificada por el término central positivo \(y\) y por otro entero positivo \(4d-y\).
Introduzcamos
$$u = y,\qquad v = 4d-y.$$
Entonces la ecuación se reduce a
$$n = uv.$$
La transformación es reversible. A partir de un par admisible \((u,v)\) se recupera
$$d = \frac{u+v}{4},\qquad x = u+d = \frac{5u+v}{4},\qquad z = u-d = \frac{3u-v}{4}.$$
Por tanto, un par \((u,v)\) corresponde a una solución válida exactamente cuando
$$u \ge 1,\qquad v \ge 1,\qquad u+v \equiv 0 \pmod 4,$$
y además, porque \(z \gt 0\),
$$\frac{u+v}{4} \lt u \qquad\Longleftrightarrow\qquad v \lt 3u.$$
En consecuencia, el número de representaciones de \(n\) es exactamente el número de pares de factores \((u,v)\) tales que
$$uv=n,\qquad u+v \equiv 0 \pmod 4,\qquad 1 \le v \lt 3u.$$
Si comenzamos con una solución de la progresión, las fórmulas anteriores producen un único par admisible \((u,v)\). En sentido inverso, si partimos de un par admisible, las fórmulas inversas devuelven enteros \(d\), \(x\) y \(z\), y las desigualdades garantizan que \(d \ge 1\) y \(z \gt 0\). Dos pares admisibles distintos no pueden dar la misma terna. Por eso contar soluciones de la ecuación original equivale exactamente a contar estas factorizaciones restringidas.
Esa es la simplificación decisiva: un problema diofántico cuadrático en tres variables se convierte en un tamiz sobre productos \(uv\) con una condición modular y una cota lineal.
Para \(n=3\), las factorizaciones admisibles son muy pocas. El par \((u,v)=(3,1)\) satisface \(uv=3\), \(u+v=4\) y \(v\lt 3u\). Entonces
$$d=\frac{3+1}{4}=1,\qquad (x,y,z)=(4,3,2).$$
Ningún otro par de factores de 3 supera las mismas pruebas, así que \(n=3\) sí se cuenta.
Para \(n=15\), en cambio, hay dos pares admisibles: \((u,v)=(3,5)\) y \((u,v)=(5,3)\). Ellos producen las dos progresiones
$$ (x,y,z)=(5,3,1),\qquad (x,y,z)=(7,5,3). $$
Por lo tanto, 15 no cuenta para el problema, porque su número de soluciones es 2 y no 1.
Una vez que el número de representaciones se expresa en términos de \((u,v)\), el algoritmo sale de forma natural. Para cada \(u\) positivo, todo \(v\) admisible debe satisfacer
$$v \le \left\lfloor\frac{N-1}{u}\right\rfloor$$
para mantener \(n=uv\) por debajo del límite \(N=5\times 10^7\), y también
$$v \le 3u-1$$
porque \(v\lt 3u\) y \(v\) es entero. La congruencia \(u+v\equiv 0\pmod 4\) implica que los valores válidos de \(v\) forman una sola clase residual módulo 4. Por eso la implementación recorre directamente esos \(v\) compatibles, marca el producto \(uv\) y aumenta su contador de representaciones.
Como el problema solo pregunta si el contador es exactamente 1, no hace falta almacenar multiplicidades grandes. En cuanto un valor de \(n\) aparece por segunda vez, ya sabemos que deja de ser un caso único, de modo que el contador puede saturarse en 2.
Las implementaciones en C++, Python y Java reservan una tabla de contadores para \(0,1,\dots,N-1\), con \(N=5\times 10^7\). Después recorren todos los candidatos positivos al término central y calculan el mayor factor acompañante permitido por la cota del producto y por la desigualdad \(v\lt 3u\).
Para cada término central fijo, el primer factor compatible es el menor entero positivo de la clase residual \(v \equiv -u \pmod 4\). Avanzar de 4 en 4 conserva la integridad de \(d=(u+v)/4\), así que cada iteración corresponde a una solución real de la progresión aritmética. Se forma el valor \(n=uv\) y el contador de ese \(n\) se incrementa, pero solo hasta 2.
Una vez que el número de representaciones supera 1, ya no importa conocer su valor exacto. Solo hace falta distinguir tres estados: “todavía no apareció”, “apareció exactamente una vez” y “apareció al menos dos veces”. Por eso una tabla de bytes es suficiente incluso en el límite completo.
Tras la fase de tamiz, el algoritmo hace una pasada lineal por la tabla y cuenta cuántas entradas son iguales a 1. Ese total es la respuesta pedida.
Una de las implementaciones incluye además una comprobación pequeña: por debajo de 100 existen 25 valores válidos. Es una verificación útil, porque confirma la derivación y la lógica modular antes de intentar el cálculo completo hasta \(5\times 10^7\).
Sea \(N\) el límite de búsqueda. Para un \(u\) fijo, el número de factores acompañantes admisibles es
$$O\!\left(\min\!\left(u,\frac{N}{u}\right)\right),$$
salvo por el factor constante asociado al salto de 4. Al sumar sobre todos los \(u\) se obtiene
$$\sum_{u=1}^{N-1} O\!\left(\min\!\left(u,\frac{N}{u}\right)\right)=O(N\log N).$$
Así, la fase de tamiz cuesta \(O(N\log N)\) y la pasada final por la tabla cuesta \(O(N)\). El uso de memoria es \(O(N)\) bytes para el arreglo saturado de contadores. En \(N=5\times 10^7\) es grande, pero sigue siendo razonable en las versiones compiladas, y precisamente por eso el método evita almacenar listas completas de soluciones.
题目要求统计有多少个整数 \(n \lt 5 \times 10^7\)，使得方程 \(x^2 - y^2 - z^2 = n\) 在正整数范围内恰好有一组解，并且 \(x\)、\(y\)、\(z\) 必须是同一个等差数列中的相邻三项。这个等差条件把三个变量强烈地绑定在一起，因此问题的本质并不是暴力搜索三元组，而是统计满足特定约束的因子对。
C++、Python 和 Java 的实现都不是对每个 \(n\) 单独求解。它们做的是把每一个合法的等差三元组恰好枚举一次，把它映射成对应的 \(n\)，然后只记录这个 \(n\) 目前出现了 0 次、1 次还是至少 2 次。
关键步骤是先用等差数列的中项和公差来重写三元组，再把得到的二次表达式改写成一个带有模条件和线性不等式的乘积。
如果 \(x\)、\(y\)、\(z\) 构成公差为正整数 \(d\) 的等差数列，那么可以写成
$$x = y + d,\qquad z = y - d,\qquad d \ge 1,\qquad y \gt d.$$
代入题目中的方程后得到
$$n = (y+d)^2 - y^2 - (y-d)^2 = 4yd - y^2 = y(4d-y).$$
也就是说，每一个解都可以由正的中项 \(y\) 与另一个正整数 \(4d-y\) 来编码。
引入新变量
$$u = y,\qquad v = 4d-y.$$
于是方程就变成了
$$n = uv.$$
这个变换是可逆的。只要给定一个可行的 \((u,v)\)，就能恢复出
$$d = \frac{u+v}{4},\qquad x = u+d = \frac{5u+v}{4},\qquad z = u-d = \frac{3u-v}{4}.$$
因此，一个因子对 \((u,v)\) 与原问题中的一个合法解对应，当且仅当它满足
$$u \ge 1,\qquad v \ge 1,\qquad u+v \equiv 0 \pmod 4,$$
并且由于 \(z \gt 0\)，还必须有
$$\frac{u+v}{4} \lt u \qquad\Longleftrightarrow\qquad v \lt 3u.$$
于是，\(n\) 的表示个数就等于满足下面条件的因子对个数：
$$uv=n,\qquad u+v \equiv 0 \pmod 4,\qquad 1 \le v \lt 3u.$$
从一个合法的等差三元组出发，上面的公式会得到唯一一个可行因子对 \((u,v)\)。反过来，如果从一个满足条件的 \((u,v)\) 出发，逆公式会给出整数 \(d\)、\(x\)、\(z\)，而不等式又保证了 \(d \ge 1\) 且 \(z \gt 0\)。不同的可行因子对不可能生成同一个三元组，所以“统计原方程的解数”和“统计这些受约束的因子对数”完全等价。
这一步才是整道题的核心简化：三变量的二次丢番图问题被压缩成了一个关于乘积 \(uv\) 的筛法问题，只剩下一条模 4 约束和一条线性上界。
先看 \(n=3\)。它几乎没有可行的分解。因子对 \((u,v)=(3,1)\) 满足 \(uv=3\)、\(u+v=4\) 且 \(v\lt 3u\)。于是
$$d=\frac{3+1}{4}=1,\qquad (x,y,z)=(4,3,2).$$
3 的其他因子对都不能同时通过这些条件，所以 \(n=3\) 是一个会被计入的值。
再看 \(n=15\)。这一次有两个可行因子对：\((u,v)=(3,5)\) 和 \((u,v)=(5,3)\)。它们对应两组不同的等差三元组
$$ (x,y,z)=(5,3,1),\qquad (x,y,z)=(7,5,3). $$
因此 15 不属于题目要统计的范围，因为它的解数是 2 而不是 1。
一旦把解数改写为 \((u,v)\) 的计数，算法就非常自然。对于每个正整数 \(u\)，合法的 \(v\) 必须满足
$$v \le \left\lfloor\frac{N-1}{u}\right\rfloor$$
这样 \(n=uv\) 才会落在上界 \(N=5\times 10^7\) 之下；同时还必须满足
$$v \le 3u-1,$$
因为 \(v\lt 3u\) 且 \(v\) 是整数。再加上 \(u+v\equiv 0\pmod 4\)，说明可行的 \(v\) 恰好落在模 4 的某一个剩余类中。于是实现可以对每个 \(u\) 只枚举这些相容的 \(v\)，每次得到一个乘积 \(uv\)，并把对应的表示次数加一。
由于题目只关心“是否恰好为 1”，没有必要保存很大的计数值。某个 \(n\) 一旦被命中两次，就已经确定它不再属于“恰好一个解”的情形，所以表中的计数可以直接在 2 处饱和。
C++、Python 和 Java 的实现都会先分配一个长度为 \(N=5\times 10^7\) 的计数表，对应 \(0,1,\dots,N-1\)。随后它们遍历所有可能的中项，并计算同时满足乘积上界和 \(v\lt 3u\) 的最大伴随因子。
对固定的中项来说，第一项可行的伴随因子就是满足 \(v \equiv -u \pmod 4\) 的最小正整数。之后每次加 4，都会保持 \(d=(u+v)/4\) 仍为整数，因此循环中的每一步都对应原题中的一个真实解。接着程序形成 \(n=uv\)，并把该 \(n\) 的计数增加，但最多只加到 2。
当某个 \(n\) 的表示次数已经超过 1 时，程序不再需要知道它到底是 2、3 还是更多。真正需要区分的只有三种状态：“还没出现”、“正好出现一次”和“至少出现两次”。因此，一个按字节存储的饱和计数表已经完全足够。
筛法阶段结束后，算法再对整张表做一次线性扫描，统计有多少个位置的值恰好等于 1。这个总数就是题目的答案。
其中一个实现还附带了一个很小的校验点：在 100 以下，满足条件的 \(n\) 一共有 25 个。这个检查可以在正式跑到 \(5\times 10^7\) 之前，先验证推导和模条件是否都正确。
记搜索上界为 \(N\)。对于固定的 \(u\)，可行伴随因子的个数规模为
$$O\!\left(\min\!\left(u,\frac{N}{u}\right)\right),$$
模 4 的步长只带来常数因子。把这个数量对所有 \(u\) 求和，得到
$$\sum_{u=1}^{N-1} O\!\left(\min\!\left(u,\frac{N}{u}\right)\right)=O(N\log N).$$
所以筛法主过程的时间复杂度是 \(O(N\log N)\)，最后一次表扫描是 \(O(N)\)。内存复杂度是 \(O(N)\) 字节，对应那张饱和计数表。在 \(N=5\times 10^7\) 时这并不小，但在编译型实现中依然可行，而这也正是算法不去保存完整解列表的原因。
Нужно подсчитать, сколько целых чисел \(n \lt 5 \times 10^7\) имеют ровно одно положительное решение уравнения \(x^2 - y^2 - z^2 = n\), если \(x\), \(y\) и \(z\) являются соседними членами арифметической прогрессии. Это условие резко уменьшает пространство поиска: вместо произвольного перебора троек задача сводится к подсчету допустимых факторизаций числа \(n\).
Реализации на C++, Python и Java не рассматривают каждое \(n\) отдельно. Они перечисляют каждую допустимую прогрессию ровно один раз, переводят ее в соответствующее значение \(n\) и хранят только то, что действительно нужно: не встречалось ли это \(n\), встретилось ровно один раз или уже встретилось как минимум дважды.
Ключевая идея состоит в том, чтобы записать арифметическую прогрессию через средний член и разность, а затем превратить полученное квадратное выражение в произведение с простым модульным условием и линейным ограничением.
Если \(x\), \(y\) и \(z\) образуют арифметическую прогрессию с положительной разностью \(d\), то можно написать
$$x = y + d,\qquad z = y - d,\qquad d \ge 1,\qquad y \gt d.$$
После подстановки в исходное уравнение получаем
$$n = (y+d)^2 - y^2 - (y-d)^2 = 4yd - y^2 = y(4d-y).$$
Значит, каждое решение кодируется положительным средним членом \(y\) и еще одним положительным числом \(4d-y\).
Введем переменные
$$u = y,\qquad v = 4d-y.$$
Тогда уравнение принимает вид
$$n = uv.$$
Преобразование обратимо. По допустимой паре \((u,v)\) можно восстановить
$$d = \frac{u+v}{4},\qquad x = u+d = \frac{5u+v}{4},\qquad z = u-d = \frac{3u-v}{4}.$$
Следовательно, пара \((u,v)\) соответствует допустимому решению тогда и только тогда, когда выполнено
$$u \ge 1,\qquad v \ge 1,\qquad u+v \equiv 0 \pmod 4,$$
и дополнительно, поскольку \(z \gt 0\),
$$\frac{u+v}{4} \lt u \qquad\Longleftrightarrow\qquad v \lt 3u.$$
Тем самым число представлений \(n\) равно количеству пар множителей \((u,v)\), удовлетворяющих условиям
$$uv=n,\qquad u+v \equiv 0 \pmod 4,\qquad 1 \le v \lt 3u.$$
Если начать с решения исходной задачи, приведенные формулы дадут единственную допустимую пару \((u,v)\). Если же начать с допустимой пары, обратные формулы вернут целые \(d\), \(x\) и \(z\), а неравенства обеспечат \(d \ge 1\) и \(z \gt 0\). Разные допустимые пары не могут породить одну и ту же тройку. Поэтому подсчет решений исходного уравнения полностью совпадает с подсчетом этих ограниченных факторизаций.
Именно здесь возникает главное упрощение: квадратическая диофантова задача в трех переменных превращается в сито по произведениям \(uv\) с одним модульным условием и одной линейной границей.
Для \(n=3\) допустимых разложений почти нет. Пара \((u,v)=(3,1)\) удовлетворяет условиям \(uv=3\), \(u+v=4\) и \(v\lt 3u\). Тогда
$$d=\frac{3+1}{4}=1,\qquad (x,y,z)=(4,3,2).$$
Никакая другая пара множителей числа 3 не проходит те же проверки, поэтому \(n=3\) засчитывается.
Для \(n=15\) ситуация другая: допустимы уже две пары, \((u,v)=(3,5)\) и \((u,v)=(5,3)\). Они порождают две разные прогрессии
$$ (x,y,z)=(5,3,1),\qquad (x,y,z)=(7,5,3). $$
Следовательно, 15 не подходит для задачи 136, потому что число решений равно 2, а не 1.
Как только число представлений переписано через \((u,v)\), структура алгоритма становится очевидной. Для каждого положительного \(u\) допустимое \(v\) должно удовлетворять условию
$$v \le \left\lfloor\frac{N-1}{u}\right\rfloor$$
чтобы произведение \(n=uv\) оставалось ниже границы \(N=5\times 10^7\), и одновременно
$$v \le 3u-1,$$
поскольку \(v\lt 3u\) и \(v\) целое. Конгруэнция \(u+v\equiv 0\pmod 4\) означает, что допустимые значения \(v\) образуют один класс вычетов по модулю 4. Поэтому реализация для каждого \(u\) сразу перебирает только совместимые значения \(v\), отмечает произведение \(uv\) и увеличивает счетчик представлений.
Так как задача спрашивает лишь о случае “ровно одно представление”, хранить большие кратности не нужно. Как только какое-то \(n\) встречается второй раз, уже известно, что оно больше не имеет единственного представления, поэтому счетчик можно насыщать на уровне 2.
Реализации на C++, Python и Java сначала выделяют таблицу счетчиков для \(0,1,\dots,N-1\), где \(N=5\times 10^7\). Затем они проходят все положительные кандидаты на роль среднего члена и вычисляют максимальный сопутствующий множитель, который одновременно удовлетворяет ограничению на произведение и неравенству \(v\lt 3u\).
Для фиксированного среднего члена первый допустимый множитель является наименьшим положительным представителем класса \(v \equiv -u \pmod 4\). Прибавление 4 сохраняет целочисленность \(d=(u+v)/4\), поэтому каждая итерация цикла соответствует одной реальной арифметической прогрессии. Затем вычисляется \(n=uv\), а счетчик для этого \(n\) увеличивается, но не выше 2.
Когда число представлений уже превысило 1, точное значение больше не важно. Нужно различать только три состояния: “еще не встречалось”, “встретилось ровно один раз” и “встретилось хотя бы дважды”. Именно поэтому даже на полном диапазоне хватает таблицы с байтовыми ячейками.
После завершения ситовой части алгоритм делает один линейный проход по таблице и подсчитывает, сколько значений равны 1. Это и есть искомый ответ.
В одной из реализаций также есть маленький контрольный тест: ниже 100 существует 25 подходящих значений. Такой тест полезен, потому что он проверяет и сам вывод формулы, и модульную логику до запуска полного расчета до \(5\times 10^7\).
Пусть \(N\) обозначает верхнюю границу поиска. Для фиксированного \(u\) число допустимых сопутствующих множителей имеет порядок
$$O\!\left(\min\!\left(u,\frac{N}{u}\right)\right),$$
с точностью до постоянного множителя, связанного с шагом 4. При суммировании по всем \(u\) получаем
$$\sum_{u=1}^{N-1} O\!\left(\min\!\left(u,\frac{N}{u}\right)\right)=O(N\log N).$$
Следовательно, ситовая часть работает за \(O(N\log N)\), а финальный проход по таблице стоит \(O(N)\). По памяти требуется \(O(N)\) байт для насыщаемого массива счетчиков. При \(N=5\times 10^7\) это немало, но все еще практично для компилируемых реализаций, и именно поэтому алгоритм не хранит полные списки решений.
المطلوب هو حساب عدد القيم \(n \lt 5 \times 10^7\) التي تجعل المعادلة \(x^2 - y^2 - z^2 = n\) تملك حلاً موجبًا وحيدًا فقط، مع الشرط الإضافي أن تكون \(x\) و\(y\) و\(z\) ثلاثة حدود متتالية في متتالية حسابية. هذا الشرط لا يترك المسألة على صورة بحث حر في ثلاثة متغيرات، بل يحولها إلى مسألة عد منظّم لأزواج عوامل تحقق شروطًا دقيقة.
ولهذا لا تختبر تطبيقات C++ وPython وJava كل قيمة \(n\) على حدة. فهي تولّد كل متتالية صالحة مرة واحدة فقط، وتحولها إلى قيمة \(n\) المقابلة، ثم تحتفظ بالمعلومة الوحيدة التي تهمنا: هل لم تظهر هذه القيمة بعد، أم ظهرت مرة واحدة، أم ظهرت أكثر من مرة.
الخطوة الأساسية هي إعادة كتابة حدود المتتالية الحسابية بدلالة الحد الأوسط والفرق المشترك، ثم تحويل التعبير التربيعي الناتج إلى حاصل ضرب تحكمه موافقة معيارية وحدّ خطي بسيط.
إذا كانت \(x\) و\(y\) و\(z\) حدودًا في متتالية حسابية ذات فرق موجب \(d\)، فيمكن كتابتها على الصورة
$$x = y + d,\qquad z = y - d,\qquad d \ge 1,\qquad y \gt d.$$
وبالتعويض في المعادلة نحصل على
$$n = (y+d)^2 - y^2 - (y-d)^2 = 4yd - y^2 = y(4d-y).$$
إذن كل حل يحدده الحد الأوسط الموجب \(y\) ومعه العدد الموجب الآخر \(4d-y\).
لنعرّف
$$u = y,\qquad v = 4d-y.$$
فتصبح المعادلة ببساطة
$$n = uv.$$
وهذا التحويل قابل للعكس. فمن زوج مقبول \((u,v)\) نستعيد
$$d = \frac{u+v}{4},\qquad x = u+d = \frac{5u+v}{4},\qquad z = u-d = \frac{3u-v}{4}.$$
وعليه فإن الزوج \((u,v)\) يقابل حلاً صالحًا بالضبط عندما يتحقق
$$u \ge 1,\qquad v \ge 1,\qquad u+v \equiv 0 \pmod 4,$$
ومع شرط \(z \gt 0\) نحصل أيضًا على
$$\frac{u+v}{4} \lt u \qquad\Longleftrightarrow\qquad v \lt 3u.$$
إذن عدد تمثيلات \(n\) يساوي تمامًا عدد أزواج العوامل \((u,v)\) التي تحقق
$$uv=n,\qquad u+v \equiv 0 \pmod 4,\qquad 1 \le v \lt 3u.$$
إذا بدأنا بحل من حلول المتتالية الحسابية، فإن الصيغ السابقة تعطينا زوجًا مقبولاً واحدًا فقط \((u,v)\). وإذا بدأنا بزوج مقبول، فإن الصيغ العكسية تعيد أعدادًا صحيحة \(d\) و\(x\) و\(z\)، وتضمن المتباينات أن \(d \ge 1\) و\(z \gt 0\). لذلك لا يمكن لزوجين مختلفين من الأزواج المقبولة أن يولدا الثلاثية نفسها، ومن ثم فإن عد حلول المعادلة الأصلية يساوي تمامًا عد هذه التحليلات المقيدة.
وهنا يظهر التبسيط الحقيقي للمسألة: معادلة ديوفانتية تربيعية في ثلاثة متغيرات تتحول إلى غربال على الجداءات \(uv\) مع شرط معياري واحد وحدّ خطي واحد.
لننظر أولاً إلى \(n=3\). عدد التحليلات المقبولة هنا صغير جدًا. فالزوج \((u,v)=(3,1)\) يحقق \(uv=3\) و\(u+v=4\) و\(v\lt 3u\). ومنه نحصل على
$$d=\frac{3+1}{4}=1,\qquad (x,y,z)=(4,3,2).$$
ولا يوجد زوج آخر من عوامل 3 يمر بالشروط نفسها، ولذلك تُحتسب القيمة \(n=3\).
أما \(n=15\) فله زوجان مقبولان هما \((u,v)=(3,5)\) و\((u,v)=(5,3)\)، وهما يعطيان المتتاليتين
$$ (x,y,z)=(5,3,1),\qquad (x,y,z)=(7,5,3). $$
ولهذا لا تنتمي 15 إلى القيم المطلوبة في المسألة، لأن عدد حلولها يساوي 2 لا 1.
بعد إعادة كتابة عدد التمثيلات بدلالة \((u,v)\)، يصبح شكل الخوارزمية طبيعيًا جدًا. فلكل \(u\) موجب يجب على \(v\) المقبول أن يحقق
$$v \le \left\lfloor\frac{N-1}{u}\right\rfloor$$
حتى يبقى \(n=uv\) أصغر من الحد \(N=5\times 10^7\)، كما يجب أيضًا أن يحقق
$$v \le 3u-1,$$
لأن \(v\lt 3u\) و\(v\) عدد صحيح. أما الموافقة \(u+v\equiv 0\pmod 4\) فتعني أن قيم \(v\) الصالحة تقع كلها في فئة بواقي واحدة modulo 4. ولذلك تقفز الشيفرة مباشرة بين هذه القيم المتوافقة، وتشكّل الجداء \(uv\)، ثم تزيد عداد تمثيلات هذه القيمة.
وبما أن المطلوب هو معرفة ما إذا كان العدد يملك تمثيلاً واحدًا فقط، فلا جدوى من تخزين مضاعفات كبيرة. فما إن تُشاهد قيمة \(n\) للمرة الثانية حتى يصبح واضحًا أنها ليست من القيم وحيدة التمثيل، ولذلك يمكن تشبيع العداد عند 2.
تبدأ تطبيقات C++ وPython وJava بحجز جدول عدادات للقيم \(0,1,\dots,N-1\) حيث \(N=5\times 10^7\). ثم تمر على جميع القيم الموجبة المرشحة للحد الأوسط، وتحسب أكبر عامل مرافق مسموح به من جهة حد الجداء ومن جهة المتباينة \(v\lt 3u\).
وبالنسبة لكل حد أوسط ثابت، فإن أول عامل مرافق صالح هو أصغر عدد موجب في فئة البواقي \(v \equiv -u \pmod 4\). والانتقال بمقدار 4 في كل مرة يحافظ على كون \(d=(u+v)/4\) عددًا صحيحًا، لذا فإن كل دورة في الحلقة تقابل حلاً حقيقيًا من حلول المتتالية الحسابية. بعد ذلك تُحسب \(n=uv\) ويُزاد عدادها، لكن ليس لأكثر من 2.
بمجرد أن يصبح عدد التمثيلات أكبر من 1، لا تعود القيمة الدقيقة مهمة. المطلوب فقط هو التمييز بين ثلاث حالات: “لم تظهر بعد”، و“ظهرت مرة واحدة بالضبط”، و“ظهرت مرتين أو أكثر”. ولهذا يكفي جدول عدادات صغير مشبع حتى عند الحد الكامل.
بعد انتهاء مرحلة الغربلة، تجري الخوارزمية مرورًا خطيًا واحدًا على الجدول وتحصي عدد الخانات التي تساوي 1. هذا العدد هو الجواب المطلوب.
وتتضمن إحدى التطبيقات نقطة تحقق صغيرة أيضًا: تحت 100 يوجد 25 عددًا صالحًا. هذا الفحص مفيد لأنه يؤكد صحة الاشتقاق وصحة المنطق المعياري قبل تنفيذ الحساب الكامل حتى \(5\times 10^7\).
إذا رمزنا إلى الحد الأعلى بالرمز \(N\)، فإن عدد العوامل المرافقة المقبولة لقيمة ثابتة من \(u\) يكون من الرتبة
$$O\!\left(\min\!\left(u,\frac{N}{u}\right)\right),$$
مع تجاهل العامل الثابت الناتج من القفز بخطوة 4. وعند الجمع على جميع قيم \(u\) نحصل على
$$\sum_{u=1}^{N-1} O\!\left(\min\!\left(u,\frac{N}{u}\right)\right)=O(N\log N).$$
إذًا مرحلة الغربال تعمل في زمن \(O(N\log N)\)، بينما يكلف المسح الأخير للجدول \(O(N)\). أما الذاكرة فهي \(O(N)\) بايت لجدول العدادات المشبع. وعند \(N=5\times 10^7\) تبقى هذه الكلفة كبيرة لكنها عملية في التطبيقات المترجمة، وهذا هو السبب في أن الخوارزمية لا تخزن قوائم الحلول الكاملة.