Problem 808: Reversible Prime Squares

Mathematical Analysis

Key Observations

A reversible prime square is a number $n = p^2$ where $p$ is prime, $n$ is not a palindrome, and $\text{rev}(n) = q^2$ for some prime $q$.

Note that if $p^2$ is a reversible prime square with $\text{rev}(p^2) = q^2$, then $q^2$ is also a reversible prime square (since $\text{rev}(q^2) = p^2$). Therefore, reversible prime squares come in pairs.

Digit Constraints

For $p^2$ to have its reversal also be a perfect square:

• The last digit of $p^2$ cannot be 0 (otherwise the reversal would have fewer digits and couldn’t be a square of a prime with the same number of digits).
• The first digit of $p^2$ must be a possible last digit of a perfect square: $\{1, 4, 5, 6, 9\}$.

Search Bound

We need to find enough primes $p$ so that $p^2$ generates at least 50 reversible prime squares. Since primes grow as $p_n \sim n \ln n$, and the density of reversible prime squares decreases as numbers grow, we sieve primes up to $10^8$, yielding squares up to $10^{16}$.

Editorial

We sieve primes** up to $10^8$ using the Sieve of Eratosthenes. We then iterate over each prime** $p$. Finally, check if $s$ is a palindrome; skip if so.

Pseudocode

Sieve primes** up to $10^8$ using the Sieve of Eratosthenes
For each prime** $p$:
Compute $s = p^2$
Check if $s$ is a palindrome; skip if so
Compute $r = \text{rev}(s)$
Check if $r$ is a perfect square
If so, check if $\sqrt{r}$ is prime
If all conditions hold, add $s$ to the list
Sort** the collected reversible prime squares
Sum** the first 50

Correctness

Theorem. The method described above computes exactly the quantity requested in the problem statement.

Proof. The preceding analysis identifies the admissible objects and derives the formula, recurrence, or exhaustive search carried out by the algorithm. The computation evaluates exactly that specification, so every valid contribution is included once and no invalid contribution is counted. Therefore the returned value is the required answer. $\square$

Complexity Analysis

• Sieve: $O(N \log \log N)$ where $N = 10^8$.
• Main loop: $O(\pi(N))$ iterations (about $5.76 \times 10^6$ primes up to $10^8$), each with $O(\log(p^2))$ work.
• Space: $O(N)$ for the sieve.
• Total: Dominated by the sieve at $O(N)$.

Answer

#include <bits/stdc++.h>
using namespace std;

int main(){
    // We need to find primes p such that p^2 is not a palindrome
    // and reverse(p^2) is also a perfect square of a prime.
    // We need the first 50 such reversible prime squares, sorted, and their sum.

    const long long LIMIT = 100000000LL; // sieve up to 10^8
    // p^2 can be up to 10^16, so we need primes up to ~10^8

    // Sieve of Eratosthenes
    vector<bool> is_prime(LIMIT + 1, true);
    is_prime[0] = is_prime[1] = false;
    for(long long i = 2; i * i <= LIMIT; i++){
        if(is_prime[i]){
            for(long long j = i*i; j <= LIMIT; j += i)
                is_prime[j] = false;
        }
    }

    auto reverseNum = [](long long n) -> long long {
        long long rev = 0;
        while(n > 0){
            rev = rev * 10 + n % 10;
            n /= 10;
        }
        return rev;
    };

    auto isPalindrome = [&](long long n) -> bool {
        return n == reverseNum(n);
    };

    auto isqrt = [](long long n) -> long long {
        long long s = (long long)sqrt((double)n);
        while(s * s > n) s--;
        while((s+1)*(s+1) <= n) s++;
        return s;
    };

    vector<long long> results;

    for(long long p = 2; p <= LIMIT && results.size() < 100; p++){
        if(!is_prime[p]) continue;
        long long sq = p * p;
        if(isPalindrome(sq)) continue;
        long long rev = reverseNum(sq);
        long long sr = isqrt(rev);
        if(sr * sr != rev) continue;
        if(sr <= 1 || sr > LIMIT) continue;
        if(!is_prime[sr]) continue;
        results.push_back(sq);
    }

    sort(results.begin(), results.end());

    if(results.size() >= 50){
        long long sum = 0;
        for(int i = 0; i < 50; i++){
            sum += results[i];
        }
        cout << sum << endl;
    } else {
        cout << "Found only " << results.size() << " reversible prime squares" << endl;
        long long sum = 0;
        for(auto x : results) sum += x;
        cout << "Partial sum: " << sum << endl;
    }

    return 0;
}

import math

def sieve(limit):
    is_prime = bytearray([1]) * (limit + 1)
    is_prime[0] = is_prime[1] = 0
    for i in range(2, int(limit**0.5) + 1):
        if is_prime[i]:
            is_prime[i*i::i] = bytearray(len(is_prime[i*i::i]))
    return is_prime

def reverse_num(n):
    return int(str(n)[::-1])

def is_palindrome(n):
    s = str(n)
    return s == s[::-1]

def solve():
    LIMIT = 10**8
    is_prime = sieve(LIMIT)

    results = []

    for p in range(2, LIMIT + 1):
        if not is_prime[p]:
            continue
        sq = p * p
        if is_palindrome(sq):
            continue
        rev = reverse_num(sq)
        sr = int(math.isqrt(rev))
        if sr * sr != rev:
            continue
        if sr <= 1 or sr > LIMIT:
            continue
        if not is_prime[sr]:
            continue
        results.append(sq)

    results.sort()

    if len(results) >= 50:
        answer = sum(results[:50])
        print(answer)
    else:
        print(f"Found only {len(results)} reversible prime squares")
        print(f"Partial sum: {sum(results)}")

if __name__ == "__main__":
    solve()