We seek numbers \(s\) with three simultaneous properties: \(s\) must be the square of a prime, \(s\) must not be palindromic in base 10, and the decimal reversal of \(s\) must again be the square of a prime. The task is to list these reversible prime squares in increasing order and sum the first \(50\) of them.
If \(s\) qualifies and \(t=\operatorname{rev}(s)\), then \(t\) is also a reversible prime square unless \(s=t\), which is exactly the palindromic case that must be excluded. The search therefore focuses on a very special subset of prime squares rather than on all integers.
Let
$$\mathcal{R}=\left\{p^2 : p\in\mathbb{P},\ p^2\ne \operatorname{rev}(p^2),\ \operatorname{rev}(p^2)=q^2,\ q\in\mathbb{P}\right\}.$$
The implementations search this set directly. The mathematics is simple but precise: restrict the search to prime roots, reverse the decimal digits, and certify that the reversed value is also a prime square.
Every admissible value has the form
$$s=p^2,\qquad p\in\mathbb{P}.$$
So there is no reason to test arbitrary integers. It is enough to enumerate primes \(p\) and examine their squares. Because the map \(p\mapsto p^2\) is strictly increasing for positive integers, scanning prime roots in increasing order automatically scans candidate squares in increasing order as well.
For a candidate square \(s\), define its decimal reversal by
$$r=\operatorname{rev}(s).$$
The problem requires a genuinely different reversed value, so palindromes are rejected immediately:
$$s\ne r.$$
This is more than a cosmetic filter. If \(s=r\), then the reversal gives back the same number instead of a distinct reversible partner. Also, for any prime \(p>5\), the square \(p^2\) ends in \(1\) or \(9\), so its reversal begins in \(1\) or \(9\); there is no ambiguity from leading zeros.
A positive integer is a prime square exactly when it is a perfect square and its positive square root is prime. Therefore \(s\) belongs to \(\mathcal{R}\) if and only if
$$s=p^2,\qquad s\ne \operatorname{rev}(s),\qquad \operatorname{rev}(s)=q^2,\qquad p,q\in\mathbb{P}.$$
So the test for a reversed value \(r\) is exact:
$$a=\left\lfloor\sqrt{r}\right\rfloor,\qquad a^2=r,\qquad a\in\mathbb{P}.$$
If either the square test fails or the primality test fails, the original square is discarded.
Suppose \(s=p^2\in\mathcal{R}\) and let \(t=\operatorname{rev}(s)=q^2\). Reversing again gives
$$\operatorname{rev}(t)=s.$$
Because palindromes are excluded, we have \(s\ne t\). Hence reversible prime squares typically appear as two-way pairs \((s,t)\). The algorithm does not need any special pairing logic: once it tests every prime square in increasing order, both members of a valid pair will be encountered naturally.
The smallest example comes from
$$13^2=169,\qquad \operatorname{rev}(169)=961=31^2.$$
Since both \(13\) and \(31\) are prime, \(169\) is valid. The reverse direction also works:
$$31^2=961,\qquad \operatorname{rev}(961)=169=13^2,$$
so \(961\) is valid as well.
Two quick counterexamples illustrate the other filters. First,
$$11^2=121,\qquad \operatorname{rev}(121)=121,$$
so \(121\) is rejected for being palindromic. Second,
$$17^2=289,\qquad \operatorname{rev}(289)=982,$$
and \(982\) is not a perfect square, so \(289\) is rejected.
The implementations generate primes up to a current bound \(B\), test every square \(p^2\) with \(p\le B\), and keep all valid values found in that pass. If fewer than \(50\) values have been collected, the bound is enlarged and the search is repeated. This works because the candidate squares are examined in strictly increasing order. Once a pass finds at least \(50\) reversible prime squares, the first \(50\) found are exactly the first \(50\) elements of \(\mathcal{R}\).
The C++, Python, and Java implementations all follow the same logical pipeline. They begin by constructing a prime sieve up to a current bound and then iterate through the primes in ascending order. Each prime is squared, and palindromic squares are discarded before any more expensive work is done.
For every remaining square, the implementation reverses its decimal digits, computes an exact integer square root of the reversed value, and checks whether the reversal is a perfect square. If it is, the square root is then tested for primality. The primality check uses deterministic Miller-Rabin after an initial screen by a short list of small primes, so the result is exact for the integer range under consideration.
Whenever the reversed value is confirmed to be a prime square, the original square is appended to the answer list. If the list reaches \(50\) entries, the implementations sum those values and return the total. Otherwise they increase the sieve bound and restart with a larger search range. The arithmetic details differ slightly by language, but the mathematical test is identical in all three implementations.
Let \(B\) be the current sieve bound on the prime root. Building the sieve costs \(O(B\log\log B)\) time and \(O(B)\) memory. The number of candidates tested is \(\pi(B)\), one for each prime up to \(B\). For each candidate, digit reversal and integer square root use \(O(\log B)\) digit work, while deterministic Miller-Rabin uses a fixed witness set, so in this setting the primality certification is effectively constant-time per candidate and more formally requires \(O(\log B)\) modular multiplications. In practice the sieve dominates the growth, with small extra work per prime root.
Gesucht sind Zahlen \(s\) mit drei gleichzeitigen Eigenschaften: \(s\) muss das Quadrat einer Primzahl sein, \(s\) darf in Dezimalschreibweise kein Palindrom sein, und die Ziffernumkehr von \(s\) muss wiederum das Quadrat einer Primzahl sein. Anschließend sollen diese reversiblen Primzahlquadrate der Größe nach sortiert und die ersten \(50\) addiert werden.
Wenn \(s\) zulässig ist und \(t=\operatorname{rev}(s)\) gilt, dann ist normalerweise auch \(t\) zulässig. Nur der Fall \(s=t\) ist ausgeschlossen, denn genau das ist ein Palindrom. Dadurch reduziert sich die Aufgabe auf eine kleine, stark strukturierte Teilmenge aller Primzahlquadrate.
Definiere
$$\mathcal{R}=\left\{p^2 : p\in\mathbb{P},\ p^2\ne \operatorname{rev}(p^2),\ \operatorname{rev}(p^2)=q^2,\ q\in\mathbb{P}\right\}.$$
Die Implementierungen durchsuchen diese Menge direkt. Die Mathematik dahinter ist geradlinig: Man betrachtet nur Primzahlwurzeln, kehrt die Dezimalziffern um und prüft exakt, ob der umgekehrte Wert ebenfalls ein Primzahlquadrat ist.
Jeder gültige Wert hat die Form
$$s=p^2,\qquad p\in\mathbb{P}.$$
Deshalb müssen keine beliebigen ganzen Zahlen getestet werden. Es genügt, Primzahlen \(p\) zu erzeugen und ihre Quadrate zu untersuchen. Da die Abbildung \(p\mapsto p^2\) für positive Zahlen streng monoton wächst, liefert die aufsteigende Enumeration der Primzahlen automatisch eine aufsteigende Enumeration der Kandidaten \(p^2\).
Für ein Kandidatenquadrat \(s\) setzen wir
$$r=\operatorname{rev}(s).$$
Gefordert ist ein wirklich anderer umgekehrter Wert, also werden Palindrome sofort ausgeschlossen:
$$s\ne r.$$
Das ist keine bloße Schönheitsbedingung. Wenn \(s=r\), entsteht kein reversibles Paar, sondern nur ein Fixpunkt der Umkehrung. Außerdem endet für jede Primzahl \(p>5\) das Quadrat \(p^2\) auf \(1\) oder \(9\); die Umkehrung beginnt daher mit \(1\) oder \(9\), sodass keine Mehrdeutigkeit durch führende Nullen entsteht.
Eine positive ganze Zahl ist genau dann ein Primzahlquadrat, wenn sie ein vollkommenes Quadrat ist und ihre positive Quadratwurzel prim ist. Daher gilt
$$s\in\mathcal{R}\Longleftrightarrow s=p^2,\ s\ne \operatorname{rev}(s),\ \operatorname{rev}(s)=q^2,\ p,q\in\mathbb{P}.$$
Für den umgekehrten Wert \(r\) ist die Prüfung also exakt:
$$a=\left\lfloor\sqrt{r}\right\rfloor,\qquad a^2=r,\qquad a\in\mathbb{P}.$$
Scheitert entweder der Quadrattest oder der Primzahltest, dann wird das ursprüngliche Quadrat verworfen.
Sei \(s=p^2\in\mathcal{R}\) und \(t=\operatorname{rev}(s)=q^2\). Dann gilt durch erneutes Umkehren
$$\operatorname{rev}(t)=s.$$
Da Palindrome ausgeschlossen sind, folgt \(s\ne t\). Reversible Primzahlquadrate erscheinen also typischerweise als echte Paare \((s,t)\). Die Suche benötigt dafür keine Sonderbehandlung: Wer jedes Primzahlquadrat einmal testet, findet beide Partner automatisch.
Das kleinste Beispiel ist
$$13^2=169,\qquad \operatorname{rev}(169)=961=31^2.$$
Weil sowohl \(13\) als auch \(31\) prim sind, ist \(169\) gültig. Auch die Rückrichtung funktioniert:
$$31^2=961,\qquad \operatorname{rev}(961)=169=13^2,$$
also ist auch \(961\) gültig.
Zwei Gegenbeispiele zeigen die anderen Filter. Erstens
$$11^2=121,\qquad \operatorname{rev}(121)=121,$$
also wird \(121\) als Palindrom verworfen. Zweitens
$$17^2=289,\qquad \operatorname{rev}(289)=982,$$
und \(982\) ist kein vollkommenes Quadrat, also fällt \(289\) ebenfalls heraus.
Die Implementierungen erzeugen Primzahlen bis zu einer aktuellen Grenze \(B\), testen alle Quadrate \(p^2\) mit \(p\le B\) und speichern alle in diesem Durchlauf gefundenen gültigen Werte. Wenn noch keine \(50\) Treffer vorliegen, wird die Grenze vergrößert und die Suche wiederholt. Das ist korrekt, weil die Kandidatenquadrate streng aufsteigend geprüft werden. Sobald ein Durchlauf mindestens \(50\) reversible Primzahlquadrate liefert, sind die ersten \(50\) Treffer genau die ersten \(50\) Elemente von \(\mathcal{R}\).
Die C++, Python- und Java-Implementierungen verwenden dieselbe logische Pipeline. Zunächst bauen sie ein Primzahlsieb bis zu einer aktuellen Grenze auf und durchlaufen anschließend die Primzahlen in aufsteigender Reihenfolge. Jede Primzahl wird quadriert; palindromische Quadrate werden sofort aussortiert, bevor weitere Arbeit investiert wird.
Für jedes verbleibende Quadrat werden die Dezimalziffern umgedreht, dann wird eine exakte ganzzahlige Quadratwurzel der Umkehrung berechnet und geprüft, ob die Umkehrung überhaupt ein Quadrat ist. Falls ja, wird die Wurzel auf Primzahl-Eigenschaft getestet. Dieser Test basiert auf deterministischem Miller-Rabin nach einer kurzen Vorprüfung mit kleinen Primzahlen und ist im relevanten Zahlenbereich exakt.
Sobald die Umkehrung als Primzahlquadrat bestätigt ist, wird das ursprüngliche Quadrat in die Ergebnisliste aufgenommen. Erreicht die Liste \(50\) Einträge, summieren die Implementierungen diese Werte und beenden die Suche. Andernfalls wird das Sieblimit erhöht und die gesamte Suche mit größerem Bereich wiederholt. Die Arithmetik ist je nach Sprache leicht verschieden, aber die mathematische Bedingung ist überall dieselbe.
Sei \(B\) die aktuelle Siebgrenze für die Primzahlwurzel. Der Aufbau des Siebs kostet \(O(B\log\log B)\) Zeit und \(O(B)\) Speicher. Getestet werden \(\pi(B)\) Kandidaten, also genau die Primzahlen bis \(B\). Pro Kandidat benötigen Ziffernumkehr und ganzzahlige Quadratwurzel \(O(\log B)\) Zifferoperationen. Der deterministische Miller-Rabin-Test verwendet eine feste Zeugenmenge, ist in diesem Anwendungsbereich also praktisch konstant pro Kandidat und formaler betrachtet \(O(\log B)\) modulare Multiplikationen. Dominant bleibt damit das Sieb, ergänzt um geringe Zusatzkosten pro Primzahlwurzel.
Aranan sayılar \(s\) için üç koşul birlikte sağlanır: \(s\) bir asal sayının karesi olmalıdır, onluk tabanda palindrom olmamalıdır ve \(s\)'nin rakamları ters çevrildiğinde elde edilen sayı da yine bir asal sayının karesi olmalıdır. Amaç, bu tersinir asal kareleri küçükten büyüğe sıralayıp ilk \(50\) tanesinin toplamını bulmaktır.
Eğer \(s\) uygunsa ve \(t=\operatorname{rev}(s)\) ise, palindrom durumu dışında \(t\) de uygundur. Yani problem bütün sayıları taramaktan çok, özel yapıda bir asal kare alt kümesini belirlemeye dönüşür.
Şunu tanımlayalım:
$$\mathcal{R}=\left\{p^2 : p\in\mathbb{P},\ p^2\ne \operatorname{rev}(p^2),\ \operatorname{rev}(p^2)=q^2,\ q\in\mathbb{P}\right\}.$$
Uygulamalar bu kümeyi doğrudan arar. Temel fikir nettir: yalnızca asal kökleri üret, karelerini incele, rakamları ters çevir ve ters çevrilmiş değerin de asal kare olup olmadığını kesin olarak doğrula.
Her geçerli değer şu biçimdedir:
$$s=p^2,\qquad p\in\mathbb{P}.$$
Bu yüzden rastgele tamsayıları test etmeye gerek yoktur. Asal sayıları artan sırayla üretmek ve karelerini incelemek yeterlidir. \(p\mapsto p^2\) dönüşümü pozitif sayılarda sıkı biçimde artan olduğundan, asal kökleri artan sırada gezmek aday kareleri de artan sırada gezmek demektir.
Bir aday kare \(s\) için
$$r=\operatorname{rev}(s)$$
tanımını yapalım. Problem, ters çevrilmiş değerin farklı bir sayı olmasını ister; dolayısıyla palindromlar baştan reddedilir:
$$s\ne r.$$
Bu sadece estetik bir koşul değildir. Eğer \(s=r\) ise elimizde tersinir bir çift değil, ters çevirme işleminin sabit noktası vardır. Ayrıca \(p>5\) olan her asal için \(p^2\) sayısı \(1\) veya \(9\) ile biter; dolayısıyla ters çevrilmiş değer de \(1\) veya \(9\) ile başlar ve baştaki sıfırların düşmesi gibi bir belirsizlik oluşmaz.
Pozitif bir tamsayı, ancak ve ancak tam karedir ve pozitif karekökü asaldırsa bir asal karedir. Bu yüzden
$$s\in\mathcal{R}\Longleftrightarrow s=p^2,\ s\ne \operatorname{rev}(s),\ \operatorname{rev}(s)=q^2,\ p,q\in\mathbb{P}.$$
Ters çevrilmiş değer \(r\) için test tam olarak şöyledir:
$$a=\left\lfloor\sqrt{r}\right\rfloor,\qquad a^2=r,\qquad a\in\mathbb{P}.$$
Tam kare kontrolü başarısız olursa ya da karekök asal çıkmazsa, özgün kare elenir.
\(s=p^2\in\mathcal{R}\) olsun ve \(t=\operatorname{rev}(s)=q^2\) yazalım. Bir kez daha ters çevirince
$$\operatorname{rev}(t)=s$$
elde edilir. Palindromlar dışlandığı için \(s\ne t\) olur. Yani geçerli örnekler çoğu zaman iki yönlü çiftler olarak ortaya çıkar. Algoritmanın bunun için ayrı bir eşleştirme mantığı kurmasına gerek yoktur; her asal kare bir kez test edildiğinde çiftin iki üyesi de doğal olarak bulunur.
En küçük örnek şudur:
$$13^2=169,\qquad \operatorname{rev}(169)=961=31^2.$$
\(13\) ve \(31\) asal olduğu için \(169\) geçerlidir. Ters yönde de aynı durum vardır:
$$31^2=961,\qquad \operatorname{rev}(961)=169=13^2,$$
dolayısıyla \(961\) de geçerlidir.
Diğer filtreleri görmek için iki karşı örnek verelim. Birincisi,
$$11^2=121,\qquad \operatorname{rev}(121)=121,$$
yani \(121\) palindrom olduğu için reddedilir. İkincisi,
$$17^2=289,\qquad \operatorname{rev}(289)=982,$$
ve \(982\) tam kare değildir; bu yüzden \(289\) da reddedilir.
Uygulamalar önce güncel bir sınır \(B\)'ye kadar asal üretir, \(p\le B\) için bütün \(p^2\) değerlerini test eder ve o turda bulduğu tüm geçerli sayıları kaydeder. Eğer henüz \(50\) değer bulunmadıysa sınır büyütülür ve arama yeniden yapılır. Bu yöntem doğrudur; çünkü aday kareler sıkı biçimde artan sırada incelenir. Bir tur en az \(50\) tersinir asal kare ürettiğinde, bulunan ilk \(50\) değer tam olarak \(\mathcal{R}\) kümesinin ilk \(50\) elemanıdır.
C++, Python ve Java uygulamaları aynı mantıksal boru hattını izler. Önce mevcut sınır için bir asal eleği kurulur ve asallar artan sırada dolaşılır. Her asalın karesi alınır; palindrom kareler daha pahalı adımlara geçmeden hemen atılır.
Kalan her kare için rakamlar ters çevrilir, ters çevrilmiş değerin tam sayı karekökü hesaplanır ve bu değerin gerçekten tam kare olup olmadığı doğrulanır. Eğer doğrulanırsa karekökün asal olup olmadığı sınanır. Asallık testi, küçük asal bölenlere karşı kısa bir ön elemeden sonra deterministik Miller-Rabin kullanır; dolayısıyla ilgili sayı aralığında sonuç kesindir.
Ters çevrilmiş değer bir asal kare olarak onaylandığında özgün kare sonuç listesine eklenir. Liste \(50\) elemana ulaşırsa bu değerlerin toplamı hesaplanır ve işlem biter. Aksi halde elek sınırı artırılır ve daha geniş aralıkta arama yeniden başlatılır. Diller arasındaki aritmetik ayrıntılar biraz değişse de matematiksel test aynıdır.
\(B\), asal kök için kullanılan güncel elek sınırı olsun. Eleğin kurulması \(O(B\log\log B)\) zaman ve \(O(B)\) bellek gerektirir. Test edilen aday sayısı \(\pi(B)\)'dir; yani \(B\)'ye kadar olan asal sayılar kadardır. Her aday için rakam tersleme ve tamsayı karekök alma işlemleri \(O(\log B)\) basamak işi yapar. Deterministik Miller-Rabin sabit sayıda tanık kullandığından bu bağlamda aday başına pratikte sabit zamana yakındır; daha resmi olarak \(O(\log B)\) modüler çarpma ve karesel yükseltme içerir. Sonuçta baskın maliyet elektir; her asal kök başına ek iş küçüktür.
Buscamos números \(s\) que satisfacen tres condiciones a la vez: \(s\) debe ser el cuadrado de un número primo, \(s\) no debe ser palíndromo en base \(10\), y la inversión decimal de \(s\) también debe ser el cuadrado de un primo. Luego hay que ordenar estos cuadrados primos reversibles de menor a mayor y sumar los primeros \(50\).
Si \(s\) es válido y \(t=\operatorname{rev}(s)\), entonces normalmente \(t\) también es válido. El único caso excluido es \(s=t\), que es precisamente la situación palindrómica. Por eso el problema no consiste en explorar todos los enteros, sino una subfamilia muy rígida de cuadrados de primos.
Definamos
$$\mathcal{R}=\left\{p^2 : p\in\mathbb{P},\ p^2\ne \operatorname{rev}(p^2),\ \operatorname{rev}(p^2)=q^2,\ q\in\mathbb{P}\right\}.$$
Las implementaciones buscan directamente este conjunto. La idea matemática es simple: generar raíces primas, elevarlas al cuadrado, invertir las cifras y certificar que el valor invertido vuelve a ser un cuadrado de primo.
Todo valor admisible tiene la forma
$$s=p^2,\qquad p\in\mathbb{P}.$$
Por tanto, no hace falta probar enteros arbitrarios. Basta enumerar primos \(p\) y estudiar sus cuadrados. Como la aplicación \(p\mapsto p^2\) es estrictamente creciente para enteros positivos, recorrer los primos en orden creciente produce automáticamente los candidatos \(p^2\) en orden creciente.
Para un cuadrado candidato \(s\), definimos
$$r=\operatorname{rev}(s).$$
El problema exige un compañero distinto, así que los palíndromos se descartan de inmediato:
$$s\ne r.$$
Esto no es un detalle superficial. Si \(s=r\), la inversión no crea un par reversible, sino que deja el mismo número. Además, para cualquier primo \(p>5\), el cuadrado \(p^2\) termina en \(1\) o en \(9\); por tanto, su inversión empieza en \(1\) o en \(9\), y no aparece ninguna ambigüedad por ceros iniciales.
Un entero positivo es un cuadrado de primo exactamente cuando es un cuadrado perfecto y su raíz cuadrada positiva es prima. En consecuencia,
$$s\in\mathcal{R}\Longleftrightarrow s=p^2,\ s\ne \operatorname{rev}(s),\ \operatorname{rev}(s)=q^2,\ p,q\in\mathbb{P}.$$
La verificación para el valor invertido \(r\) es entonces exacta:
$$a=\left\lfloor\sqrt{r}\right\rfloor,\qquad a^2=r,\qquad a\in\mathbb{P}.$$
Si falla la comprobación de cuadrado perfecto o falla la primalidad de la raíz, el cuadrado original se rechaza.
Supongamos \(s=p^2\in\mathcal{R}\) y \(t=\operatorname{rev}(s)=q^2\). Al invertir de nuevo obtenemos
$$\operatorname{rev}(t)=s.$$
Como los palíndromos están excluidos, se tiene \(s\ne t\). Por eso los ejemplos válidos suelen aparecer en pares bidireccionales \((s,t)\). El algoritmo no necesita una gestión especial de parejas: al probar cada cuadrado de primo una sola vez, los dos miembros del par aparecerán de forma natural.
El ejemplo más pequeño es
$$13^2=169,\qquad \operatorname{rev}(169)=961=31^2.$$
Como \(13\) y \(31\) son primos, \(169\) es válido. La dirección inversa también funciona:
$$31^2=961,\qquad \operatorname{rev}(961)=169=13^2,$$
así que \(961\) también es válido.
Dos contraejemplos muestran los otros filtros. Primero,
$$11^2=121,\qquad \operatorname{rev}(121)=121,$$
de modo que \(121\) se rechaza por ser palíndromo. Segundo,
$$17^2=289,\qquad \operatorname{rev}(289)=982,$$
y \(982\) no es un cuadrado perfecto, así que \(289\) también se rechaza.
Las implementaciones generan primos hasta un límite actual \(B\), prueban todos los cuadrados \(p^2\) con \(p\le B\) y guardan los valores válidos encontrados en esa pasada. Si todavía no hay \(50\) resultados, el límite se aumenta y la búsqueda se repite. Esto es correcto porque los cuadrados candidatos se examinan en orden estrictamente creciente. En cuanto una pasada encuentra al menos \(50\) cuadrados primos reversibles, los primeros \(50\) encontrados son exactamente los primeros \(50\) elementos de \(\mathcal{R}\).
Las implementaciones en C++, Python y Java siguen la misma secuencia lógica. Primero construyen una criba de primos hasta un límite actual y luego recorren los primos en orden ascendente. Cada primo se eleva al cuadrado, y los cuadrados palindrómicos se descartan antes de hacer trabajo adicional.
Para cada cuadrado restante, la implementación invierte sus cifras decimales, calcula una raíz cuadrada entera exacta del valor invertido y comprueba si esa inversión es realmente un cuadrado perfecto. Si lo es, la raíz se somete a una prueba de primalidad. Esa prueba usa Miller-Rabin determinista después de una criba previa con algunos primos pequeños, así que el resultado es exacto en el rango de enteros utilizado.
Cuando el valor invertido queda certificado como cuadrado de primo, el cuadrado original se añade a la lista de respuestas. Si la lista alcanza \(50\) elementos, las implementaciones suman esos valores y terminan. En caso contrario, duplican el límite de búsqueda y reinician el proceso. Los detalles aritméticos cambian ligeramente entre lenguajes, pero la condición matemática es la misma en los tres casos.
Sea \(B\) el límite actual de la criba para la raíz prima. Construir la criba cuesta \(O(B\log\log B)\) tiempo y \(O(B)\) memoria. El número de candidatos comprobados es \(\pi(B)\), uno por cada primo hasta \(B\). Para cada candidato, invertir dígitos y calcular la raíz cuadrada entera requiere \(O(\log B)\) trabajo de dígitos. La certificación de primalidad mediante Miller-Rabin usa un conjunto fijo de testigos; en esta aplicación es efectivamente constante por candidato y, de manera más formal, requiere \(O(\log B)\) multiplicaciones modulares. En la práctica domina la criba, con un coste adicional pequeño por raíz prima.
我们要找的数 \(s\) 同时满足三个条件：\(s\) 必须是某个素数的平方，\(s\) 的十进制表示不能是回文，并且把 \(s\) 的十进制数字倒过来以后得到的新数也必须是某个素数的平方。题目的目标是按从小到大的顺序列出这样的可逆素数平方，并求出前 \(50\) 个的和。
如果某个 \(s\) 合格，并且记 \(t=\operatorname{rev}(s)\)，那么除去 \(s=t\) 的回文情形之外，\(t\) 也会合格。因此问题并不是在所有整数中盲目搜索，而是在素数平方里寻找一种很特殊、很稀疏的结构。
定义集合
$$\mathcal{R}=\left\{p^2 : p\in\mathbb{P},\ p^2\ne \operatorname{rev}(p^2),\ \operatorname{rev}(p^2)=q^2,\ q\in\mathbb{P}\right\}.$$
实现的任务就是直接搜索这个集合。数学上的思路可以拆成几步：先只枚举素数根，再看平方值的数字反转，最后严格验证反转后的结果是否仍然是素数平方。
任何合法值都必须写成
$$s=p^2,\qquad p\in\mathbb{P}.$$
因此根本没有必要检查任意整数。只要按升序生成素数 \(p\)，再考察对应的平方 \(p^2\) 即可。因为映射 \(p\mapsto p^2\) 在正整数上严格递增，所以按升序扫描素数根，也就等价于按升序扫描候选平方。
对候选平方 \(s\)，定义它的十进制反转为
$$r=\operatorname{rev}(s).$$
题目要求反转后得到的是一个不同的值，所以回文数必须立刻剔除：
$$s\ne r.$$
这不是表面上的小条件。如果 \(s=r\)，那么它并没有形成一个“互相反转”的不同配对，只是反转操作的固定点。另外，对任何 \(p>5\) 的素数来说，\(p^2\) 的个位只能是 \(1\) 或 \(9\)，所以反转后的数也会以 \(1\) 或 \(9\) 开头，不会出现因为前导零被消去而改变位数含义的情况。
一个正整数是素数平方，当且仅当它是完全平方数，并且它的正平方根本身是素数。因此有
$$s\in\mathcal{R}\Longleftrightarrow s=p^2,\ s\ne \operatorname{rev}(s),\ \operatorname{rev}(s)=q^2,\ p,q\in\mathbb{P}.$$
所以对反转值 \(r\) 的判定可以写成非常直接的形式：
$$a=\left\lfloor\sqrt{r}\right\rfloor,\qquad a^2=r,\qquad a\in\mathbb{P}.$$
如果 \(r\) 不是完全平方数，或者虽然是平方但平方根不是素数，那么原来的 \(s\) 都要被拒绝。
假设 \(s=p^2\in\mathcal{R}\)，并且 \(t=\operatorname{rev}(s)=q^2\)。再反转一次就得到
$$\operatorname{rev}(t)=s.$$
由于回文数已经被排除，所以必有 \(s\ne t\)。这说明可逆素数平方通常以真正的二元配对 \((s,t)\) 出现。算法不需要显式地“配对管理”；只要把每个素数平方都检查一遍，配对中的两个成员都会在各自出现时被自然识别出来。
最小的例子来自
$$13^2=169,\qquad \operatorname{rev}(169)=961=31^2.$$
因为 \(13\) 和 \(31\) 都是素数，所以 \(169\) 合格。反过来同样成立：
$$31^2=961,\qquad \operatorname{rev}(961)=169=13^2,$$
因此 \(961\) 也合格。
再看两个反例。第一，
$$11^2=121,\qquad \operatorname{rev}(121)=121,$$
所以 \(121\) 因为是回文而被排除。第二，
$$17^2=289,\qquad \operatorname{rev}(289)=982,$$
而 \(982\) 不是完全平方数，所以 \(289\) 也不合格。
实现会先取一个当前上界 \(B\)，生成所有不超过 \(B\) 的素数，并测试全部 \(p\le B\) 对应的平方 \(p^2\)。如果这一轮找到的可逆素数平方还不到 \(50\) 个，就把上界放大后重新执行。这样做是正确的，因为候选平方是按严格递增的顺序被检查的。一旦某一轮已经找到了至少 \(50\) 个可逆素数平方，那么该轮得到的前 \(50\) 个值，就必然是集合 \(\mathcal{R}\) 中按大小排列的前 \(50\) 个元素。
C++、Python 和 Java 实现遵循完全相同的逻辑流程。它们先在当前上界内建立素数筛，然后按升序遍历所有素数。每遇到一个素数，就先求平方；如果这个平方本身是回文，就立即跳过，从而避免后续更昂贵的检查。
对于其余平方，程序先反转十进制数字，再计算反转结果的精确整数平方根，并检查该反转值是否真的是完全平方数。如果是，再对这个平方根做素性判定。素性判定在先排除少量小素数因子之后，使用固定见证集合的确定性 Miller-Rabin，因此在这里涉及的整数范围内结论是精确的。
一旦反转值被确认是素数平方，原来的平方就被加入答案列表。如果列表已经达到 \(50\) 项，实现就把这 \(50\) 个数求和并返回；否则就扩大筛法上界，重新在更大的范围内搜索。不同语言在底层整数运算上略有差异，但数学判定条件完全一致。
设当前用于素数根的筛法上界为 \(B\)。建立筛法需要 \(O(B\log\log B)\) 时间和 \(O(B)\) 空间。被检查的候选数量是 \(\pi(B)\)，也就是不超过 \(B\) 的素数个数。对每个候选来说，数字反转和整数平方根需要 \(O(\log B)\) 级别的位数处理；而 Miller-Rabin 使用固定见证集合，在本题的实现范围内可以视为候选级别的常数时间，更形式化地说则需要 \(O(\log B)\) 次模乘与模平方。总体上，主导成本仍然是筛法，而每个素数根附带的额外检查成本较小。
Нужно найти такие числа \(s\), которые одновременно обладают тремя свойствами: \(s\) является квадратом простого числа, десятичная запись \(s\) не является палиндромом, а число, полученное обращением десятичных цифр \(s\), снова является квадратом простого числа. После этого требуется упорядочить такие обратимые квадраты простых по возрастанию и просуммировать первые \(50\).
Если некоторое \(s\) подходит и \(t=\operatorname{rev}(s)\), то, кроме палиндромного случая \(s=t\), обычно подходит и \(t\). Поэтому поиск идет не по всем натуральным числам, а по очень специальному подмножеству квадратов простых.
Обозначим
$$\mathcal{R}=\left\{p^2 : p\in\mathbb{P},\ p^2\ne \operatorname{rev}(p^2),\ \operatorname{rev}(p^2)=q^2,\ q\in\mathbb{P}\right\}.$$
Именно это множество и ищут реализации. Математическая схема проста: рассматривать только простые корни, обращать десятичные цифры квадрата и строго проверять, что обращенное число тоже является квадратом простого.
Любое допустимое значение имеет вид
$$s=p^2,\qquad p\in\mathbb{P}.$$
Следовательно, нет смысла тестировать произвольные целые числа. Достаточно перечислять простые \(p\) и анализировать их квадраты. Поскольку отображение \(p\mapsto p^2\) строго возрастает на положительных числах, перечисление простых по возрастанию автоматически перечисляет и кандидаты \(p^2\) по возрастанию.
Для кандидата \(s\) положим
$$r=\operatorname{rev}(s).$$
По условию требуется именно другой обратный партнер, поэтому палиндромы сразу отбрасываются:
$$s\ne r.$$
Это не просто косметическое ограничение. Если \(s=r\), то обращение не создает новую пару, а возвращает то же самое число. Кроме того, для любого простого \(p>5\) квадрат \(p^2\) оканчивается на \(1\) или \(9\), а значит обращенное число начинается с \(1\) или \(9\), так что не возникает неоднозначности из-за исчезающих ведущих нулей.
Положительное число является квадратом простого тогда и только тогда, когда оно является полным квадратом, а его положительный квадратный корень прост. Поэтому
$$s\in\mathcal{R}\Longleftrightarrow s=p^2,\ s\ne \operatorname{rev}(s),\ \operatorname{rev}(s)=q^2,\ p,q\in\mathbb{P}.$$
Проверка для обращенного значения \(r\) имеет точный вид
$$a=\left\lfloor\sqrt{r}\right\rfloor,\qquad a^2=r,\qquad a\in\mathbb{P}.$$
Если число \(r\) не является полным квадратом или его корень составной, исходный квадрат отвергается.
Пусть \(s=p^2\in\mathcal{R}\) и \(t=\operatorname{rev}(s)=q^2\). Тогда при повторном обращении получаем
$$\operatorname{rev}(t)=s.$$
Так как палиндромы исключены, имеем \(s\ne t\). Значит, такие числа обычно возникают как настоящие пары \((s,t)\). Алгоритму не нужна отдельная логика для связывания пар: если проверить каждый квадрат простого один раз, оба элемента пары будут обнаружены естественным образом.
Минимальный пример:
$$13^2=169,\qquad \operatorname{rev}(169)=961=31^2.$$
Так как \(13\) и \(31\) простые, число \(169\) подходит. В обратную сторону также верно:
$$31^2=961,\qquad \operatorname{rev}(961)=169=13^2,$$
поэтому \(961\) тоже подходит.
Два контрпримера показывают остальные фильтры. Во-первых,
$$11^2=121,\qquad \operatorname{rev}(121)=121,$$
поэтому \(121\) отбрасывается как палиндром. Во-вторых,
$$17^2=289,\qquad \operatorname{rev}(289)=982,$$
а \(982\) не является полным квадратом, значит \(289\) тоже не подходит.
Реализации генерируют простые числа до текущей границы \(B\), проверяют все квадраты \(p^2\) при \(p\le B\) и сохраняют все подходящие значения, найденные на этом проходе. Если найдено меньше \(50\) элементов, граница увеличивается, и поиск повторяется. Это корректно, потому что кандидаты \(p^2\) рассматриваются в строго возрастающем порядке. Как только очередной проход уже нашел не менее \(50\) обратимых квадратов простых, первые \(50\) найденных значений и есть первые \(50\) элементов множества \(\mathcal{R}\).
Реализации на C++, Python и Java используют одну и ту же логическую схему. Сначала строится решето простых чисел до текущей границы, затем простые перебираются по возрастанию. Каждый простой корень возводится в квадрат, а палиндромные квадраты отбрасываются сразу, до более дорогих проверок.
Для каждого оставшегося квадрата обращаются десятичные цифры, затем вычисляется точный целочисленный квадратный корень обращенного значения и проверяется, является ли это значение полным квадратом. Если да, то квадратный корень тестируется на простоту. Для этого после быстрой проверки делимости на несколько малых простых применяется детерминированный тест Миллера-Рабина, поэтому результат точен на рассматриваемом диапазоне чисел.
Если обращенное значение подтверждается как квадрат простого, исходный квадрат добавляется в список ответа. Когда список достигает длины \(50\), реализации суммируют эти значения и завершаются. Иначе граница решета увеличивается, и поиск запускается заново на более широком диапазоне. Низкоуровневая арифметика немного различается между языками, но математический критерий совпадает полностью.
Пусть \(B\) обозначает текущую границу решета по простому корню. Построение решета занимает \(O(B\log\log B)\) времени и \(O(B)\) памяти. Число проверяемых кандидатов равно \(\pi(B)\), то есть числу простых до \(B\). Для каждого кандидата обращение цифр и вычисление целочисленного квадратного корня требуют \(O(\log B)\) операций над цифрами. Детерминированный Миллер-Рабин использует фиксированный набор свидетелей, поэтому в данной постановке он практически постоянный на один кандидат, а формально требует \(O(\log B)\) модульных умножений. В итоге главным источником роста остается решето, а дополнительная работа на каждый простой корень невелика.
نبحث عن أعداد \(s\) تحقق ثلاث خصائص معًا: أن يكون \(s\) مربعًا لعدد أولي، وألا يكون متناظرًا عشريًا، وأن يكون العدد الناتج من عكس أرقامه العشرية أيضًا مربعًا لعدد أولي. بعد ذلك نرتب هذه المربعات الأولية القابلة للعكس تصاعديًا ونجمع أول \(50\) منها.
إذا كانت قيمة ما \(s\) صالحة وكتبنا \(t=\operatorname{rev}(s)\)، فعادةً تكون \(t\) صالحة أيضًا، ما دام \(s\ne t\). أمّا الحالة المستبعدة فهي حالة التناظر نفسها. لذلك فالمسألة لا تبحث في جميع الأعداد الصحيحة، بل في مجموعة فرعية دقيقة جدًا من مربعات الأعداد الأولية.
لنعرّف المجموعة
$$\mathcal{R}=\left\{p^2 : p\in\mathbb{P},\ p^2\ne \operatorname{rev}(p^2),\ \operatorname{rev}(p^2)=q^2,\ q\in\mathbb{P}\right\}.$$
هذا هو الهدف الذي تبحث عنه التطبيقات مباشرة. الفكرة الرياضية الأساسية هي: نولّد الجذور الأولية فقط، ثم ننظر إلى مربعاتها، ثم نعكس الأرقام العشرية، ثم نتحقق بدقة من أن القيمة المعكوسة ما زالت مربعًا لعدد أولي.
كل قيمة مقبولة يجب أن تكون من الشكل
$$s=p^2,\qquad p\in\mathbb{P}.$$
لذلك لا حاجة لاختبار أعداد صحيحة عامة. يكفي تعداد الأعداد الأولية \(p\) ودراسة المربعات \(p^2\). وبما أن الدالة \(p\mapsto p^2\) متزايدة بصرامة على الأعداد الموجبة، فإن المرور على الجذور الأولية بترتيب تصاعدي يعطينا المرشحات \(p^2\) بالترتيب التصاعدي نفسه.
لكل مربع مرشح \(s\) نعرّف
$$r=\operatorname{rev}(s).$$
المطلوب في المسألة هو وجود شريك مختلف بعد العكس، ولذلك تُستبعد القيم المتناظرة فورًا:
$$s\ne r.$$
وهذا ليس شرطًا شكليًا فقط. فإذا كان \(s=r\)، فإن عملية العكس لا تنتج زوجًا مختلفًا بل تعيد العدد نفسه. كذلك، لكل عدد أولي \(p>5\)، ينتهي \(p^2\) بالرقم \(1\) أو \(9\)، ومن ثم يبدأ العدد المعكوس بالرقم \(1\) أو \(9\)، فلا تظهر مشكلة أصفار بادئة تختفي عند القراءة العادية.
العدد الصحيح الموجب يكون مربعًا أوليًا إذا وفقط إذا كان مربعًا كاملًا وكان جذره الموجب عددًا أوليًا. لذلك
$$s\in\mathcal{R}\Longleftrightarrow s=p^2,\ s\ne \operatorname{rev}(s),\ \operatorname{rev}(s)=q^2,\ p,q\in\mathbb{P}.$$
ومن ثم فإن اختبار القيمة المعكوسة \(r\) يكون بالصيغة الدقيقة التالية:
$$a=\left\lfloor\sqrt{r}\right\rfloor,\qquad a^2=r,\qquad a\in\mathbb{P}.$$
إذا فشل اختبار المربع الكامل أو فشل اختبار أولية الجذر، فإن المربع الأصلي يُرفض.
افترض أن \(s=p^2\in\mathcal{R}\) وأن \(t=\operatorname{rev}(s)=q^2\). عند عكس \(t\) مرة أخرى نحصل على
$$\operatorname{rev}(t)=s.$$
وبما أن الأعداد المتناظرة مستبعدة، فلدينا \(s\ne t\). هذا يعني أن الأمثلة الصحيحة تظهر غالبًا في أزواج ثنائية الاتجاه \((s,t)\). ولا يحتاج البرنامج إلى منطق خاص لإدارة الأزواج؛ فمجرد فحص كل مربع أولي مرة واحدة كافٍ لاكتشاف طرفي الزوج كلٌّ في موضعه الطبيعي.
أصغر مثال هو
$$13^2=169,\qquad \operatorname{rev}(169)=961=31^2.$$
وبما أن \(13\) و\(31\) عددان أوليان، فإن \(169\) قيمة صالحة. والاتجاه العكسي صحيح أيضًا:
$$31^2=961,\qquad \operatorname{rev}(961)=169=13^2,$$
ولذلك تكون \(961\) صالحة كذلك.
ولإظهار المرشحات المستبعدة، خذ المثالين الآتيين. أولًا،
$$11^2=121,\qquad \operatorname{rev}(121)=121,$$
فتُرفض \(121\) لأنها متناظرة. ثانيًا،
$$17^2=289,\qquad \operatorname{rev}(289)=982,$$
والعدد \(982\) ليس مربعًا كاملًا، ولذلك تُرفض \(289\) أيضًا.
تولّد التطبيقات الأعداد الأولية حتى حدّ حالي \(B\)، ثم تختبر كل القيم \(p^2\) حيث \(p\le B\)، وتحفظ كل القيم الصحيحة التي تظهر في تلك الجولة. إذا كان عدد النتائج أقل من \(50\)، يُزاد الحد وتُعاد العملية من جديد. هذا صحيح لأن المرشحات تُفحص بترتيب تصاعدي صارم. وبمجرد أن تعثر جولة ما على \(50\) مربعًا أوليًا قابلًا للعكس أو أكثر، فإن أول \(50\) قيمة تم العثور عليها تكون بالضبط أول \(50\) عنصرًا في المجموعة \(\mathcal{R}\).
تتبع تطبيقات C++ وPython وJava المسار المنطقي نفسه. فهي تبدأ ببناء غربال للأعداد الأولية حتى حدّ حالي، ثم تمر على الأعداد الأولية بترتيب تصاعدي. كل عدد أولي يُربّع أولًا، وتُستبعد المربعات المتناظرة فورًا قبل أي خطوات أغلى كلفة.
بعد ذلك تُعكس الأرقام العشرية لكل مربع باقٍ، ثم يُحسب الجذر التربيعي الصحيح للقيمة المعكوسة بدقة، ويُتحقق إن كانت تلك القيمة مربعًا كاملًا فعلًا. وإذا كانت كذلك، يُختبر الجذر نفسه من حيث الأولية. ويستخدم هذا الاختبار نسخة حتمية من Miller-Rabin بعد فحص أولي صغير بقواسم أولية صغيرة، لذا تكون النتيجة دقيقة ضمن مجال الأعداد المعني.
كلما تأكدت الشيفرة من أن القيمة المعكوسة مربع أولي، تُضاف القيمة الأصلية إلى قائمة الإجابة. وإذا وصلت القائمة إلى \(50\) عنصرًا، تجمع التطبيقات هذه العناصر وتُنهي التنفيذ. وإن لم يحدث ذلك، فإنها توسّع حدّ الغربال وتعيد البحث على مجال أكبر. تختلف تفاصيل الحساب قليلًا بين اللغات، لكن الشرط الرياضي نفسه يبقى دون تغيير.
ليكن \(B\) هو الحد الحالي للغربال على الجذر الأولي. بناء الغربال يحتاج إلى زمن \(O(B\log\log B)\) وذاكرة \(O(B)\). وعدد المرشحات المختبرة هو \(\pi(B)\)، أي عدد الأعداد الأولية حتى \(B\). ولكل مرشح، يتطلب عكس الأرقام وحساب الجذر التربيعي الصحيح عملًا من رتبة \(O(\log B)\) بالنسبة لعدد الخانات. أما اختبار Miller-Rabin الحتمي فيستخدم مجموعة ثابتة من الشواهد، ولذلك يكون عمليًا شبه ثابت لكل مرشح في هذا السياق، وصوريًا يحتاج إلى \(O(\log B)\) ضربات معيارية. وبذلك تبقى كلفة الغربال هي المسيطرة، مع كلفة إضافية صغيرة لكل جذر أولي.