Detailed mathematical approach

Problem Summary

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.

Mathematical Approach

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.

Step 1: Restrict the Search Space to Prime Squares

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.

Step 2: Reverse the Decimal Expansion and Exclude Fixed Points

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.

Step 3: Characterize When the Reversal Is Also a Prime Square

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.

Step 4: Reversible Prime Squares Come in Distinct Pairs

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.

Step 5: Worked Example

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.

Step 6: Why an Expanding Prime Bound Is Enough

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}\).

How the Code Works

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.

Complexity Analysis

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.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=808
2. Sieve of Eratosthenes: Wikipedia — Sieve of Eratosthenes
3. Miller-Rabin primality test: Wikipedia — Miller-Rabin primality test
4. Integer square root: Wikipedia — Integer square root
5. Palindromic number: Wikipedia — Palindromic number