A positive integer \(N\) is called stealthy if there exist positive integers \(a,b,c,d\) such that
$$ab=cd=N,\qquad a+b=c+d+1.$$
The task is to count how many distinct stealthy numbers satisfy \(N\le L\). The key fact used by the implementation is that stealthy numbers are exactly the products of two pronic numbers.
Define the pronic function
$$P(t)=t(t+1).$$
The whole problem becomes manageable once we show that every stealthy number can be written as \(P(x)P(y)\), and then enumerate those products without double-counting repeats.
Take two factor pairs of the same stealthy number, and let \((a,b)\) be the pair with the larger sum. After ordering the factors, the other pair lies strictly between them, so we may write
$$c=a+k,\qquad d=b-k-1,\qquad k\ge 1.$$
The condition \(ab=cd\) becomes
$$ab=(a+k)(b-k-1)=ab+k(b-a-k-1)-a.$$
Hence
$$a=k(b-a-k-1).$$
So \(k\) divides \(a\). Write
$$a=ky,\qquad y\ge 1.$$
Substituting back gives
$$b=(k+1)(y+1),\qquad c=k(y+1),\qquad d=(k+1)y.$$
Therefore
$$N=ab=k(k+1)y(y+1).$$
Renaming \(k\) as \(x\), we obtain the standard parametrization
$$\boxed{N=x(x+1)y(y+1).}$$
The formula above is not only necessary but also sufficient. For any positive integers \(x\) and \(y\), consider the two factor pairs
$$xy\cdot (x+1)(y+1),\qquad x(y+1)\cdot y(x+1).$$
Both products equal
$$x(x+1)y(y+1),$$
and their sums differ by exactly \(1\):
$$xy+(x+1)(y+1)=x(y+1)+y(x+1)+1.$$
So every number of the form \(x(x+1)y(y+1)\) is stealthy. The counting problem is therefore equivalent to counting distinct products
$$P(x)P(y),\qquad x,y\ge 1.$$
Because \(P(x)P(y)=P(y)P(x)\), we may impose
$$1\le x\le y$$
to remove the obvious symmetry.
For a fixed \(x\), admissible values of \(y\) satisfy
$$P(x)P(y)\le L,$$
or equivalently
$$P(y)\le \left\lfloor\frac{L}{P(x)}\right\rfloor.$$
If we define
$$T_x=\left\lfloor\frac{L}{P(x)}\right\rfloor,$$
then \(y\) must solve
$$y(y+1)\le T_x.$$
The positive root of \(y^2+y-T_x=0\) is
$$\frac{-1+\sqrt{1+4T_x}}{2},$$
so the largest valid integer is
$$y_{\max}(x)=\left\lfloor\frac{\sqrt{1+4T_x}-1}{2}\right\rfloor.$$
There is also a bound on \(x\) itself. Since \(y\ge x\), the smallest product in the \(x\)-row is \(P(x)^2\), so that row is active only when
$$P(x)^2\le L.$$
This determines the final range of rows that must be explored.
For each active \(x\), define the list
$$V_x=\{P(x)P(y): y=x,x+1,\dots,y_{\max}(x)\}.$$
Because \(P(y)\) is strictly increasing, every \(V_x\) is strictly increasing as well. The full set of candidates is the union of these sorted lists. That means the problem is no longer a brute-force scan over all pairs; it is a k-way merge problem over many already sorted sequences.
A min-heap stores the current first unseen value from each list \(V_x\). Repeatedly removing the smallest heap element produces the global candidate stream in increasing order. When a value from one row is consumed, the next product from the same row is inserted.
Duplicates can occur because the same stealthy number may have more than one parametrization. Since the merged stream is sorted, equal products appear consecutively, so it is enough to compare the current extracted value with the previously extracted one:
$$v_{\mathrm{current}}\ne v_{\mathrm{previous}}.$$
This is why the implementation can count distinct stealthy numbers without storing every product in a global set.
First compute the relevant pronic numbers:
$$P(1)=2,\quad P(2)=6,\quad P(3)=12,\quad P(4)=20.$$
Since \(P(4)^2=400>200\), only the rows \(x=1,2,3\) are active.
For \(x=1\), we need \(2P(y)\le 200\), so \(P(y)\le 100\) and \(y_{\max}(1)=9\). This row is
$$4,12,24,40,60,84,112,144,180.$$
For \(x=2\), we need \(6P(y)\le 200\), so \(P(y)\le 33\) and \(y_{\max}(2)=5\). This row is
$$36,72,120,180.$$
For \(x=3\), only \(y=3\) works, giving
$$144.$$
Merging and deduplicating yields
$$4,12,24,36,40,60,72,84,112,120,144,180,$$
so there are \(12\) stealthy numbers up to \(200\). The repeated values \(144\) and \(180\) show why deduplication is necessary.
The C++, Python, and Java implementations first build a table of pronic numbers up to the global limit \(P(y)\le L\). They then determine which starting rows are active by checking whether \(P(x)^2\le L\).
For every active row, the implementation computes the exact upper bound \(y_{\max}(x)\) using the inverse-pronic formula above and inserts the first value \(P(x)^2\) into a priority queue. Each queue entry stores enough information to generate the next product from the same row.
The main loop repeatedly removes the smallest current product. If it differs from the previous extracted value, the answer is increased by \(1\). Then the row that produced that product is advanced from \(y\) to \(y+1\), and the new product is inserted if it still lies within the valid range. The C++ version maintains its own binary heap, while the Python and Java versions rely on standard library priority queues, but the algorithmic idea is the same in all three languages.
Let
$$K=\#\{x:P(x)^2\le L\},\qquad M=\sum_{x=1}^{K}\bigl(y_{\max}(x)-x+1\bigr).$$
Building the pronic table up to the global bound costs \(O(\sqrt{L})\) time and \(O(\sqrt{L})\) memory, because the largest needed index satisfies \(P(y)\le L\). The priority-queue phase performs one extract operation and at most one insert operation per generated pair, so it costs \(O(M\log K)\) time and \(O(K)\) additional memory for the heap.
In particular, the implementation never stores all \(M\) products at once. It keeps only one current candidate per active row, which is the essential reason the method remains practical for very large limits.
Eine positive ganze Zahl \(N\) heißt stealthy, wenn es positive ganze Zahlen \(a,b,c,d\) gibt mit
$$ab=cd=N,\qquad a+b=c+d+1.$$
Gesucht ist die Anzahl verschiedener stealthy Zahlen mit \(N\le L\). Die zentrale Beobachtung der Implementierung lautet: Genau die stealthy Zahlen sind Produkte zweier pronischer Zahlen.
Definiere die pronische Funktion
$$P(t)=t(t+1).$$
Dann wird das Problem beherrschbar, sobald gezeigt ist, dass jede stealthy Zahl die Form \(P(x)P(y)\) hat. Danach muss man diese Produkte nur noch effizient und ohne Doppelzählung erzeugen.
Betrachte zwei Faktorpaare derselben stealthy Zahl, wobei \((a,b)\) das Paar mit der größeren Summe sei. Nach Sortierung der Faktoren liegt das andere Paar dazwischen, also können wir schreiben
$$c=a+k,\qquad d=b-k-1,\qquad k\ge 1.$$
Aus \(ab=cd\) folgt
$$ab=(a+k)(b-k-1)=ab+k(b-a-k-1)-a.$$
Daher gilt
$$a=k(b-a-k-1).$$
Also teilt \(k\) die Zahl \(a\). Schreibe deshalb
$$a=ky,\qquad y\ge 1.$$
Einsetzen liefert
$$b=(k+1)(y+1),\qquad c=k(y+1),\qquad d=(k+1)y.$$
Damit erhält man
$$N=ab=k(k+1)y(y+1).$$
Mit der Umbenennung \(k=x\) entsteht die Standarddarstellung
$$\boxed{N=x(x+1)y(y+1).}$$
Diese Formel ist nicht nur notwendig, sondern auch hinreichend. Für beliebige positive \(x\) und \(y\) betrachte die beiden Faktorpaare
$$xy\cdot (x+1)(y+1),\qquad x(y+1)\cdot y(x+1).$$
Beide Produkte sind gleich
$$x(x+1)y(y+1),$$
und ihre Summen unterscheiden sich genau um \(1\):
$$xy+(x+1)(y+1)=x(y+1)+y(x+1)+1.$$
Also ist jede Zahl der Form \(x(x+1)y(y+1)\) stealthy. Das Zählproblem reduziert sich damit auf verschiedene Produkte
$$P(x)P(y),\qquad x,y\ge 1.$$
Wegen \(P(x)P(y)=P(y)P(x)\) genügt die Nebenbedingung
$$1\le x\le y$$
um die offensichtliche Symmetrie zu entfernen.
Für festes \(x\) müssen zulässige \(y\) die Bedingung
$$P(x)P(y)\le L$$
erfüllen, also
$$P(y)\le \left\lfloor\frac{L}{P(x)}\right\rfloor.$$
Mit
$$T_x=\left\lfloor\frac{L}{P(x)}\right\rfloor$$
muss \(y\) also
$$y(y+1)\le T_x$$
erfüllen. Die positive Nullstelle von \(y^2+y-T_x=0\) ist
$$\frac{-1+\sqrt{1+4T_x}}{2},$$
also ist der größte zulässige ganzzahlige Wert
$$y_{\max}(x)=\left\lfloor\frac{\sqrt{1+4T_x}-1}{2}\right\rfloor.$$
Auch \(x\) selbst ist beschränkt. Da \(y\ge x\), ist das kleinste Produkt in Zeile \(x\) gleich \(P(x)^2\). Diese Zeile ist also nur aktiv, wenn
$$P(x)^2\le L.$$
Für jedes aktive \(x\) definieren wir die Liste
$$V_x=\{P(x)P(y): y=x,x+1,\dots,y_{\max}(x)\}.$$
Da \(P(y)\) streng wächst, ist auch jede Liste \(V_x\) streng wachsend. Die gesamte Kandidatenmenge ist also eine Vereinigung bereits sortierter Listen. Das Problem ist damit kein roher Doppelloop mehr, sondern ein k-faches Zusammenführen sortierter Folgen.
Ein Min-Heap speichert aus jeder Liste \(V_x\) den aktuell kleinsten noch nicht verbrauchten Wert. Das wiederholte Entfernen des kleinsten Heap-Elements erzeugt den globalen Kandidatenstrom in aufsteigender Reihenfolge. Wird ein Wert aus einer Zeile verbraucht, wird der nächste Wert derselben Zeile nachgeschoben.
Doppelte Werte sind möglich, weil dieselbe stealthy Zahl mehrere Parametrisierungen besitzen kann. Da der zusammengeführte Strom sortiert ist, erscheinen gleiche Produkte hintereinander. Deshalb genügt der Vergleich mit dem zuletzt ausgegebenen Wert:
$$v_{\mathrm{current}}\ne v_{\mathrm{previous}}.$$
Genau dadurch braucht die Implementierung keine globale Mengenstruktur für alle Produkte.
Zuerst die relevanten pronischen Zahlen:
$$P(1)=2,\quad P(2)=6,\quad P(3)=12,\quad P(4)=20.$$
Da \(P(4)^2=400>200\), sind nur die Zeilen \(x=1,2,3\) aktiv.
Für \(x=1\) gilt \(2P(y)\le 200\), also \(P(y)\le 100\) und damit \(y_{\max}(1)=9\). Die Zeile lautet
$$4,12,24,40,60,84,112,144,180.$$
Für \(x=2\) gilt \(6P(y)\le 200\), also \(P(y)\le 33\) und \(y_{\max}(2)=5\). Die Zeile lautet
$$36,72,120,180.$$
Für \(x=3\) funktioniert nur \(y=3\), also entsteht
$$144.$$
Nach dem Zusammenführen und Deduplizieren erhält man
$$4,12,24,36,40,60,72,84,112,120,144,180,$$
also genau \(12\) stealthy Zahlen bis \(200\). Die doppelten Werte \(144\) und \(180\) zeigen, warum Deduplizierung nötig ist.
Die Implementierungen in C++, Python und Java erzeugen zunächst eine Tabelle aller pronischen Zahlen bis zur globalen Schranke \(P(y)\le L\). Danach bestimmen sie alle Startzeilen, für die \(P(x)^2\le L\) gilt.
Für jede aktive Zeile wird mit der inversen pronischen Formel der exakte obere Index \(y_{\max}(x)\) berechnet und der erste Wert \(P(x)^2\) in eine Prioritätswarteschlange gelegt. Jeder Eintrag enthält genau die Informationen, die nötig sind, um später den nächsten Wert derselben Zeile zu erzeugen.
In der Hauptschleife wird stets das kleinste aktuelle Produkt entfernt. Unterscheidet es sich vom zuvor entfernten Wert, wird der Zähler erhöht. Anschließend wird die zugehörige Zeile von \(y\) auf \(y+1\) weitergeschoben und ihr neuer Produktwert wieder eingefügt, falls er noch im zulässigen Bereich liegt. Die C++-Version verwaltet ihren Binär-Heap selbst, Python und Java benutzen Standardbibliotheken, mathematisch ist der Ablauf aber identisch.
Sei
$$K=\#\{x:P(x)^2\le L\},\qquad M=\sum_{x=1}^{K}\bigl(y_{\max}(x)-x+1\bigr).$$
Der Aufbau der pronischen Tabelle bis zur globalen Schranke kostet \(O(\sqrt{L})\) Zeit und \(O(\sqrt{L})\) Speicher, weil der größte benötigte Index durch \(P(y)\le L\) bestimmt ist. Die Prioritätswarteschlange führt pro erzeugtem Paar genau eine Entnahme und höchstens eine Einfügung aus, also insgesamt \(O(M\log K)\) Zeit bei \(O(K)\) zusätzlichem Heap-Speicher.
Entscheidend ist, dass nie alle \(M\) Produkte gleichzeitig gespeichert werden. Die Implementierung hält immer nur einen aktuellen Kandidaten pro aktiver Zeile vor, und genau das macht die Methode für sehr große Grenzen praktikabel.
Pozitif bir \(N\) tamsayısı, pozitif \(a,b,c,d\) sayıları için
$$ab=cd=N,\qquad a+b=c+d+1$$
koşulları sağlanıyorsa stealthy sayıdır. Amaç, \(N\le L\) koşulunu sağlayan farklı stealthy sayıların kaç tane olduğunu bulmaktır. Uygulamanın kullandığı temel gözlem şudur: Stealthy sayılar tam olarak iki pronik sayının çarpımıdır.
Pronik fonksiyonu
$$P(t)=t(t+1)$$
olarak tanımlayalım. Problem, her stealthy sayının \(P(x)P(y)\) biçiminde yazıldığını gösterince ve bu çarpımları tekrarsız sayınca çözülebilir hale gelir.
Aynı stealthy sayıya ait iki çarpan çiftini düşünelim ve toplamı daha büyük olan çifti \((a,b)\) ile gösterelim. Çarpanları sıraladıktan sonra diğer çift arada kalır; bu yüzden
$$c=a+k,\qquad d=b-k-1,\qquad k\ge 1$$
yazabiliriz. \(ab=cd\) eşitliği
$$ab=(a+k)(b-k-1)=ab+k(b-a-k-1)-a$$
olur. Buradan
$$a=k(b-a-k-1)$$
elde edilir. Demek ki \(k\), \(a\)'yı böler. O halde
$$a=ky,\qquad y\ge 1$$
yazalım. Yerine koyunca
$$b=(k+1)(y+1),\qquad c=k(y+1),\qquad d=(k+1)y$$
bulunur. Dolayısıyla
$$N=ab=k(k+1)y(y+1).$$
\(k\) yerine \(x\) yazarsak standart parametreleme elde edilir:
$$\boxed{N=x(x+1)y(y+1).}$$
Bu formül sadece gerekli değil, aynı zamanda yeterlidir. Her pozitif \(x\) ve \(y\) için şu iki çarpan çiftine bakın:
$$xy\cdot (x+1)(y+1),\qquad x(y+1)\cdot y(x+1).$$
İki çarpım da
$$x(x+1)y(y+1)$$
değerine eşittir ve toplamları tam \(1\) fark eder:
$$xy+(x+1)(y+1)=x(y+1)+y(x+1)+1.$$
Yani \(x(x+1)y(y+1)\) biçimindeki her sayı stealthy'dir. Böylece problem,
$$P(x)P(y),\qquad x,y\ge 1$$
şeklindeki farklı çarpımları sayma problemine dönüşür. Ayrıca
$$P(x)P(y)=P(y)P(x)$$
olduğu için aynı değeri iki kez saymamak adına
$$1\le x\le y$$
koşulunu koyabiliriz.
Sabit bir \(x\) için uygun \(y\) değerleri
$$P(x)P(y)\le L$$
koşulunu sağlamalıdır; yani
$$P(y)\le \left\lfloor\frac{L}{P(x)}\right\rfloor.$$
Şunu tanımlayalım:
$$T_x=\left\lfloor\frac{L}{P(x)}\right\rfloor.$$
O zaman \(y\),
$$y(y+1)\le T_x$$
eşitsizliğini sağlamalıdır. \(y^2+y-T_x=0\) denkleminin pozitif kökü
$$\frac{-1+\sqrt{1+4T_x}}{2}$$
olduğundan, en büyük geçerli tam sayı
$$y_{\max}(x)=\left\lfloor\frac{\sqrt{1+4T_x}-1}{2}\right\rfloor$$
olur. \(x\) için de bir sınır vardır. Çünkü \(y\ge x\) olduğundan, \(x\) satırındaki en küçük çarpım \(P(x)^2\)'dir. Bu satır ancak
$$P(x)^2\le L$$
ise aktiftir.
Her aktif \(x\) için
$$V_x=\{P(x)P(y): y=x,x+1,\dots,y_{\max}(x)\}$$
listesini tanımlayalım. \(P(y)\) sıkı artan olduğu için her \(V_x\) listesi de sıkı artandır. Böylece tüm adaylar, zaten sıralı olan birçok listenin birleşimi haline gelir. Problem artık kaba kuvvetle tüm çiftleri taramak değil, sıralı listeleri birleştirme problemidir.
Bir min-heap, her \(V_x\) listesindeki henüz görülmemiş en küçük değeri tutar. Heap'ten en küçük elemanı tekrar tekrar çıkarmak, küresel aday akışını artan sırada üretir. Bir satırdan değer tüketildiğinde, aynı satırın bir sonraki değeri heap'e eklenir.
Aynı stealthy sayı birden fazla parametre çiftiyle üretilebildiği için tekrarlar oluşabilir. Ancak birleşik akış sıralı olduğundan eşit değerler arka arkaya gelir. Bu yüzden yalnızca bir önceki çıkarılan değerle karşılaştırmak yeterlidir:
$$v_{\mathrm{current}}\ne v_{\mathrm{previous}}.$$
Bu sayede uygulama tüm çarpımları küresel bir kümede tutmadan farklı değerleri sayabilir.
Önce gerekli pronik sayıları yazalım:
$$P(1)=2,\quad P(2)=6,\quad P(3)=12,\quad P(4)=20.$$
\(P(4)^2=400>200\) olduğundan yalnızca \(x=1,2,3\) satırları aktiftir.
\(x=1\) için \(2P(y)\le 200\), yani \(P(y)\le 100\) ve \(y_{\max}(1)=9\). Bu satır
$$4,12,24,40,60,84,112,144,180$$
değerlerini üretir. \(x=2\) için \(6P(y)\le 200\), yani \(P(y)\le 33\) ve \(y_{\max}(2)=5\). Bu satır
$$36,72,120,180$$
olur. \(x=3\) için yalnızca \(y=3\) mümkündür ve
$$144$$
elde edilir. Sıralayıp tekilleştirince
$$4,12,24,36,40,60,72,84,112,120,144,180$$
kalır; yani \(200\)'e kadar toplam \(12\) stealthy sayı vardır. \(144\) ve \(180\) değerleri tekrar geldiği için tekilleştirmenin gerekli olduğu açıkça görülür.
C++, Python ve Java uygulamaları önce \(P(y)\le L\) sınırına kadar tüm pronik sayıları önceden hesaplar. Ardından \(P(x)^2\le L\) koşulunu sağlayan başlangıç satırlarını belirler.
Her aktif satır için yukarıdaki ters pronik formülüyle tam \(y_{\max}(x)\) sınırı bulunur ve ilk değer \(P(x)^2\) bir öncelik kuyruğuna yerleştirilir. Kuyruktaki her kayıt, aynı satırın sıradaki çarpımını üretecek kadar bilgi taşır.
Ana döngü her seferinde en küçük güncel çarpımı çıkarır. Bu değer bir önceki çıkarılan değerden farklıysa cevap \(1\) artırılır. Sonra o değeri üreten satır \(y\) konumundan \(y+1\) konumuna ilerletilir ve yeni çarpım hâlâ geçerliyse tekrar kuyruğa eklenir. C++ sürümü heap yapısını elle yönetirken Python ve Java standart kütüphane kuyruklarını kullanır; fakat üç dilde de algoritma aynıdır.
Şöyle tanımlayalım:
$$K=\#\{x:P(x)^2\le L\},\qquad M=\sum_{x=1}^{K}\bigl(y_{\max}(x)-x+1\bigr).$$
Küresel sınıra kadar pronik tabloyu oluşturmak \(O(\sqrt{L})\) zaman ve \(O(\sqrt{L})\) bellek ister; çünkü gereken en büyük indis \(P(y)\le L\) koşuluyla belirlenir. Öncelik kuyruğu aşamasında ise her üretilen çift için bir çıkarma ve en fazla bir ekleme yapılır; bu yüzden toplam süre \(O(M\log K)\), ek heap belleği ise \(O(K)\) olur.
Kritik nokta, uygulamanın bütün \(M\) çarpımı aynı anda saklamamasıdır. Her aktif satır için yalnızca tek bir güncel aday tutulur; yöntemi büyük limitlerde uygulanabilir yapan esas fikir budur.
Un entero positivo \(N\) es stealthy si existen enteros positivos \(a,b,c,d\) tales que
$$ab=cd=N,\qquad a+b=c+d+1.$$
Hay que contar cuántos valores distintos cumplen \(N\le L\). La observación clave usada por la implementación es que los números stealthy son exactamente los productos de dos números prónicos.
Definimos la función prónica
$$P(t)=t(t+1).$$
El problema se vuelve manejable cuando se demuestra que todo número stealthy puede escribirse como \(P(x)P(y)\), y luego se enumeran esos productos sin contar dos veces el mismo valor.
Tomemos dos pares de factores del mismo número stealthy y llamemos \((a,b)\) al par con suma mayor. Tras ordenar los factores, el otro par queda entre ambos, así que podemos escribir
$$c=a+k,\qquad d=b-k-1,\qquad k\ge 1.$$
La igualdad \(ab=cd\) da
$$ab=(a+k)(b-k-1)=ab+k(b-a-k-1)-a.$$
Por tanto,
$$a=k(b-a-k-1).$$
Luego \(k\) divide a \(a\). Escribimos entonces
$$a=ky,\qquad y\ge 1.$$
Sustituyendo se obtiene
$$b=(k+1)(y+1),\qquad c=k(y+1),\qquad d=(k+1)y.$$
Así,
$$N=ab=k(k+1)y(y+1).$$
Renombrando \(k\) como \(x\), llegamos a la parametrización estándar
$$\boxed{N=x(x+1)y(y+1).}$$
La fórmula anterior no solo es necesaria: también es suficiente. Para cualesquiera enteros positivos \(x\) e \(y\), consideremos los pares de factores
$$xy\cdot (x+1)(y+1),\qquad x(y+1)\cdot y(x+1).$$
Ambos productos son iguales a
$$x(x+1)y(y+1),$$
y sus sumas difieren exactamente en \(1\):
$$xy+(x+1)(y+1)=x(y+1)+y(x+1)+1.$$
Por tanto, todo número de la forma \(x(x+1)y(y+1)\) es stealthy. El problema de conteo se reduce a contar productos distintos
$$P(x)P(y),\qquad x,y\ge 1.$$
Además, como \(P(x)P(y)=P(y)P(x)\), podemos imponer
$$1\le x\le y$$
para eliminar la simetría evidente.
Para un \(x\) fijo, los valores admisibles de \(y\) deben satisfacer
$$P(x)P(y)\le L,$$
es decir,
$$P(y)\le \left\lfloor\frac{L}{P(x)}\right\rfloor.$$
Si definimos
$$T_x=\left\lfloor\frac{L}{P(x)}\right\rfloor,$$
entonces \(y\) debe cumplir
$$y(y+1)\le T_x.$$
La raíz positiva de \(y^2+y-T_x=0\) es
$$\frac{-1+\sqrt{1+4T_x}}{2},$$
así que el mayor entero válido es
$$y_{\max}(x)=\left\lfloor\frac{\sqrt{1+4T_x}-1}{2}\right\rfloor.$$
También hay una cota para \(x\). Como \(y\ge x\), el producto mínimo en la fila \(x\) es \(P(x)^2\), de modo que esa fila solo existe si
$$P(x)^2\le L.$$
Para cada \(x\) activo definimos la lista
$$V_x=\{P(x)P(y): y=x,x+1,\dots,y_{\max}(x)\}.$$
Como \(P(y)\) crece estrictamente, cada \(V_x\) también es estrictamente creciente. El conjunto completo de candidatos es entonces una unión de listas ya ordenadas. El problema deja de ser un doble recorrido bruto y pasa a ser una fusión k-way de secuencias ordenadas.
Un min-heap guarda el menor valor aún no procesado de cada lista \(V_x\). Extraer repetidamente el mínimo produce el flujo global de candidatos en orden creciente. Cuando se consume un valor de una fila, se inserta el siguiente valor de esa misma fila.
Pueden aparecer duplicados porque un mismo número stealthy puede tener más de una parametrización. Como el flujo fusionado está ordenado, los valores iguales aparecen consecutivamente. Por eso basta comparar el valor actual con el anterior:
$$v_{\mathrm{current}}\ne v_{\mathrm{previous}}.$$
Esa es la razón por la que la implementación puede contar valores distintos sin almacenar todos los productos en un conjunto global.
Primero calculamos los números prónicos relevantes:
$$P(1)=2,\quad P(2)=6,\quad P(3)=12,\quad P(4)=20.$$
Como \(P(4)^2=400>200\), solo están activas las filas \(x=1,2,3\).
Para \(x=1\), la condición es \(2P(y)\le 200\), luego \(P(y)\le 100\) y \(y_{\max}(1)=9\). La fila es
$$4,12,24,40,60,84,112,144,180.$$
Para \(x=2\), la condición es \(6P(y)\le 200\), así que \(P(y)\le 33\) y \(y_{\max}(2)=5\). La fila es
$$36,72,120,180.$$
Para \(x=3\), solo sirve \(y=3\), y produce
$$144.$$
Al fusionar y deduplicar obtenemos
$$4,12,24,36,40,60,72,84,112,120,144,180,$$
de modo que hay \(12\) números stealthy hasta \(200\). Los valores repetidos \(144\) y \(180\) muestran por qué la deduplicación es indispensable.
Las implementaciones en C++, Python y Java construyen primero una tabla de números prónicos hasta el límite global \(P(y)\le L\). Después determinan qué filas iniciales están activas comprobando si \(P(x)^2\le L\).
Para cada fila activa, la implementación calcula el límite exacto \(y_{\max}(x)\) con la fórmula inversa prónica e inserta el primer valor \(P(x)^2\) en una cola de prioridad. Cada entrada conserva la información necesaria para generar el siguiente producto de esa misma fila.
El bucle principal extrae siempre el menor producto actual. Si difiere del valor extraído inmediatamente antes, se incrementa la respuesta. Luego la fila correspondiente avanza de \(y\) a \(y+1\), y se vuelve a insertar su nuevo producto si todavía está dentro del rango válido. La versión en C++ mantiene el heap de forma explícita, mientras que Python y Java usan estructuras estándar, pero el algoritmo es el mismo en los tres casos.
Sea
$$K=\#\{x:P(x)^2\le L\},\qquad M=\sum_{x=1}^{K}\bigl(y_{\max}(x)-x+1\bigr).$$
Construir la tabla prónica hasta el límite global cuesta \(O(\sqrt{L})\) tiempo y \(O(\sqrt{L})\) memoria, porque el mayor índice necesario viene determinado por \(P(y)\le L\). La fase de cola de prioridad realiza una extracción y como máximo una inserción por cada par generado, así que cuesta \(O(M\log K)\) tiempo y \(O(K)\) memoria adicional para el heap.
El punto importante es que la implementación nunca almacena simultáneamente los \(M\) productos. Solo mantiene un candidato actual por fila activa, y esa es la razón esencial por la que el método sigue siendo práctico para límites muy grandes.
如果一个正整数 \(N\) 存在正整数 \(a,b,c,d\)，满足
$$ab=cd=N,\qquad a+b=c+d+1,$$
那么 \(N\) 就称为 stealthy number。题目的目标是统计所有满足 \(N\le L\) 的不同 stealthy 数的个数。实现所依赖的核心事实是：stealthy 数恰好等价于两个 pronic 数的乘积。
定义 pronic 函数
$$P(t)=t(t+1).$$
一旦证明每个 stealthy 数都可以写成 \(P(x)P(y)\) 的形式，并且只需把这些乘积去重计数，问题就会从原始定义转化为一个可直接枚举的结构化问题。
设同一个 stealthy 数有两组因子对，其中 \((a,b)\) 是和较大的那一组。将各组内部按从小到大排列后，另一组因子会夹在它们之间，因此可以写成
$$c=a+k,\qquad d=b-k-1,\qquad k\ge 1.$$
再利用 \(ab=cd\)，得到
$$ab=(a+k)(b-k-1)=ab+k(b-a-k-1)-a.$$
于是
$$a=k(b-a-k-1).$$
这说明 \(k\) 整除 \(a\)。令
$$a=ky,\qquad y\ge 1,$$
代回后可得
$$b=(k+1)(y+1),\qquad c=k(y+1),\qquad d=(k+1)y.$$
因此
$$N=ab=k(k+1)y(y+1).$$
把 \(k\) 改记为 \(x\)，便得到标准参数化
$$\boxed{N=x(x+1)y(y+1).}$$
上面的形式不仅是必要条件，也是充分条件。对任意正整数 \(x,y\)，考虑两组因子
$$xy\cdot (x+1)(y+1),\qquad x(y+1)\cdot y(x+1).$$
它们的乘积都等于
$$x(x+1)y(y+1),$$
而两组因子的和恰好相差 \(1\)：
$$xy+(x+1)(y+1)=x(y+1)+y(x+1)+1.$$
所以，任何形如 \(x(x+1)y(y+1)\) 的数一定是 stealthy 数。于是原问题等价于统计不同的
$$P(x)P(y),\qquad x,y\ge 1.$$
又因为
$$P(x)P(y)=P(y)P(x),$$
所以可以加入
$$1\le x\le y$$
这个限制来去掉显然的对称重复。
固定某个 \(x\) 之后，合法的 \(y\) 必须满足
$$P(x)P(y)\le L,$$
也就是
$$P(y)\le \left\lfloor\frac{L}{P(x)}\right\rfloor.$$
记
$$T_x=\left\lfloor\frac{L}{P(x)}\right\rfloor,$$
则 \(y\) 需要满足
$$y(y+1)\le T_x.$$
二次方程 \(y^2+y-T_x=0\) 的正根是
$$\frac{-1+\sqrt{1+4T_x}}{2},$$
因此最大的合法整数是
$$y_{\max}(x)=\left\lfloor\frac{\sqrt{1+4T_x}-1}{2}\right\rfloor.$$
\(x\) 本身也有上界。因为 \(y\ge x\)，所以第 \(x\) 行中最小的乘积是 \(P(x)^2\)。只有当
$$P(x)^2\le L$$
时，这一行才可能产生候选值。
对每个有效的 \(x\)，定义序列
$$V_x=\{P(x)P(y): y=x,x+1,\dots,y_{\max}(x)\}.$$
由于 \(P(y)\) 随 \(y\) 严格递增，所以每条 \(V_x\) 也是严格递增的。于是所有候选值并不是无序散落的双重循环结果，而是若干条已排序序列的并集。这样问题自然转化为一个 k 路归并问题。
用一个最小堆保存每条序列当前最小的未处理元素。每次从堆中取出最小值，就得到了全局有序候选流中的下一个元素；随后把同一条序列中的下一个乘积重新压回堆中。
之所以需要去重，是因为同一个 stealthy 数可能来自多个不同的参数对。由于归并后的流已经按大小排序，相同的值一定连续出现，因此只要与前一个取出的值比较即可：
$$v_{\mathrm{current}}\ne v_{\mathrm{previous}}.$$
这就是实现能够在不使用全局集合存储全部乘积的情况下，仍然正确统计不同值的原因。
先列出相关的 pronic 数：
$$P(1)=2,\quad P(2)=6,\quad P(3)=12,\quad P(4)=20.$$
因为 \(P(4)^2=400>200\)，所以只有 \(x=1,2,3\) 这三行是有效的。
当 \(x=1\) 时，需要 \(2P(y)\le 200\)，也就是 \(P(y)\le 100\)，故 \(y_{\max}(1)=9\)。这一行给出
$$4,12,24,40,60,84,112,144,180.$$
当 \(x=2\) 时，需要 \(6P(y)\le 200\)，即 \(P(y)\le 33\)，因此 \(y_{\max}(2)=5\)。这一行给出
$$36,72,120,180.$$
当 \(x=3\) 时，只有 \(y=3\) 可行，因此产生
$$144.$$
把这些序列归并并去重后，得到
$$4,12,24,36,40,60,72,84,112,120,144,180,$$
所以不超过 \(200\) 的 stealthy 数共有 \(12\) 个。其中 \(144\) 和 \(180\) 都重复出现过，这正说明在线去重是必要的。
C++、Python 和 Java 三个实现都会先预计算所有满足 \(P(y)\le L\) 的 pronic 数。随后通过检查 \(P(x)^2\le L\) 来确定哪些起始行真正有效。
对每个有效的 \(x\)，实现会用上面的反函数公式精确求出 \(y_{\max}(x)\)，然后把这一行的第一个值 \(P(x)^2\) 放入优先队列。每个队列元素都携带继续向该行下一项推进所需的信息。
主循环反复取出当前最小乘积。如果它与上一个取出的值不同，答案就加 \(1\)。随后，把产生该乘积的那一行从 \(y\) 推进到 \(y+1\)，若新乘积仍在合法范围内，就再次放回队列。C++ 版本手工维护二叉堆，Python 和 Java 使用标准库优先队列，但三者的算法思想完全一致。
记
$$K=\#\{x:P(x)^2\le L\},\qquad M=\sum_{x=1}^{K}\bigl(y_{\max}(x)-x+1\bigr).$$
预计算 pronic 表到全局上界需要 \(O(\sqrt{L})\) 时间和 \(O(\sqrt{L})\) 空间，因为所需最大下标由 \(P(y)\le L\) 决定。优先队列阶段对每个生成的参数对执行一次弹出、至多一次压入，因此总时间为 \(O(M\log K)\)，额外堆空间为 \(O(K)\)。
更重要的是，实现从不一次性保存全部 \(M\) 个乘积。它始终只为每个有效行保留一个当前候选值，而这正是算法能够处理极大上界的关键。
Положительное целое число \(N\) называется stealthy, если существуют положительные целые \(a,b,c,d\), такие что
$$ab=cd=N,\qquad a+b=c+d+1.$$
Нужно посчитать количество различных stealthy-чисел, не превосходящих \(L\). Ключевое наблюдение, на котором основана реализация, состоит в том, что такие числа в точности являются произведениями двух pronic-чисел.
Введем pronic-функцию
$$P(t)=t(t+1).$$
После этого задача сводится к двум шагам: доказать представление любого stealthy-числа в виде \(P(x)P(y)\) и затем перечислить такие произведения без повторного подсчета одинаковых значений.
Рассмотрим две пары делителей одного и того же stealthy-числа и обозначим через \((a,b)\) пару с большей суммой. После упорядочивания множителей вторая пара лежит между ними, поэтому можно записать
$$c=a+k,\qquad d=b-k-1,\qquad k\ge 1.$$
Из равенства \(ab=cd\) получаем
$$ab=(a+k)(b-k-1)=ab+k(b-a-k-1)-a.$$
Следовательно,
$$a=k(b-a-k-1).$$
Значит, \(k\) делит \(a\). Запишем
$$a=ky,\qquad y\ge 1.$$
Тогда
$$b=(k+1)(y+1),\qquad c=k(y+1),\qquad d=(k+1)y.$$
Отсюда
$$N=ab=k(k+1)y(y+1).$$
Переобозначив \(k\) как \(x\), получаем стандартную формулу
$$\boxed{N=x(x+1)y(y+1).}$$
Полученная формула не только необходима, но и достаточна. Для любых положительных \(x\) и \(y\) рассмотрим пары множителей
$$xy\cdot (x+1)(y+1),\qquad x(y+1)\cdot y(x+1).$$
Оба произведения равны
$$x(x+1)y(y+1),$$
а их суммы отличаются ровно на \(1\):
$$xy+(x+1)(y+1)=x(y+1)+y(x+1)+1.$$
Следовательно, каждое число вида \(x(x+1)y(y+1)\) действительно stealthy. Значит, задача подсчета сводится к подсчету различных произведений
$$P(x)P(y),\qquad x,y\ge 1.$$
Так как
$$P(x)P(y)=P(y)P(x),$$
можно наложить условие
$$1\le x\le y$$
и тем самым убрать очевидную симметрию.
При фиксированном \(x\) допустимые значения \(y\) должны удовлетворять
$$P(x)P(y)\le L,$$
то есть
$$P(y)\le \left\lfloor\frac{L}{P(x)}\right\rfloor.$$
Обозначим
$$T_x=\left\lfloor\frac{L}{P(x)}\right\rfloor.$$
Тогда требуется, чтобы
$$y(y+1)\le T_x.$$
Положительный корень уравнения \(y^2+y-T_x=0\) равен
$$\frac{-1+\sqrt{1+4T_x}}{2},$$
поэтому максимальное целое допустимое значение равно
$$y_{\max}(x)=\left\lfloor\frac{\sqrt{1+4T_x}-1}{2}\right\rfloor.$$
Есть и ограничение на сам \(x\). Поскольку \(y\ge x\), минимальное произведение в строке \(x\) равно \(P(x)^2\). Значит, строка активна только если
$$P(x)^2\le L.$$
Для каждого активного \(x\) определим список
$$V_x=\{P(x)P(y): y=x,x+1,\dots,y_{\max}(x)\}.$$
Так как \(P(y)\) строго возрастает, каждый список \(V_x\) тоже строго возрастает. Следовательно, все кандидаты образуют объединение уже отсортированных последовательностей. Это превращает задачу из грубого перебора всех пар в задачу k-путевого слияния.
Минимальная куча хранит текущий наименьший необработанный элемент из каждого списка \(V_x\). Повторное извлечение минимального элемента порождает глобальный поток кандидатов в возрастающем порядке. Когда значение из некоторой строки извлечено, в кучу добавляется следующий элемент той же строки.
Повторы возможны, потому что одно и то же stealthy-число может иметь несколько параметризаций. Но поскольку объединенный поток отсортирован, одинаковые значения идут подряд. Поэтому достаточно сравнивать текущее извлеченное значение с предыдущим:
$$v_{\mathrm{current}}\ne v_{\mathrm{previous}}.$$
Именно поэтому реализация может обходиться без глобального множества всех произведений.
Сначала выпишем нужные pronic-числа:
$$P(1)=2,\quad P(2)=6,\quad P(3)=12,\quad P(4)=20.$$
Так как \(P(4)^2=400>200\), активными остаются только строки \(x=1,2,3\).
Для \(x=1\) требуется \(2P(y)\le 200\), то есть \(P(y)\le 100\), откуда \(y_{\max}(1)=9\). Эта строка дает
$$4,12,24,40,60,84,112,144,180.$$
Для \(x=2\) требуется \(6P(y)\le 200\), то есть \(P(y)\le 33\), и потому \(y_{\max}(2)=5\). Здесь получаем
$$36,72,120,180.$$
Для \(x=3\) подходит только \(y=3\), что дает
$$144.$$
После слияния и удаления повторов остается
$$4,12,24,36,40,60,72,84,112,120,144,180,$$
то есть до \(200\) существует \(12\) stealthy-чисел. Повторяющиеся значения \(144\) и \(180\) хорошо показывают, почему этап дедупликации обязателен.
Реализации на C++, Python и Java сначала строят таблицу pronic-чисел до глобальной границы \(P(y)\le L\). Затем они определяют, какие стартовые строки активны, проверяя условие \(P(x)^2\le L\).
Для каждой активной строки вычисляется точная верхняя граница \(y_{\max}(x)\) по обратной pronic-формуле, после чего первое значение \(P(x)^2\) помещается в очередь с приоритетом. Каждый элемент очереди хранит достаточно информации, чтобы перейти к следующему произведению из той же строки.
Главный цикл каждый раз извлекает наименьшее текущее произведение. Если оно отличается от предыдущего извлеченного значения, ответ увеличивается на \(1\). Затем соответствующая строка продвигается от \(y\) к \(y+1\), и ее новый продукт снова помещается в очередь, если он еще допустим. В C++ куча реализована вручную, а в Python и Java используются стандартные приоритетные структуры, но алгоритм во всех трех версиях один и тот же.
Обозначим
$$K=\#\{x:P(x)^2\le L\},\qquad M=\sum_{x=1}^{K}\bigl(y_{\max}(x)-x+1\bigr).$$
Построение таблицы pronic-чисел до глобальной границы требует \(O(\sqrt{L})\) времени и \(O(\sqrt{L})\) памяти, потому что максимальный нужный индекс определяется условием \(P(y)\le L\). Фаза работы с очередью с приоритетом выполняет одно извлечение и не более одной вставки на каждую сгенерированную пару, поэтому занимает \(O(M\log K)\) времени и использует \(O(K)\) дополнительной памяти для кучи.
Принципиально важно, что реализация никогда не хранит все \(M\) произведений одновременно. В памяти находится только один текущий кандидат на каждую активную строку, и именно это делает метод практичным для очень больших ограничений.
يُسمى العدد الصحيح الموجب \(N\) عددًا stealthy إذا وُجدت أعداد صحيحة موجبة \(a,b,c,d\) تحقق
$$ab=cd=N,\qquad a+b=c+d+1.$$
المطلوب هو عدّ عدد القيم المختلفة التي تحقق \(N\le L\). الفكرة الأساسية التي تعتمد عليها التطبيقات هي أن الأعداد stealthy هي بالضبط نواتج ضرب عددين pronic.
لنعرّف دالة pronic بالصيغة
$$P(t)=t(t+1).$$
بعد ذلك تصبح المسألة قابلة للحل عندما نثبت أن كل عدد stealthy يمكن كتابته على صورة \(P(x)P(y)\)، ثم نعد هذه النواتج بعد إزالة التكرار.
لنأخذ زوجين من القواسم للعدد stealthy نفسه، ولنفرض أن \((a,b)\) هو الزوج ذو المجموع الأكبر. بعد ترتيب العوامل داخل كل زوج، يقع الزوج الآخر بينهما، ولذلك يمكننا أن نكتب
$$c=a+k,\qquad d=b-k-1,\qquad k\ge 1.$$
وباستخدام الشرط \(ab=cd\) نحصل على
$$ab=(a+k)(b-k-1)=ab+k(b-a-k-1)-a.$$
ومن ثم
$$a=k(b-a-k-1).$$
إذن \(k\) يقسم \(a\). نكتب لذلك
$$a=ky,\qquad y\ge 1.$$
وبالتعويض ينتج
$$b=(k+1)(y+1),\qquad c=k(y+1),\qquad d=(k+1)y.$$
وبالتالي
$$N=ab=k(k+1)y(y+1).$$
وبإعادة تسمية \(k\) إلى \(x\) نحصل على التمثيل القياسي
$$\boxed{N=x(x+1)y(y+1).}$$
هذه الصيغة ليست شرطًا لازمًا فقط، بل هي كافية أيضًا. لأي عددين موجبين \(x\) و\(y\)، انظر إلى زوجي العوامل
$$xy\cdot (x+1)(y+1),\qquad x(y+1)\cdot y(x+1).$$
كلا الناتجين يساوي
$$x(x+1)y(y+1),$$
ومجموعا العوامل يختلفان بمقدار \(1\) تمامًا:
$$xy+(x+1)(y+1)=x(y+1)+y(x+1)+1.$$
إذن كل عدد على الصورة \(x(x+1)y(y+1)\) هو عدد stealthy فعلًا. وهكذا تصبح المسألة هي عدّ القيم المختلفة من الشكل
$$P(x)P(y),\qquad x,y\ge 1.$$
ولأن
$$P(x)P(y)=P(y)P(x),$$
يمكننا فرض الشرط
$$1\le x\le y$$
حتى لا نعدّ التناظر نفسه مرتين.
عند تثبيت \(x\)، يجب أن تحقق قيم \(y\) الممكنة الشرط
$$P(x)P(y)\le L,$$
أي
$$P(y)\le \left\lfloor\frac{L}{P(x)}\right\rfloor.$$
إذا عرّفنا
$$T_x=\left\lfloor\frac{L}{P(x)}\right\rfloor,$$
فإن \(y\) يجب أن يحقق
$$y(y+1)\le T_x.$$
والجذر الموجب للمعادلة \(y^2+y-T_x=0\) هو
$$\frac{-1+\sqrt{1+4T_x}}{2},$$
ومن ثم فإن أكبر قيمة صحيحة صالحة هي
$$y_{\max}(x)=\left\lfloor\frac{\sqrt{1+4T_x}-1}{2}\right\rfloor.$$
كما توجد حدود على \(x\) نفسه. لأن \(y\ge x\)، فإن أصغر حاصل ضرب في الصف الخاص بـ \(x\) هو \(P(x)^2\). لذلك لا يكون هذا الصف نشطًا إلا إذا تحقق
$$P(x)^2\le L.$$
لكل قيمة فعالة من \(x\)، نعرّف السلسلة
$$V_x=\{P(x)P(y): y=x,x+1,\dots,y_{\max}(x)\}.$$
وبما أن \(P(y)\) تزداد زيادة صارمة مع \(y\)، فإن كل سلسلة \(V_x\) تكون مرتبة تصاعديًا هي الأخرى. لذلك فمجموعة المرشحات كلها ليست مجرد ناتج دوران مزدوج عشوائي، بل هي اتحاد عدة سلاسل مرتبة مسبقًا، وهذا يحول المسألة إلى مسألة دمج k-way.
تحتفظ بنية min-heap بأصغر عنصر غير معالج حاليًا من كل سلسلة \(V_x\). وعند استخراج أصغر عنصر في كل مرة نحصل على تيار القيم المرشحة العالمي بترتيب تصاعدي. وبعد استهلاك قيمة من صف معين، نضيف القيمة التالية من الصف نفسه.
قد تظهر التكرارات لأن العدد stealthy نفسه قد ينتج من أكثر من زوج بارامترات. لكن بما أن التيار الناتج بعد الدمج مرتب، فإن القيم المتساوية تظهر متجاورة. لذلك يكفي مقارنتها بالقيمة المستخرجة السابقة:
$$v_{\mathrm{current}}\ne v_{\mathrm{previous}}.$$
ولهذا تستطيع التطبيقات عدّ القيم المختلفة من دون الحاجة إلى تخزين كل النواتج داخل مجموعة عامة ضخمة.
لنحسب أولًا أعداد pronic ذات الصلة:
$$P(1)=2,\quad P(2)=6,\quad P(3)=12,\quad P(4)=20.$$
وبما أن \(P(4)^2=400>200\)، فإن الصفوف الفعالة الوحيدة هي \(x=1,2,3\).
عندما \(x=1\)، يجب أن يكون \(2P(y)\le 200\)، أي \(P(y)\le 100\)، ومن ثم \(y_{\max}(1)=9\). هذا الصف يعطي
$$4,12,24,40,60,84,112,144,180.$$
وعندما \(x=2\)، نحتاج إلى \(6P(y)\le 200\)، أي \(P(y)\le 33\)، ولذلك \(y_{\max}(2)=5\). هذا الصف يعطي
$$36,72,120,180.$$
أما عند \(x=3\)، فلا يصلح إلا \(y=3\)، فنحصل على
$$144.$$
وبعد الدمج وإزالة التكرار نحصل على
$$4,12,24,36,40,60,72,84,112,120,144,180,$$
أي يوجد \(12\) عددًا stealthy لا يتجاوز \(200\). وظهور \(144\) و\(180\) أكثر من مرة يوضح مباشرة سبب ضرورة إزالة التكرار.
تبدأ تطبيقات C++ وPython وJava ببناء جدول لجميع أعداد pronic حتى الحد العام \(P(y)\le L\). ثم تحدد أي الصفوف الابتدائية فعالة عبر فحص الشرط \(P(x)^2\le L\).
لكل صف فعال، تحسب الشيفرة الحد الأعلى الدقيق \(y_{\max}(x)\) باستخدام صيغة الدالة العكسية السابقة، ثم تضع أول قيمة \(P(x)^2\) في طابور أولوية. ويحمل كل عنصر في الطابور المعلومات اللازمة لتوليد القيمة التالية من الصف نفسه.
في الحلقة الرئيسية تُزال أصغر قيمة حالية. إذا كانت مختلفة عن القيمة التي أزيلت قبلها مباشرة، يُزاد الجواب بمقدار \(1\). بعد ذلك يُقدَّم الصف المقابل من \(y\) إلى \(y+1\)، وتُعاد القيمة الجديدة إلى الطابور إذا بقيت ضمن المجال الصحيح. نسخة C++ تدير heap ثنائيًا يدويًا، بينما تستخدم نسختا Python وJava هياكل أولوية جاهزة، لكن الفكرة الخوارزمية واحدة في اللغات الثلاث.
لنعرّف
$$K=\#\{x:P(x)^2\le L\},\qquad M=\sum_{x=1}^{K}\bigl(y_{\max}(x)-x+1\bigr).$$
بناء جدول pronic حتى الحد العام يكلف \(O(\sqrt{L})\) زمنًا و\(O(\sqrt{L})\) ذاكرة، لأن أكبر فهرس مطلوب تحدده العلاقة \(P(y)\le L\). أما مرحلة طابور الأولوية فتجري عملية استخراج واحدة وعلى الأكثر عملية إدراج واحدة لكل زوج مولد، ولذلك تكلف \(O(M\log K)\) زمنًا و\(O(K)\) ذاكرة إضافية للـ heap.
والنقطة الأهم أن التطبيق لا يخزن جميع النواتج \(M\) في الوقت نفسه. فهو يحتفظ بمرشح حالي واحد فقط لكل صف فعال، وهذه بالضبط هي الفكرة التي تجعل الطريقة عملية حتى عندما يكون الحد كبيرًا جدًا.