A sqube is a number of the form
$$n=p^2q^3,\qquad p\neq q,\qquad p,q\text{ prime}.$$
The task is to find the 200th sqube whose decimal expansion contains the contiguous substring "200" and which is prime-proof, meaning that every valid one-digit change produces a composite number. The arithmetic form \(p^2q^3\) is the main structural restriction, and the decimal pattern and prime-proof property are two additional filters applied to that sparse family.
There is no closed formula for the 200th answer. The practical route is therefore to enumerate all squbes below a bound, sort them, and test each candidate with exact criteria that mirror the statement of the problem.
The solution is best understood as a search over a highly structured set, not as a scan over all integers. The number-theoretic part identifies which values can even be candidates, and the decimal and primality parts then certify which of those candidates survive.
For a fixed bound \(L\), every relevant candidate lies in
$$\mathcal S(L)=\{p^2q^3: p,q\text{ prime},\ p\neq q,\ p^2q^3\le L\}.$$
Because the smallest possible cube prime is \(2\), any such candidate satisfies
$$p^2\le \frac{L}{2^3}=\frac{L}{8},\qquad p\le \sqrt{L/8}.$$
Once \(p\) is fixed, the cube prime must satisfy
$$q^3\le \frac{L}{p^2},\qquad q\le \left(\frac{L}{p^2}\right)^{1/3}.$$
So the search space is finite and can be generated by nested loops over primes with an early stop as soon as \(p^2q^3\) exceeds the current bound.
A useful way to write the candidate count is
$$M(L)=\sum_{\substack{p\le \sqrt{L/8}\\ p\text{ prime}}}\#\left\{q\text{ prime}:q\neq p,\ q\le \left(\frac{L}{p^2}\right)^{1/3}\right\}.$$
This expression is not evaluated symbolically in the code, but it makes the geometry of the enumeration explicit.
A positive integer \(x\) contains the substring "200" if and only if there exists some offset \(m\ge 0\) such that
$$\left\lfloor \frac{x}{10^m}\right\rfloor \equiv 200 \pmod{1000}.$$
That condition says exactly that some consecutive block of three decimal digits equals 200. Repeatedly checking \(x\bmod 1000\) and then discarding the last digit by integer division by \(10\) is therefore a sliding three-digit window through the decimal expansion. This is the arithmetic content behind the substring filter.
Write the decimal expansion of a \(d\)-digit candidate as
$$x=\sum_{i=0}^{d-1} a_i10^i,\qquad 0\le a_i\le 9,\qquad a_{d-1}\neq 0.$$
If the digit at position \(i\) is replaced by another digit \(b\), the new number is
$$x'=x+(b-a_i)10^i.$$
All choices \(b\neq a_i\) are allowed, except that the leading digit may not be replaced by \(0\). The number \(x\) is prime-proof exactly when every valid value of \(x'\) is composite.
This reformulation explains the code directly. A \(d\)-digit sqube needs at most \(9d\) primality tests, one for each alternative digit at each position, and the candidate is rejected immediately if any modified number is prime.
If \(L_1\le L_2\), then \(\mathcal S(L_1)\subseteq \mathcal S(L_2)\). After the substring filter and the prime-proof filter are applied, the same monotonicity still holds: every valid value found below \(L_1\) remains present below \(L_2\). Therefore, once a bound \(L\) produces at least 200 valid squbes, the 200th element of the sorted list below \(L\) is already the true answer.
This is why two different implementation styles are correct. One implementation starts from a moderate bound and doubles it until enough values are found. The other two choose a very large fixed bound from the beginning. Both rely on the same invariant: enlarging the bound can only add larger candidates, never invalidate smaller ones.
The number \(200\) is already a sqube, because
$$200=5^2\cdot 2^3.$$
It obviously contains the substring "200". To show that it is prime-proof, inspect the three digit positions.
Changing the hundreds digit gives \(100,300,400,\dots,900\), all composite. Changing the tens digit gives \(210,220,\dots,290\), also all composite because they are even and larger than \(2\). Changing the units digit gives \(201,202,\dots,209\); the even values are composite, \(201\) and \(207\) are divisible by \(3\), \(205\) is divisible by \(5\), \(203=7\cdot 29\), and \(209=11\cdot 19\).
So every valid one-digit change of \(200\) is composite. This is the exact logical pattern used for every candidate in the final search.
The C++, Python, and Java implementations all use the same pipeline: generate squbes below a bound, keep only those whose decimal expansion contains "200", and then verify prime-proofness by examining every allowed single-digit modification.
Each implementation begins by producing enough prime numbers with a sieve. It then loops over distinct prime pairs and forms products of the shape \(p^2q^3\) until the current bound is exceeded. The resulting values are collected in a structure that removes duplicates and preserves sorted order after the generation phase.
Two implementations explicitly enumerate both exponent assignments \(p^2q^3\) and \(p^3q^2\), then deduplicate. The C++ implementation covers the same family by letting the squared prime and the cubed prime play ordered roles inside a single formula. The mathematical candidate set is identical in all three languages.
The substring test is implemented in decimal arithmetic or via the decimal string representation, but both versions test the same condition. Only values that pass this stage are sent to the prime-proof check.
For the prime-proof test, the C++ implementation mutates one digit arithmetically using powers of \(10\), which is a direct realization of \(x' = x + (b-a_i)10^i\). The Python and Java implementations rebuild the altered decimal string and convert it back to an integer. These are different surfaces for the same mathematical operation.
Every modified number produced by the prime-proof test must be checked for primality. The C++ implementation uses deterministic Miller-Rabin valid for 64-bit integers. The Python and Java implementations use trial division in the \(6k\pm 1\) pattern. The logic is the same: if any modified value is prime, the original sqube is rejected.
After that, the valid squbes are counted in increasing order. The C++ implementation can grow the bound geometrically until the target count is reached and also includes sanity checks: the first squbes are \(72,108,200,392,500\), and the second prime-proof sqube containing "200" is \(1992008\). The Python and Java implementations instead start from a sufficiently large fixed bound and stop once the 200th valid value is encountered.
Let \(L\) be the final bound large enough to contain the 200th answer, and let \(M(L)\) be the number of squbes generated below that bound. Prime generation by a sieve costs \(O(B\log\log B)\), where \(B\) is the largest sieved integer. In the adaptive version \(B\) is essentially \(\sqrt{L/8}\); in the fixed-bound versions it is chosen on the same square-root scale.
Building the candidate list costs \(O(M(L))\) arithmetic operations before sorting, and ordering the resulting values costs \(O(M(L)\log M(L))\). The substring filter is only linear in the number of decimal digits of each candidate and is comparatively cheap.
The expensive phase is the prime-proof certification. If \(F(L)\) candidates survive the substring test and a candidate \(x\) has \(d(x)\) decimal digits, then the number of primality tests is at most
$$\sum_{x\in F(L)} 9\,d(x).$$
In C++, each of these calls is a fixed-base Miller-Rabin test, so for 64-bit inputs the primality step is effectively near-constant time per call. In Python and Java, trial division has worst-case cost \(O(\sqrt{x})\) per call, but the number of tested neighbors stays manageable because the sqube family is sparse and the decimal filter removes most candidates first.
The memory usage is \(O(M(L))\) for the stored squbes, plus the prime table. The key efficiency gain is structural: the search never scans all integers up to \(L\); it explores only numbers of the specific form \(p^2q^3\), which is a dramatically smaller set.
Ein Sqube ist eine Zahl der Form
$$n=p^2q^3,\qquad p\neq q,\qquad p,q\text{ prim}.$$
Gesucht ist das 200. Sqube, dessen Dezimaldarstellung den zusammenhängenden Teilstring "200" enthält und das prime-proof ist, also bei jeder zulässigen Änderung genau einer Ziffer stets eine zusammengesetzte Zahl liefert. Die Form \(p^2q^3\) ist die arithmetische Grundstruktur; die Dezimalbedingung und die Prime-proof-Eigenschaft sind zusätzliche Filter auf dieser dünnen Kandidatenmenge.
Eine geschlossene Formel für das 200. Element gibt es nicht. Deshalb arbeitet die Lösung mit einer vollständigen, aber stark eingeschränkten Enumeration aller Squbes bis zu einer Schranke und prüft dann jede Kandidatenzahl exakt.
Der zentrale Gedanke ist, nicht alle ganzen Zahlen zu durchsuchen, sondern nur die Zahlen mit der richtigen Primfaktorstruktur. Erst danach werden die dezimale Teilstring-Bedingung und die Prime-proof-Bedingung getestet.
Für eine feste Schranke \(L\) liegen alle relevanten Kandidaten in
$$\mathcal S(L)=\{p^2q^3: p,q\text{ prim},\ p\neq q,\ p^2q^3\le L\}.$$
Da die kleinste mögliche Kubik-Primzahl \(2\) ist, gilt für jeden Kandidaten
$$p^2\le \frac{L}{2^3}=\frac{L}{8},\qquad p\le \sqrt{L/8}.$$
Ist \(p\) fest, so muss außerdem
$$q^3\le \frac{L}{p^2},\qquad q\le \left(\frac{L}{p^2}\right)^{1/3}$$
gelten. Damit ist der Suchraum endlich und lässt sich durch verschachtelte Schleifen über Primzahlen erzeugen, wobei man sofort abbrechen kann, sobald \(p^2q^3\) die Schranke überschreitet.
Eine passende Zählformel ist
$$M(L)=\sum_{\substack{p\le \sqrt{L/8}\\ p\text{ prim}}}\#\left\{q\text{ prim}:q\neq p,\ q\le \left(\frac{L}{p^2}\right)^{1/3}\right\}.$$
Sie wird im Code nicht symbolisch ausgewertet, macht aber die Struktur der Enumeration klar sichtbar.
Eine positive ganze Zahl \(x\) enthält genau dann den Teilstring "200", wenn es ein \(m\ge 0\) gibt mit
$$\left\lfloor \frac{x}{10^m}\right\rfloor \equiv 200 \pmod{1000}.$$
Das bedeutet, dass irgendwo in der Dezimaldarstellung ein zusammenhängender Drei-Ziffern-Block gleich 200 ist. Wenn man wiederholt \(x\bmod 1000\) betrachtet und danach per ganzzahliger Division durch \(10\) die letzte Ziffer entfernt, schiebt man genau dieses Drei-Ziffern-Fenster von rechts nach links durch die Zahl.
Schreibe die Dezimaldarstellung eines \(d\)-stelligen Kandidaten als
$$x=\sum_{i=0}^{d-1} a_i10^i,\qquad 0\le a_i\le 9,\qquad a_{d-1}\neq 0.$$
Ersetzt man die Ziffer an Position \(i\) durch eine andere Ziffer \(b\), dann entsteht
$$x'=x+(b-a_i)10^i.$$
Alle Werte \(b\neq a_i\) sind zulässig, außer \(b=0\) an der führenden Stelle. Genau dann ist \(x\) prime-proof, wenn jede so entstehende gültige Zahl \(x'\) zusammengesetzt ist.
Diese Formulierung erklärt die Implementierung unmittelbar. Für einen \(d\)-stelligen Kandidaten sind höchstens \(9d\) Primzahltests nötig, einer für jede alternative Ziffer an jeder Position, und beim ersten Primtreffer wird der Kandidat verworfen.
Aus \(L_1\le L_2\) folgt \(\mathcal S(L_1)\subseteq \mathcal S(L_2)\). Dieselbe Monotonie bleibt auch nach dem Teilstring-Filter und dem Prime-proof-Filter erhalten: Jeder gültige Wert unter \(L_1\) bleibt auch unter \(L_2\) erhalten. Sobald also eine Schranke \(L\) mindestens 200 gültige Squbes liefert, ist das 200. Element der sortierten Liste bereits die gesuchte globale Antwort.
Darauf beruhen beide Implementationsstile. Eine Version startet mit einer kleineren Schranke und verdoppelt sie, bis genug Werte gefunden sind. Die beiden anderen wählen von Anfang an eine großzügige feste Schranke. Mathematisch ist das dieselbe Aussage: Eine größere Schranke kann nur zusätzliche, größere Kandidaten hinzufügen, niemals frühere entfernen.
Die Zahl \(200\) ist bereits ein Sqube, denn
$$200=5^2\cdot 2^3.$$
Den Teilstring "200" enthält sie offensichtlich. Für die Prime-proof-Eigenschaft betrachtet man die drei Ziffernpositionen getrennt.
Ändert man die Hunderterziffer, erhält man \(100,300,400,\dots,900\), also nur zusammengesetzte Zahlen. Ändert man die Zehnerziffer, entstehen \(210,220,\dots,290\), ebenfalls alle zusammengesetzt, weil sie gerade und größer als \(2\) sind. Ändert man die Einerziffer, erhält man \(201,202,\dots,209\); die geraden Werte sind zusammengesetzt, \(201\) und \(207\) sind durch \(3\) teilbar, \(205\) durch \(5\), \(203=7\cdot 29\) und \(209=11\cdot 19\).
Damit führt jede zulässige Ein-Ziffer-Änderung von \(200\) zu einer zusammengesetzten Zahl. Genau dieses Argumentmuster wird später auf jeden Kandidaten angewandt.
Die C++-, Python- und Java-Implementierungen folgen derselben Pipeline: Squbes unter einer Schranke erzeugen, nur die Werte mit Teilstring "200" behalten und anschließend mit allen zulässigen Ein-Ziffer-Änderungen prüfen, ob sie prime-proof sind.
Zunächst werden genügend Primzahlen mit einem Sieb erzeugt. Danach laufen die Programme über Paare verschiedener Primzahlen und bilden Produkte der Form \(p^2q^3\), solange die aktuelle Schranke nicht überschritten wird. Die entstehenden Werte werden in einer Datenstruktur gesammelt, die Duplikate entfernt und am Ende eine Verarbeitung in aufsteigender Reihenfolge erlaubt.
Zwei Implementierungen durchlaufen explizit beide Exponentenverteilungen \(p^2q^3\) und \(p^3q^2\) und entfernen danach Duplikate. Die C++-Implementierung beschreibt dieselbe Zahlenfamilie mit einer einzigen Formel, in der die quadratische und die kubische Primzahl geordnete Rollen spielen. Mathematisch ist die Kandidatenmenge in allen drei Sprachen dieselbe.
Der Teilstring-Test wird entweder rein arithmetisch oder über die Dezimalzeichenkette umgesetzt; beides prüft exakt dieselbe Bedingung. Nur Werte, die diesen Test bestehen, gelangen in die Prime-proof-Prüfung.
Bei der Ziffernänderung unterscheiden sich die Implementierungen nur in der Darstellung. Die C++-Version verändert Ziffern arithmetisch mit Zehnerpotenzen und setzt damit direkt \(x' = x + (b-a_i)10^i\) um. Python und Java bauen die veränderte Dezimalzeichenkette neu zusammen und wandeln sie zurück in eine Zahl. Das mathematische Nachbarschaftsmodell ist identisch.
Jede durch die Prime-proof-Prüfung erzeugte Nachbarzahl wird auf Primzahleigenschaft getestet. Die C++-Implementierung verwendet dafür einen deterministischen Miller-Rabin-Test, der für 64-Bit-Zahlen gültig ist. Python und Java verwenden Probeteilung im Muster \(6k\pm 1\). Die Logik bleibt gleich: Sobald eine veränderte Zahl prim ist, wird das ursprüngliche Sqube verworfen.
Die verbleibenden gültigen Werte werden dann in aufsteigender Reihenfolge gezählt. Die C++-Implementierung kann die Schranke geometrisch vergrößern, bis das Ziel erreicht ist, und enthält zusätzlich Plausibilitätsprüfungen: Die ersten Squbes sind \(72,108,200,392,500\), und das zweite prime-proof Sqube mit Teilstring "200" ist \(1992008\). Python und Java starten stattdessen mit einer ausreichend großen festen Schranke und brechen ab, sobald der 200. gültige Wert gefunden ist.
Sei \(L\) die endgültige Schranke, die die 200. Lösung bereits enthält, und sei \(M(L)\) die Anzahl der darunter erzeugten Squbes. Die Primzahlerzeugung mit einem Sieb kostet \(O(B\log\log B)\), wobei \(B\) die größte ausgesiebte Zahl ist. In der adaptiven Variante liegt \(B\) im Wesentlichen bei \(\sqrt{L/8}\); in den Varianten mit fester Schranke ist dieselbe Größenordnung relevant.
Das Erzeugen der Kandidaten kostet vor dem Sortieren \(O(M(L))\) arithmetische Operationen, und das Sortieren kostet \(O(M(L)\log M(L))\). Der Teilstring-Test ist nur linear in der Zahl der Dezimalstellen eines Kandidaten und daher vergleichsweise billig.
Der teure Teil ist die Prime-proof-Zertifizierung. Wenn nach dem Teilstring-Test noch \(F(L)\) Kandidaten übrig bleiben und \(x\) genau \(d(x)\) Dezimalstellen hat, dann ist die Zahl der Primzahltests höchstens
$$\sum_{x\in F(L)} 9\,d(x).$$
In C++ ist jeder dieser Tests ein fester Miller-Rabin-Aufruf, sodass der Aufwand pro Test auf 64-Bit-Eingaben praktisch nahezu konstant ist. In Python und Java hat die Probeteilung im schlechtesten Fall Aufwand \(O(\sqrt{x})\) pro Test. Praktisch bleibt die Laufzeit trotzdem beherrschbar, weil die Squbes schon eine sehr dünne Menge bilden und der Dezimalfilter den größten Teil der Kandidaten entfernt, bevor die Primzahltests dominieren.
Der Speicherbedarf beträgt \(O(M(L))\) für die gespeicherten Squbes plus die Primzahlliste. Der entscheidende Effizienzgewinn liegt also nicht in einer geheimen Formel, sondern darin, dass niemals alle Zahlen bis \(L\) betrachtet werden, sondern nur die deutlich kleinere Menge der Zahlen vom Typ \(p^2q^3\).
Bir sqube şu biçimdedir:
$$n=p^2q^3,\qquad p\neq q,\qquad p,q\text{ asal}.$$
Aranan değer, ondalık gösteriminde bitişik "200" alt dizisini taşıyan ve prime-proof olan 200. sqube'dür. Prime-proof olmak, sayının herhangi bir tek basamağı geçerli bir biçimde değiştirildiğinde elde edilen her yeni sayının bileşik olması demektir. Dolayısıyla problem, önce \(p^2q^3\) biçimindeki seyrek aday kümesini belirlemeyi, sonra bu adaylar üzerinde ondalık ve asallık filtreleri uygulamayı gerektirir.
200. değeri doğrudan veren kapalı bir formül yoktur. Bu yüzden çözüm, belirli bir üst sınır altındaki bütün sqube'leri üretip sıralar ve her adayı problemdeki iki özel koşula göre tek tek sınar.
Temel fikir, tüm tamsayıları değil yalnızca doğru asal üs yapısına sahip sayıları taramaktır. Asıl verim kazancı burada gelir; geri kalan kısım, bu daha küçük kümeyi hassas testlerden geçirmekten ibarettir.
Sabit bir \(L\) üst sınırı için bütün adaylar
$$\mathcal S(L)=\{p^2q^3: p,q\text{ asal},\ p\neq q,\ p^2q^3\le L\}$$
kümesinde yatar. Küp tarafındaki en küçük asal \(2\) olduğundan her aday için
$$p^2\le \frac{L}{2^3}=\frac{L}{8},\qquad p\le \sqrt{L/8}$$
olmalıdır. \(p\) sabitlendikten sonra diğer asal için de
$$q^3\le \frac{L}{p^2},\qquad q\le \left(\frac{L}{p^2}\right)^{1/3}$$
sınırı elde edilir. Böylece arama uzayı sonludur ve asal çiftleri üzerinde dolaşan iç içe döngülerle üretilebilir; ürün \(p^2q^3\) sınırı aştığı anda ilgili iç döngü kırılır.
Aday sayısını ifade eden uygun bir formül şudur:
$$M(L)=\sum_{\substack{p\le \sqrt{L/8}\\ p\text{ asal}}}\#\left\{q\text{ asal}:q\neq p,\ q\le \left(\frac{L}{p^2}\right)^{1/3}\right\}.$$
Kod bu toplamı sembolik olarak kullanmaz; fakat üretimin neden yönetilebilir olduğunu açıkça gösterir.
Pozitif bir \(x\) sayısı, ancak ve ancak bir \(m\ge 0\) için
$$\left\lfloor \frac{x}{10^m}\right\rfloor \equiv 200 \pmod{1000}$$
koşulu sağlanıyorsa "200" alt dizisini içerir. Bunun anlamı, sayının ondalık açılımında ardışık üç basamaktan oluşan bir pencerenin tam olarak 200 olmasıdır. \(x\bmod 1000\) kontrol edilip sonra \(x\) her seferinde \(10\)'a bölünürse, bu üç basamaklı pencere sağdan sola kaydırılmış olur.
\(d\) basamaklı bir adayın ondalık açılımını
$$x=\sum_{i=0}^{d-1} a_i10^i,\qquad 0\le a_i\le 9,\qquad a_{d-1}\neq 0$$
şeklinde yazalım. \(i\). basamaktaki rakam \(a_i\), başka bir \(b\) rakamıyla değiştirilirse yeni sayı
$$x'=x+(b-a_i)10^i$$
olur. Burada \(b\neq a_i\) olmalıdır; ayrıca en soldaki basamak için \(b=0\) yasaktır. Tam olarak bütün geçerli \(x'\) değerleri bileşikse, \(x\) prime-proof'tur.
Bu ifade doğrudan uygulamayı açıklıyor. \(d\) basamaklı bir aday için en fazla \(9d\) adet asallık testi gerekir; her konumda orijinal rakam dışında dokuz seçenek vardır ve bunlardan biri asal çıkarsa aday hemen elenir.
\(L_1\le L_2\) ise \(\mathcal S(L_1)\subseteq \mathcal S(L_2)\) olur. Aynı tekdüzelik, "200" filtresi ve prime-proof filtresi uygulandıktan sonra da korunur: daha küçük sınır altında bulunan her geçerli sayı, daha büyük sınır altında da bulunur. O halde bir \(L\) sınırı altında en az 200 geçerli sqube elde edildiği anda, sıralı listenin 200. elemanı gerçek cevaptır.
Bu nedenle iki farklı uygulama tarzı da doğrudur. Bir sürüm sınırı küçük başlatıp gerektiğinde iki katına çıkarır. Diğer iki sürüm baştan büyük bir sabit sınır seçer. İkisi de aynı değişmeze dayanır: sınırı büyütmek yalnızca daha büyük adaylar ekler, daha önce bulunanları geçersiz kılmaz.
\(200\) sayısı zaten bir sqube'dür, çünkü
$$200=5^2\cdot 2^3.$$
Ayrıca açıkça "200" alt dizisini içerir. Prime-proof olduğunu görmek için üç basamak konumunu ayrı ayrı incelemek yeterlidir.
Yüzler basamağı değiştirilirse \(100,300,400,\dots,900\) elde edilir; bunların hepsi bileşiktir. Onlar basamağı değiştirilirse \(210,220,\dots,290\) oluşur; bunlar da çift ve \(2\)'den büyük oldukları için bileşiktir. Birler basamağı değiştiğinde \(201,202,\dots,209\) sayıları gelir; çift olanlar bileşiktir, \(201\) ve \(207\) sayıları \(3\)'e bölünür, \(205\) sayısı \(5\)'e bölünür, \(203=7\cdot 29\) ve \(209=11\cdot 19\) olur.
Dolayısıyla \(200\)'ün bütün geçerli tek basamak komşuları bileşiktir. Nihai aramada her aday için yapılan mantık tam olarak budur.
C++, Python ve Java uygulamaları aynı boru hattını izler: önce belli bir sınır altındaki sqube'leri üretir, sonra "200" içermeyenleri eler, son olarak kalan adayların prime-proof olup olmadığını her geçerli tek basamak değişimini deneyerek denetler.
Her uygulama önce bir asal listesi üretir. Ardından farklı asal çiftleri üzerinde dolaşarak \(p^2q^3\) biçimindeki değerleri sınır aşılıncaya kadar hesaplar. Üretilen sayılar, tekrarları temizleyen bir yapı içinde toplanır ve sonunda artan sırada işlenir.
İki uygulama hem \(p^2q^3\) hem de \(p^3q^2\) biçimlerini açıkça üretip sonra tekilleştirir. C++ uygulaması ise aynı sqube ailesini, karesi alınan asal ile küpü alınan asalı tek formül içinde sıralı roller olarak düşünerek kapsar. Matematiksel aday kümesi her üç dilde de aynıdır.
"200" filtresi kimi yerde aritmetik işlemlerle, kimi yerde sayının ondalık dizgesi üzerinden yapılır; fakat iki yaklaşım da aynı koşulu test eder. Bu filtreden geçmeyen adaylar prime-proof aşamasına hiç ulaşmaz.
Prime-proof denetiminde fark yalnızca temsil düzeyindedir. C++ sürümü \(10\)'un kuvvetlerini kullanarak rakamı aritmetik olarak değiştirir; bu, doğrudan \(x' = x + (b-a_i)10^i\) formülüdür. Python ve Java sürümleri değişmiş ondalık dizgeyi yeniden kurup tekrar sayıya çevirir. Matematiksel komşuluk kümesi aynı kalır.
Prime-proof kontrolünde üretilen her yeni sayının asal olup olmadığına bakılır. C++ uygulaması 64 bit için deterministik Miller-Rabin kullanır. Python ve Java uygulamaları ise \(6k\pm 1\) örüntüsünde deneme bölmesi yapar. Mantık değişmez: değiştirilmiş sayılardan biri asal ise ilk aday reddedilir.
Ardından geçerli sqube'ler küçükten büyüğe sayılır. C++ uygulaması hedefe ulaşana kadar sınırı katlayarak büyütebilir ve ayrıca iki sağlama içerir: ilk sqube'ler \(72,108,200,392,500\), "200" içeren ikinci prime-proof sqube ise \(1992008\)'dir. Python ve Java uygulamaları bunun yerine yeterince büyük sabit bir sınırdan başlar ve 200. geçerli değere ulaşınca durur.
\(L\), 200. cevabı içerecek kadar büyük son sınır; \(M(L)\) ise bu sınır altında üretilen sqube sayısı olsun. Asal üretmek için kullanılan elek \(O(B\log\log B)\) maliyetlidir; burada \(B\), elenen en büyük tam sayıdır. Uyarlamalı sürümde bu büyüklük yaklaşık \(\sqrt{L/8}\) mertebesindedir; sabit sınırlı sürümlerde de aynı karekök ölçeği kullanılır.
Aday listesini kurmak sıralama öncesinde \(O(M(L))\) aritmetik işlem gerektirir. Daha sonra sıralama \(O(M(L)\log M(L))\) sürer. "200" filtresi, her adayın basamak sayısı kadar işlem yaptığı için görece ucuzdur.
Pahalı kısım prime-proof sertifikasıdır. "200" filtresinden sonra \(F(L)\) aday kalıyorsa ve \(x\) adayının basamak sayısı \(d(x)\) ise, toplam asallık testi sayısı en fazla
$$\sum_{x\in F(L)} 9\,d(x)$$
olur. C++ tarafında bu testlerin her biri sabit tabanlı Miller-Rabin çağrısı olduğundan 64 bit girdiler için pratikte neredeyse sabit zamandır. Python ve Java tarafında deneme bölmesi en kötü durumda çağrı başına \(O(\sqrt{x})\) maliyetlidir; ancak sqube kümesi seyrek olduğu ve ondalık filtre çoğu adayı daha başta elediği için toplam çalışma süresi yine makul kalır.
Bellek kullanımı, saklanan sqube'ler ve asal tablosu için \(O(M(L))\) mertebesindedir. Asıl hız kazancı da buradan gelir: yöntem \(L\)'ye kadar olan tüm sayıları taramaz, yalnızca \(p^2q^3\) biçimindeki çok daha küçük kümeyi dolaşır.
Un sqube es un número de la forma
$$n=p^2q^3,\qquad p\neq q,\qquad p,q\text{ primos}.$$
La tarea consiste en hallar el sqube número 200 cuya expansión decimal contiene la subcadena contigua "200" y que además es prime-proof, es decir, cualquier cambio válido de una sola cifra produce un número compuesto. La estructura \(p^2q^3\) reduce drásticamente el universo de búsqueda; después se aplican los filtros decimal y de primalidad.
No hay una fórmula cerrada para obtener directamente el término número 200. Por eso la solución enumera todos los squbes por debajo de una cota, los ordena y certifica cada candidato mediante condiciones exactas que reproducen el enunciado.
La clave es no recorrer todos los enteros, sino solo los números con la factorización prima correcta. A partir de ese conjunto mucho más pequeño, los otros dos requisitos se convierten en comprobaciones finitas y directas.
Para una cota fija \(L\), todos los candidatos relevantes pertenecen a
$$\mathcal S(L)=\{p^2q^3: p,q\text{ primos},\ p\neq q,\ p^2q^3\le L\}.$$
Como el menor primo que puede aparecer con exponente \(3\) es \(2\), cualquier candidato cumple
$$p^2\le \frac{L}{2^3}=\frac{L}{8},\qquad p\le \sqrt{L/8}.$$
Fijado \(p\), el otro primo debe satisfacer
$$q^3\le \frac{L}{p^2},\qquad q\le \left(\frac{L}{p^2}\right)^{1/3}.$$
Así, el conjunto de búsqueda es finito y puede generarse con dos bucles sobre primos, deteniéndose en cuanto \(p^2q^3\) supera la cota.
Una forma cómoda de expresar el número de candidatos es
$$M(L)=\sum_{\substack{p\le \sqrt{L/8}\\ p\text{ primo}}}\#\left\{q\text{ primo}:q\neq p,\ q\le \left(\frac{L}{p^2}\right)^{1/3}\right\}.$$
El código no evalúa esta suma simbólicamente, pero la fórmula deja clara la estructura de la enumeración.
Un entero positivo \(x\) contiene la subcadena "200" si y solo si existe algún desplazamiento \(m\ge 0\) tal que
$$\left\lfloor \frac{x}{10^m}\right\rfloor \equiv 200 \pmod{1000}.$$
Eso significa exactamente que algún bloque consecutivo de tres cifras decimales es igual a 200. Por tanto, comprobar \(x\bmod 1000\) y luego dividir \(x\) entre \(10\) de manera entera equivale a deslizar una ventana de tres cifras de derecha a izquierda por la representación decimal.
Escribamos un candidato de \(d\) cifras como
$$x=\sum_{i=0}^{d-1} a_i10^i,\qquad 0\le a_i\le 9,\qquad a_{d-1}\neq 0.$$
Si reemplazamos la cifra \(a_i\) por otra cifra \(b\), obtenemos
$$x'=x+(b-a_i)10^i.$$
Se admiten todos los valores \(b\neq a_i\), salvo \(b=0\) en la cifra más significativa porque eso introduciría un cero inicial. El número \(x\) es prime-proof exactamente cuando todo valor válido de \(x'\) es compuesto.
Esta reformulación describe la implementación con precisión. Un candidato de \(d\) cifras requiere como máximo \(9d\) pruebas de primalidad, una por cada cifra alternativa en cada posición, y basta encontrar una sola modificación prima para descartar el candidato original.
Si \(L_1\le L_2\), entonces \(\mathcal S(L_1)\subseteq \mathcal S(L_2)\). La misma monotonía se conserva después de aplicar el filtro decimal y el filtro prime-proof: todo valor válido encontrado bajo \(L_1\) sigue presente bajo \(L_2\). En consecuencia, en el momento en que una cota \(L\) produce al menos 200 squbes válidos, el elemento número 200 de la lista ordenada ya es la respuesta verdadera del problema completo.
Eso justifica los dos estilos de implementación presentes. Una versión empieza con una cota moderada y la va duplicando hasta tener suficientes resultados. Las otras dos fijan desde el principio una cota grande. Matemáticamente ambos enfoques descansan en el mismo invariante: ampliar la búsqueda solo puede añadir candidatos mayores, nunca invalidar los anteriores.
El número \(200\) ya es un sqube, porque
$$200=5^2\cdot 2^3.$$
Además contiene de forma trivial la subcadena "200". Para ver que es prime-proof basta examinar sus tres posiciones decimales.
Si se cambia la cifra de las centenas, aparecen \(100,300,400,\dots,900\), todos compuestos. Si se cambia la cifra de las decenas, se obtienen \(210,220,\dots,290\), también todos compuestos porque son pares y mayores que \(2\). Si se cambia la unidad, surgen \(201,202,\dots,209\); los pares son compuestos, \(201\) y \(207\) son múltiplos de \(3\), \(205\) es múltiplo de \(5\), \(203=7\cdot 29\) y \(209=11\cdot 19\).
Por tanto, toda modificación válida de una sola cifra de \(200\) es compuesta. Ese es exactamente el patrón lógico que después se aplica a cada candidato.
Las implementaciones en C++, Python y Java siguen la misma tubería: generar squbes bajo una cota, descartar los que no contienen "200" en decimal y, finalmente, comprobar la propiedad prime-proof analizando todas las modificaciones válidas de una sola cifra.
Cada implementación empieza produciendo suficientes números primos mediante una criba. Luego recorre pares de primos distintos y forma productos de tipo \(p^2q^3\) hasta que la cota actual queda superada. Los valores generados se almacenan en una estructura que elimina duplicados y permite procesarlos en orden creciente.
Dos implementaciones enumeran explícitamente tanto \(p^2q^3\) como \(p^3q^2\) y después deduplican. La implementación en C++ cubre la misma familia tratando al primo cuadrático y al primo cúbico como papeles ordenados dentro de una sola fórmula. El conjunto matemático de candidatos es el mismo en los tres lenguajes.
La prueba de la subcadena se implementa con aritmética decimal o con la representación como cadena, pero ambas expresiones comprueban la misma condición. Solo los valores que pasan este filtro llegan a la fase prime-proof.
En el control prime-proof, la diferencia entre implementaciones es puramente mecánica. C++ modifica las cifras aritméticamente usando potencias de \(10\), lo que realiza de manera directa la fórmula \(x' = x + (b-a_i)10^i\). Python y Java reconstruyen la cadena decimal alterada y luego la convierten de nuevo en entero. La vecindad matemática explorada es idéntica.
Cada número vecino generado durante la prueba prime-proof debe someterse a una prueba de primalidad. La implementación en C++ usa Miller-Rabin determinista para enteros de 64 bits. Las implementaciones en Python y Java usan división por prueba con el patrón \(6k\pm 1\). La regla lógica es la misma: si alguna modificación es prima, el sqube original queda descartado.
Después, los squbes válidos se cuentan en orden creciente. La implementación en C++ puede ir ampliando la cota geométricamente hasta alcanzar el objetivo y además incluye comprobaciones internas: los primeros squbes son \(72,108,200,392,500\), y el segundo sqube prime-proof que contiene "200" es \(1992008\). Las implementaciones en Python y Java parten en cambio de una cota fija suficientemente grande y se detienen cuando aparece el término número 200.
Sea \(L\) la cota final que ya contiene la respuesta número 200 y sea \(M(L)\) el número de squbes generados por debajo de ella. Generar los primos con una criba cuesta \(O(B\log\log B)\), donde \(B\) es el mayor entero cribado. En la versión adaptativa, \(B\) está esencialmente en la escala de \(\sqrt{L/8}\); en las versiones de cota fija se usa una escala de la misma magnitud.
Construir la lista de candidatos cuesta \(O(M(L))\) operaciones aritméticas antes de ordenar, y la ordenación cuesta \(O(M(L)\log M(L))\). El filtro de la subcadena es lineal en el número de cifras decimales de cada candidato y, comparativamente, resulta barato.
La parte costosa es la certificación prime-proof. Si \(F(L)\) candidatos sobreviven al filtro decimal y un candidato \(x\) tiene \(d(x)\) cifras, el número total de pruebas de primalidad está acotado por
$$\sum_{x\in F(L)} 9\,d(x).$$
En C++, cada llamada usa Miller-Rabin con bases fijas, de modo que para enteros de 64 bits el coste por prueba es prácticamente constante. En Python y Java, la división por prueba tiene coste peor caso \(O(\sqrt{x})\) por llamada, pero la cantidad de vecinos examinados sigue siendo razonable porque la familia de squbes es dispersa y el filtro decimal descarta la mayoría de candidatos antes de llegar a esta etapa.
El uso de memoria es \(O(M(L))\) para almacenar los squbes, además de la tabla de primos. La ganancia de eficiencia no viene de un truco oculto, sino de restringir la exploración a los números de la forma \(p^2q^3\), que son muchísimo menos numerosos que todos los enteros hasta \(L\).
Sqube 指的是形如
$$n=p^2q^3,\qquad p\neq q,\qquad p,q\text{ 都是素数}$$
的数。题目要求找出第 200 个满足以下两个附加条件的 sqube：它的十进制表示中包含连续子串 “200”，并且它是 prime-proof，也就是任意一次合法的单个数字替换都不会得到素数。这里真正的搜索对象并不是所有整数，而是先被 \(p^2q^3\) 这种质因子结构严格限制过的一小类数，再在这类数上施加十进制模式和 prime-proof 两层筛选。
第 200 个答案没有现成闭式。可行的方法是：先在某个上界内枚举全部 sqube，再按数值顺序检查哪些候选同时满足 “包含 200” 与 “prime-proof” 这两个条件。
这道题最重要的数学观察不是某个递推式，而是如何把搜索范围压缩到足够小。只要 sqube 的枚举方式正确，后面的十进制子串判定与 prime-proof 判定都只是有限、精确、可以穷尽的检查。
给定一个上界 \(L\)，所有可能的候选都属于
$$\mathcal S(L)=\{p^2q^3: p,q\text{ 为素数},\ p\neq q,\ p^2q^3\le L\}.$$
因为带立方指数的一侧最小也至少是 \(2^3=8\)，所以任何候选都必须满足
$$p^2\le \frac{L}{8},\qquad p\le \sqrt{L/8}.$$
当平方那一侧的素数 \(p\) 固定后，立方那一侧的素数 \(q\) 还要满足
$$q^3\le \frac{L}{p^2},\qquad q\le \left(\frac{L}{p^2}\right)^{1/3}.$$
这说明候选集合是有限的，而且可以通过两层素数循环来生成；一旦某个 \(p^2q^3\) 超过当前上界，就可以立刻停止对应的内层循环。
如果想把这种枚举写成计数式，可以写成
$$M(L)=\sum_{\substack{p\le \sqrt{L/8}\\ p\text{ 为素数}}}\#\left\{q\text{ 为素数}:q\neq p,\ q\le \left(\frac{L}{p^2}\right)^{1/3}\right\}.$$
代码并不会真的去求这个公式的闭式值，但它清楚地揭示了候选规模来自哪里。
一个正整数 \(x\) 的十进制表示中包含连续子串 “200”，当且仅当存在某个偏移 \(m\ge 0\)，使得
$$\left\lfloor \frac{x}{10^m}\right\rfloor \equiv 200 \pmod{1000}.$$
这句话的意思是：在十进制展开中，某个连续的三位数字块恰好等于 200。于是只要不断检查 \(x\bmod 1000\)，再把 \(x\) 整除 \(10\)，就等价于让一个三位窗口从最低位向最高位滑动。实现里使用的取模与整除，本质上就是这个十进制窗口判定。
设候选数 \(x\) 有 \(d\) 位，写成
$$x=\sum_{i=0}^{d-1} a_i10^i,\qquad 0\le a_i\le 9,\qquad a_{d-1}\neq 0.$$
如果把第 \(i\) 位数字 \(a_i\) 改成另一个数字 \(b\)，那么新数就是
$$x'=x+(b-a_i)10^i.$$
这里要求 \(b\neq a_i\)；另外最高位不能改成 \(0\)，否则会产生前导零。所谓 \(x\) 是 prime-proof，就是所有合法的 \(x'\) 都必须是合数。
这个公式直接解释了程序结构。一个 \(d\) 位数在每一位上最多有 9 个替代数字，因此最多只需要做 \(9d\) 次素性测试；只要发现某一个修改结果是素数，原候选就立即被淘汰。
如果 \(L_1\le L_2\)，那么 \(\mathcal S(L_1)\subseteq \mathcal S(L_2)\)。经过 “包含 200” 筛选和 prime-proof 筛选之后，这种单调性仍然成立：在较小上界内已经找到的有效值，在更大上界内不会消失。于是只要某个上界 \(L\) 已经给出了至少 200 个合法 sqube，那么按升序排列后的第 200 个值就已经是全局正确答案。
这正是三份实现都成立的原因。一份实现从较小上界开始，不够就把上界翻倍；另外两份实现直接选取一个足够大的固定上界。两种写法依赖的是同一个不变性：扩大搜索范围只会增加更大的候选，不会推翻已经找到的较小答案。
\(200\) 自己就是一个 sqube，因为
$$200=5^2\cdot 2^3.$$
它显然含有连续子串 “200”。再来看 prime-proof 性质。
如果改动百位，就得到 \(100,300,400,\dots,900\)，这些全都是合数。改动十位，会得到 \(210,220,\dots,290\)，它们都是大于 \(2\) 的偶数，所以也全是合数。改动个位时得到 \(201,202,\dots,209\)：其中偶数当然是合数，\(201\) 和 \(207\) 可被 \(3\) 整除，\(205\) 可被 \(5\) 整除，\(203=7\cdot 29\)，\(209=11\cdot 19\)。
因此，\(200\) 的每一个合法单数字邻居都是合数，所以它确实是 prime-proof。完整程序对任意候选做的事情，逻辑上就是这个例子的放大版。
C++、Python 和 Java 三份实现都遵循同一条流水线：先在某个上界下生成 sqube，再筛掉十进制中不含 “200” 的候选，最后对保留下来的数做 prime-proof 验证。
每份实现都会先用筛法准备一批足够大的素数。随后枚举不同的素数对，构造 \(p^2q^3\) 这样的乘积，直到超过当前上界为止。生成出的值会被放进能够去重的容器中，最后按从小到大的顺序处理。
其中两份实现显式枚举 \(p^2q^3\) 和 \(p^3q^2\) 两种指数分配，再统一去重；C++ 实现则把“平方那一侧的素数”和“立方那一侧的素数”作为有序角色放在同一个公式里，从而覆盖同样的 sqube 家族。三种写法在数学上得到的是同一批候选。
“包含 200” 这一关，有的实现用取模和整除来做，有的实现直接使用十进制字符串，但它们检查的是同一个条件。只有通过这一关的候选，才会继续进入 prime-proof 判定。
在 prime-proof 阶段，差异只体现在实现方式上。C++ 版本用 \(10\) 的幂直接做算术改位，这正是公式 \(x' = x + (b-a_i)10^i\) 的直接实现。Python 和 Java 版本则重建修改后的十进制字符串，再转回整数。表面写法不同，检查的单数字邻居集合完全相同。
prime-proof 过程中生成的每个新数都要做素性测试。C++ 实现使用适用于 64 位整数的确定性 Miller-Rabin。Python 和 Java 实现使用 \(6k\pm 1\) 模式的试除法。判断逻辑没有区别：只要某一个改单数字结果是素数，原来的 sqube 就被判为不合格。
最后，把所有合格 sqube 按升序计数。C++ 实现可以按几何方式扩大上界，直到找到足够多的合法值，并且还带有两个针对本题的校验点：最前面的 sqube 是 \(72,108,200,392,500\)，而包含 “200” 的第二个 prime-proof sqube 是 \(1992008\)。Python 和 Java 实现则一开始就采用一个足够大的固定上界，并在遇到第 200 个合法值时停止。
设最终足以包含第 200 个答案的上界为 \(L\)，在该上界下生成出的 sqube 数量记作 \(M(L)\)。筛法生成素数的代价是 \(O(B\log\log B)\)，其中 \(B\) 是被筛到的最大整数。对于自适应版本，\(B\) 基本落在 \(\sqrt{L/8}\) 的量级；固定上界版本使用的也是同样数量级的平方根范围。
构造候选列表本身需要 \(O(M(L))\) 次算术操作，之后排序需要 \(O(M(L)\log M(L))\)。十进制子串过滤对每个候选只按位数线性扫描，因此相对便宜。
真正昂贵的是 prime-proof 认证。如果通过子串过滤后的候选数量是 \(F(L)\)，而某个候选 \(x\) 的十进制位数是 \(d(x)\)，那么总的素性测试次数至多为
$$\sum_{x\in F(L)} 9\,d(x).$$
在 C++ 中，每一次调用都是固定底数的 Miller-Rabin，因此对 64 位整数来说几乎可以看成接近常数时间。Python 和 Java 中使用的试除法单次最坏复杂度是 \(O(\sqrt{x})\)，但由于 sqube 本身很稀疏，而且 “200” 过滤已经提前排除了大部分候选，所以整体运行仍然可控。
空间复杂度是 \(O(M(L))\)，主要来自存储 sqube 以及素数表。这个方法之所以有效，不是因为存在神秘公式，而是因为它从一开始就只搜索 \(p^2q^3\) 这种非常稀疏的数族，而不是把 \(1\) 到 \(L\) 的所有整数都扫一遍。
Sqube — это число вида
$$n=p^2q^3,\qquad p\neq q,\qquad p,q\text{ — простые}.$$
Нужно найти 200-е sqube, в десятичной записи которого встречается непрерывная подстрока "200" и которое является prime-proof, то есть при любой допустимой замене ровно одной цифры получается составное число. Итак, сначала задача ограничивает нас числами специального вида \(p^2q^3\), а затем добавляет два фильтра: десятичный шаблон и устойчивость к одноцифровым изменениям.
Прямой формулы для 200-го ответа нет. Поэтому решение перебирает все sqube ниже некоторой границы, сортирует их и точно проверяет каждый кандидат на соответствие двум дополнительным условиям.
Главная идея состоит не в рекуррентной формуле, а в правильном выборе пространства поиска. Вместо перебора всех целых чисел достаточно исследовать только значения с нужной структурой простых степеней, после чего оставшиеся проверки становятся конечными и прозрачными.
Для фиксированной границы \(L\) все релевантные кандидаты лежат в множестве
$$\mathcal S(L)=\{p^2q^3: p,q\text{ простые},\ p\neq q,\ p^2q^3\le L\}.$$
Так как на кубической стороне минимально возможен простой множитель \(2\), обязательно выполняется
$$p^2\le \frac{L}{2^3}=\frac{L}{8},\qquad p\le \sqrt{L/8}.$$
Когда квадратный простой множитель \(p\) уже выбран, второй простой множитель должен удовлетворять неравенствам
$$q^3\le \frac{L}{p^2},\qquad q\le \left(\frac{L}{p^2}\right)^{1/3}.$$
Значит, множество кандидатов конечно, и его можно породить двойным циклом по простым числам с ранним выходом, как только \(p^2q^3\) превосходит текущую границу.
Удобная запись числа кандидатов имеет вид
$$M(L)=\sum_{\substack{p\le \sqrt{L/8}\\ p\text{ простое}}}\#\left\{q\text{ простое}:q\neq p,\ q\le \left(\frac{L}{p^2}\right)^{1/3}\right\}.$$
Код не использует эту сумму как закрытую формулу, но она ясно показывает структуру перечисления.
Положительное целое число \(x\) содержит подстроку "200" тогда и только тогда, когда существует сдвиг \(m\ge 0\), для которого
$$\left\lfloor \frac{x}{10^m}\right\rfloor \equiv 200 \pmod{1000}.$$
Это просто означает, что некоторый подряд идущий блок из трёх десятичных цифр равен 200. Поэтому операция «проверить \(x\bmod 1000\), затем отбросить последнюю цифру делением на \(10\)» реализует скользящее трёхзначное окно по десятичной записи числа.
Пусть десятичная запись кандидата длины \(d\) равна
$$x=\sum_{i=0}^{d-1} a_i10^i,\qquad 0\le a_i\le 9,\qquad a_{d-1}\neq 0.$$
Если заменить цифру \(a_i\) в позиции \(i\) на другую цифру \(b\), получится число
$$x'=x+(b-a_i)10^i.$$
Разрешены все значения \(b\neq a_i\), кроме \(b=0\) в старшем разряде, поскольку ведущие нули не допускаются. Число \(x\) является prime-proof ровно тогда, когда каждое допустимое \(x'\) составно.
Эта формула непосредственно объясняет структуру программы. Для \(d\)-значного кандидата требуется не более \(9d\) проверок простоты, по одной для каждой альтернативной цифры в каждой позиции, и кандидат отбрасывается сразу, как только обнаруживается простое соседнее число.
Если \(L_1\le L_2\), то \(\mathcal S(L_1)\subseteq \mathcal S(L_2)\). После фильтра по подстроке и после проверки prime-proof эта монотонность сохраняется: любой корректный ответ ниже \(L_1\) остаётся корректным и ниже \(L_2\). Следовательно, как только некоторая граница \(L\) даёт хотя бы 200 допустимых sqube, 200-й элемент отсортированного списка уже является окончательным ответом задачи.
Именно это оправдывает обе стратегии в реализациях. Одна версия начинает с умеренной границы и удваивает её, пока найденных значений не станет достаточно. Две другие сразу выбирают большую фиксированную границу. Математическая причина одинакова: увеличение области поиска может только добавить более крупные кандидаты, но не отменить уже найденные меньшие.
Число \(200\) уже является sqube, поскольку
$$200=5^2\cdot 2^3.$$
Подстрока "200" в нём очевидно присутствует. Проверим теперь свойство prime-proof.
Если менять сотни, получаются \(100,300,400,\dots,900\), и все эти числа составные. Если менять десятки, получаются \(210,220,\dots,290\), и они тоже составные, так как это чётные числа больше \(2\). При изменении единиц возникают \(201,202,\dots,209\): чётные значения составны, \(201\) и \(207\) делятся на \(3\), \(205\) делится на \(5\), \(203=7\cdot 29\), \(209=11\cdot 19\).
Значит, любая допустимая одноцифровая модификация числа \(200\) даёт составное число, и потому \(200\) действительно prime-proof. Для каждого другого кандидата в полном поиске используется ровно та же логика.
Реализации на C++, Python и Java используют одну и ту же схему: сгенерировать sqube ниже некоторой границы, отфильтровать числа без подстроки "200", а затем проверить оставшиеся значения на prime-proof, перебирая все допустимые замены одной цифры.
Сначала каждая реализация строит достаточно большую таблицу простых чисел с помощью решета. Затем перебираются пары различных простых и формируются произведения вида \(p^2q^3\) до тех пор, пока текущая граница не будет превышена. Полученные значения помещаются в структуру, которая устраняет дубликаты и позволяет потом обрабатывать кандидаты в возрастающем порядке.
Две реализации явно перебирают и \(p^2q^3\), и \(p^3q^2\), после чего убирают совпадения. Реализация на C++ покрывает то же семейство, рассматривая простой с квадратом и простой с кубом как упорядоченные роли в одной формуле. С математической точки зрения набор кандидатов во всех трёх языках совпадает.
Проверка подстроки реализована либо чисто арифметически, либо через десятичную строку, но условие во всех случаях одно и то же. Только числа, прошедшие этот этап, поступают на проверку prime-proof.
На этапе одноцифровых замен различается лишь техника реализации. Версия на C++ меняет цифры арифметически с помощью степеней \(10\), что прямо соответствует формуле \(x' = x + (b-a_i)10^i\). Версии на Python и Java заново собирают изменённую десятичную строку и преобразуют её обратно в число. Проверяемое математическое множество соседей при этом одинаково.
Каждое число, полученное при проверке prime-proof, проходит тест на простоту. В C++ используется детерминированный тест Миллера-Рабина, корректный для 64-битных целых. В Python и Java используется пробное деление по схеме \(6k\pm 1\). Логика не меняется: если хотя бы одно модифицированное значение оказывается простым, исходный sqube отвергается.
Далее допустимые sqube подсчитываются в порядке возрастания. Реализация на C++ может геометрически увеличивать границу, пока не будет достигнута целевая мощность, и содержит две внутренние проверки: первые sqube равны \(72,108,200,392,500\), а второе prime-proof sqube, содержащее "200", равно \(1992008\). Реализации на Python и Java сразу берут достаточно большую фиксированную границу и останавливаются, как только встречают 200-е корректное значение.
Пусть \(L\) — итоговая граница, уже содержащая 200-й ответ, а \(M(L)\) — число sqube ниже этой границы. Генерация простых чисел решетом требует \(O(B\log\log B)\), где \(B\) — максимальное просеянное значение. В адаптивной версии \(B\) находится примерно на уровне \(\sqrt{L/8}\); в версиях с фиксированной границей используется тот же квадратный корень по порядку величины.
Построение списка кандидатов требует \(O(M(L))\) арифметических операций до сортировки, а сортировка требует \(O(M(L)\log M(L))\). Фильтр по подстроке работает линейно по числу десятичных цифр и сравнительно дёшев.
Самая дорогая часть — сертификация prime-proof. Если после фильтра по подстроке остаётся \(F(L)\) кандидатов, а число \(x\) имеет \(d(x)\) десятичных цифр, то суммарное число тестов простоты не превосходит
$$\sum_{x\in F(L)} 9\,d(x).$$
В C++ каждый такой вызов — это фиксированный тест Миллера-Рабина, поэтому на 64-битных входах затраты на один тест практически близки к постоянным. В Python и Java пробное деление в худшем случае стоит \(O(\sqrt{x})\) на один вызов, но реальное число проверяемых соседей остаётся умеренным, потому что само семейство sqube разрежено, а фильтр по "200" предварительно отсеивает большую часть кандидатов.
Память расходуется как \(O(M(L))\) на хранение sqube и таблицы простых. Основной выигрыш по эффективности имеет структурную природу: алгоритм не просматривает все числа до \(L\), а работает только с куда более редкими числами вида \(p^2q^3\).
الـ sqube هو عدد من الشكل
$$n=p^2q^3,\qquad p\neq q,\qquad p,q\text{ prime}.$$
المطلوب هو إيجاد الـ sqube رقم 200 الذي يحتوي في كتابته العشرية على السلسلة المتجاورة "200" ويكون prime-proof، أي إن أي تغيير مشروع في رقم واحد فقط يعطي عددًا مركبًا لا عددًا أوليًا. إذن البحث لا يبدأ من جميع الأعداد الصحيحة، بل من العائلة الخاصة \(p^2q^3\)، ثم تُطبَّق عليها شرطية التمثيل العشري وشرطية prime-proof.
لا توجد صيغة مغلقة تعطي الحد رقم 200 مباشرة. لذلك تعتمد الحلول على توليد جميع قيم sqube تحت حد علوي معين، وترتيبها، ثم فحص كل مرشح فحصًا دقيقًا وفقًا لشروط المسألة نفسها.
الفكرة الأساسية ليست علاقة عودية، بل اختيار فضاء الحالة الصحيح. عندما نقصر البحث على الأعداد ذات البنية الأولية المناسبة، تصبح بقية الشروط اختبارات منتهية وواضحة.
لحد علوي ثابت \(L\)، كل المرشحين ينتمون إلى المجموعة
$$\mathcal S(L)=\{p^2q^3: p,q\text{ prime},\ p\neq q,\ p^2q^3\le L\}.$$
وبما أن أصغر أولي يمكن أن يظهر مرفوعًا للقوة الثالثة هو \(2\)، فلا بد أن يتحقق
$$p^2\le \frac{L}{2^3}=\frac{L}{8},\qquad p\le \sqrt{L/8}.$$
وبعد تثبيت \(p\)، يجب أن يحقق الأولي الآخر
$$q^3\le \frac{L}{p^2},\qquad q\le \left(\frac{L}{p^2}\right)^{1/3}.$$
وهذا يعني أن فضاء البحث منتهٍ، ويمكن توليده بحلقتين متداخلتين على الأعداد الأولية مع إيقاف الحلقة الداخلية بمجرد أن يتجاوز \(p^2q^3\) الحد الحالي.
ويمكن كتابة عدد المرشحين على الصورة
$$M(L)=\sum_{\substack{p\le \sqrt{L/8}\\ p\text{ prime}}}\#\left\{q\text{ prime}:q\neq p,\ q\le \left(\frac{L}{p^2}\right)^{1/3}\right\}.$$
الشفرة لا تستخدم هذا التعبير كصيغة مغلقة، لكنه يوضح بدقة كيف يتكون فضاء التوليد.
يحتوي العدد الموجب \(x\) على السلسلة "200" إذا وفقط إذا وُجد إزاحة \(m\ge 0\) بحيث
$$\left\lfloor \frac{x}{10^m}\right\rfloor \equiv 200 \pmod{1000}.$$
ومعنى ذلك أن هناك نافذة مكونة من ثلاث خانات متتالية في التمثيل العشري تساوي 200 بالضبط. لذلك فإن فحص \(x\bmod 1000\) ثم حذف آخر خانة بالقسمة الصحيحة على \(10\) يعادل تحريك نافذة من ثلاث خانات عبر العدد من اليمين إلى اليسار.
لنكتب عددًا مرشحًا ذا \(d\) خانات على الصورة
$$x=\sum_{i=0}^{d-1} a_i10^i,\qquad 0\le a_i\le 9,\qquad a_{d-1}\neq 0.$$
إذا استبدلنا الخانة \(a_i\) في الموضع \(i\) بخانة أخرى \(b\)، فإن العدد الجديد يساوي
$$x'=x+(b-a_i)10^i.$$
كل القيم \(b\neq a_i\) مسموح بها، ما عدا \(b=0\) في الخانة الأكثر أهمية لأن الأصفار البادئة غير مقبولة. ويكون \(x\) prime-proof إذا وفقط إذا كانت كل القيم المسموح بها من \(x'\) أعدادًا مركبة.
هذا الوصف يفسر الشفرة مباشرة. فالعدد ذو \(d\) خانات يحتاج إلى ما لا يزيد على \(9d\) اختبارات أولية، واحد لكل بديل رقمي في كل موضع، ويُرفض المرشح فورًا إذا ظهر تعديل واحد فقط يعطي عددًا أوليًا.
إذا كان \(L_1\le L_2\)، فلدينا \(\mathcal S(L_1)\subseteq \mathcal S(L_2)\). وبعد تطبيق مرشح "200" واختبار prime-proof تبقى هذه الأحادية صحيحة: كل قيمة صحيحة تحت \(L_1\) ستظل موجودة تحت \(L_2\). لذلك، ما إن يعطي حد علوي \(L\) ما لا يقل عن 200 قيمة صالحة، فإن العنصر رقم 200 في القائمة المرتبة يكون بالفعل هو الجواب النهائي.
وهذا يبرر أسلوبي التنفيذ الموجودين في الحلول. إحدى النسخ تبدأ بحد متوسط وتضاعفه حتى تجد عددًا كافيًا من النتائج. والنسختان الأخريان تختاران حدًا ثابتًا كبيرًا منذ البداية. الأساس الرياضي واحد في الحالتين: توسيع مجال البحث لا يمكن إلا أن يضيف مرشحين أكبر، ولا يمكن أن يُبطل المرشحين الأصغر الذين عُثر عليهم سابقًا.
العدد \(200\) هو بالفعل sqube لأن
$$200=5^2\cdot 2^3.$$
وواضح أنه يحتوي على السلسلة "200". بقيت خاصية prime-proof.
إذا غيّرنا خانة المئات نحصل على \(100,300,400,\dots,900\)، وكلها أعداد مركبة. وإذا غيّرنا خانة العشرات نحصل على \(210,220,\dots,290\)، وهي أيضًا مركبة لأنها أعداد زوجية أكبر من \(2\). وإذا غيّرنا خانة الآحاد نحصل على \(201,202,\dots,209\): القيم الزوجية مركبة، والعددان \(201\) و\(207\) يقبلان القسمة على \(3\)، والعدد \(205\) يقبل القسمة على \(5\)، و\(203=7\cdot 29\)، و\(209=11\cdot 19\).
إذن كل تعديل مشروع في رقم واحد من \(200\) يعطي عددًا مركبًا، ومن ثم فهو prime-proof فعلًا. والبرنامج الكامل يكرر هذا المنطق نفسه على كل مرشح.
تتبع تطبيقات C++ وPython وJava المسار نفسه: توليد sqube تحت حد علوي، ثم الاحتفاظ فقط بما يحتوي على "200"، ثم التحقق من prime-proof عبر تجربة كل تعديل مشروع في خانة واحدة.
تبدأ كل نسخة بتوليد قائمة كافية من الأعداد الأولية باستخدام غربال. بعد ذلك تُفحَص أزواج مختلفة من الأعداد الأولية، وتُبنى القيم من النوع \(p^2q^3\) إلى أن يتم تجاوز الحد العلوي. وتُجمَع النتائج في بنية تزيل التكرارات وتسمح بمعالجة القيم بترتيب تصاعدي.
نسختان تولدان صراحةً كلا التوزيعين \(p^2q^3\) و\(p^3q^2\) ثم تزيلان التكرار. أما نسخة C++ فتغطي العائلة نفسها باعتبار الأولي المربَّع والأولي المكعَّب دورين مرتبين داخل صيغة واحدة. المجموعة الرياضية للمرشحين هي نفسها في اللغات الثلاث.
اختبار السلسلة "200" يُنفَّذ إما بالحساب العشري المباشر وإما عبر تحويل العدد إلى سلسلة نصية، لكن الشرط المختبَر واحد. ولا ينتقل إلى فحص prime-proof إلا المرشح الذي ينجح في هذا المرشح الأول.
أما في فحص prime-proof، فالاختلاف شكلي فقط. نسخة C++ تغيّر الخانة حسابيًا باستخدام قوى \(10\)، وهذا يطابق مباشرة الصيغة \(x' = x + (b-a_i)10^i\). أما نسختا Python وJava فتعيدان بناء السلسلة العشرية بعد التغيير ثم تحولانها إلى عدد صحيح من جديد. الجوار العددي الذي يُفحَص هو نفسه تمامًا.
كل عدد جديد يتولد أثناء فحص prime-proof يجب اختباره من حيث الأولية. تستخدم نسخة C++ اختبار Miller-Rabin الحتمي الملائم للأعداد الصحيحة ذات 64 بت. وتستخدم نسختا Python وJava القسمة التجريبية بنمط \(6k\pm 1\). والمنطق ثابت: إذا وُجد تعديل واحد فقط يعطي عددًا أوليًا، يُرفض sqube الأصلي.
بعد ذلك تُحصى قيم sqube الصحيحة بترتيب تصاعدي. تستطيع نسخة C++ تكبير الحد العلوي هندسيًا حتى تصل إلى العدد المطلوب، كما تحتوي على نقطتي تحقق خاصتين بهذه المسألة: أول sqube هي \(72,108,200,392,500\)، وثاني sqube prime-proof يحتوي على "200" هو \(1992008\). أما نسختا Python وJava فتبدآن من حد ثابت كبير بما يكفي وتتوقفان عندما تصادفان القيمة الصحيحة رقم 200.
لنفترض أن \(L\) هو الحد النهائي الذي يحتوي بالفعل على الجواب رقم 200، وأن \(M(L)\) هو عدد قيم sqube المولدة تحته. توليد الأعداد الأولية بالغربال يكلف \(O(B\log\log B)\)، حيث \(B\) هو أكبر عدد صحيح يُغربَل. في النسخة التكيفية يكون \(B\) تقريبًا على مقياس \(\sqrt{L/8}\)، وفي النسخ ذات الحد الثابت يبقى ضمن مقياس الجذر التربيعي نفسه.
بناء قائمة المرشحين يكلف \(O(M(L))\) عملية حسابية قبل الترتيب، بينما يكلف الترتيب \(O(M(L)\log M(L))\). أما فحص السلسلة العشرية فهو خطي في عدد الخانات، ولذلك فهو رخيص نسبيًا.
المرحلة المكلفة هي شهادة prime-proof. إذا بقي بعد مرشح "200" عدد \(F(L)\) من المرشحين، وكان للمرشح \(x\) عدد خانات يساوي \(d(x)\)، فإن عدد اختبارات الأولية لا يتجاوز
$$\sum_{x\in F(L)} 9\,d(x).$$
في C++ يكون كل اختبار من هذه الاختبارات استدعاءً ثابت القواعد لاختبار Miller-Rabin، لذا فالكلفة العملية لكل استدعاء على الأعداد ذات 64 بت تكاد تكون ثابتة. أما في Python وJava فالقسمة التجريبية تملك كلفة أسوأ حالة قدرها \(O(\sqrt{x})\) لكل اختبار، لكن العدد الفعلي للمرشحين المفحوصين يبقى معقولًا لأن عائلة sqube نفسها متناثرة، ومرشح "200" يستبعد معظم القيم قبل الوصول إلى هذه المرحلة.
أما الذاكرة فتُستهلك على نحو \(O(M(L))\) لتخزين sqube وجدول الأعداد الأولية. ومصدر الفاعلية الحقيقي هنا بنيوي: الخوارزمية لا تفحص كل الأعداد حتى \(L\)، بل تقتصر على المجموعة الأصغر كثيرًا من الأعداد ذات الشكل \(p^2q^3\).