This was another straightforward problem. It came down to looping through all primes and storing their squares. If the reverse of one of these prime squares has already been seen, then it is a reversible prime square.
Using a sieve to create the primes, gets the answer in roughly 8 seconds with Python 3.10.8.
def sieve(top):
sieve = [False, False] + [True] * (top - 1)
for p, isprime in enumerate(sieve):
if not isprime:
continue
yield p
num = p * p
while num <= top:
sieve[num] = False
num += p
def reverse(n):
k = 0
while n:
n, mod = divmod(n, 10)
k = 10 * k + mod
return k
def solve(n):
total = count = 0
seen = {}
for prime in sieve(31100101):
squ = prime ** 2
num = reverse(squ)
if num in seen:
total += num + squ
count += 2
if count >= n:
return total
seen[squ] = True
if __name__ == '__main__':
import sys
n = eval(sys.argv[1])
print(solve(n))
import pytest
from problem import solve, reverse, sieve
_test_sieve = (
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61,
67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137,
139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199,
211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277,
281, 283, 293,
)
def test_sieve():
for e, a in zip(_test_sieve, sieve(300)):
assert e == a
_test_reverse = (
(1, 1),
(2, 2),
(3, 3),
(4, 4),
(5, 5),
(6, 6),
(7, 7),
(8, 8),
(9, 9),
(10, 1),
(11, 11),
(12, 21),
(13, 31),
(14, 41),
(15, 51),
(16, 61),
(17, 71),
(18, 81),
(19, 91),
(20, 2),
)
@pytest.mark.parametrize('n,expect', _test_reverse)
def test_reverse(n, expect):
assert expect == reverse(n)
_test_not_solve = (
(50, 3611678744236),
(50, 113361847418),
(50, 1183208424),
(50, 1163845887),
(50, 29627292),
(50, 11002896),
(50, 172156),
)
@pytest.mark.parametrize('n,expect', _test_not_solve)
def test_not_solve(n, expect):
assert expect != solve(n)