find.py

#!/usr/bin/env python3

import sys
import bisect

specials = []
with open("specials.txt", "r") as f:
    for line in f:
        specials.append(int(line.strip()))
specials.sort()

T = int(next(sys.stdin).strip())

for case_num in range(1, T + 1):
    A, B = map(int, next(sys.stdin).split())
    left = bisect.bisect_left(specials, A)
    right = bisect.bisect_right(specials, B)
    count = right - left
    print(f"Case #{case_num}: {count}")

go.py

#!/usr/bin/env python3

import sys

memo = {}

def search(n, first, s):
    if (n, s) in memo:
        return memo[n, s]
    memo[n, s] = _search(n, first, s)
    return memo[n, s]

def _search(n, first, s):
    if n == 0:
        return [""]

    if s < 0:
        return []

    if first:
        possibilities = [1, 2, 3]
    else:
        possibilities = [0, 1, 2]

    result = []
    for digit in possibilities:
        subsol = search(n - 1, False, s - digit * digit)
        subsol = [str(digit) + x for x in subsol]
        subsol = [x for x in subsol if x.startswith("0") or special_numbers_from(x)]
        result.extend(subsol)
    return result

def special_numbers_from(s):
    candidates = [s + s[-2::-1], s + s[::-1]]
    candidates = map(int, candidates)
    candidates = [x * x for x in candidates]
    candidates = [x for x in candidates if str(x) == str(x)[::-1]]
    return candidates

def main():
    N = int(sys.argv[1])
    special_numbers = [
        x
        for n in range(1, N + 1)
        for x in search(n, True, 9)
    ]
    special_numbers = [
        special_number
        for x in special_numbers
        for special_number in special_numbers_from(x)
    ]
    special_numbers.sort()
    for special_number in special_numbers:
        print(special_number)

if __name__ == "__main__":
    main()

run.sh

cesarkawakami@pandambp13r ~/D/s/g/c-fair-and-square (master)> time ./go.py 25 > specials.txt
        5.88 real         5.47 user         0.11 sys

cesarkawakami@pandambp13r ~/D/s/g/c-fair-and-square (master)> diff -sN specials.txt specials-reference.txt
Files specials.txt and specials-reference.txt are identical