# Project Euler 348: Sum of a square and a cube

Many numbers can be expressed as the sum of a square and a cube. Some of them in more than one way.

Consider the palindromic numbers that can be expressed as the sum of a square and a cube, both greater than 1, in exactly 4 different ways. For example, 5229225 is a palindromic number and it can be expressed in exactly 4 different ways:

22852 + 203

22232 + 663

18102 + 1253

11972 + 1563

Find the sum of the five smallest such palindromic numbers.

I used brute force; it solves in around 11 seconds. I thought about it for some time but couldn't come up with any obvious optimizations, the problem seems built for brute force. Any suggestions?

Note that I'm using PyPy which makes math code run much faster...

"""Find the sum of the five smallest palindromic numbers
that can be expressed as the sum of a square and a cube."""

from math import log10
from collections import Counter
from timeit import default_timer as timer

def is_palindrome(n):
length = int(log10(n))
while length > 0:
right = n % 10
left = n / 10**length
if right != left:
return False
n %= 10**length
n /=10
length -= 2
return True

start = timer()
palindromes = Counter()

for square in xrange(1, 30000):
squared = square**2
for cube in xrange(1, 3000):
cubed = cube**3
total = squared + cubed
if is_palindrome(total): palindromes[total] += 1

ans = sum(x[0] for x in palindromes.most_common(5))
elapsed_time = timer() - start
print "Found %d in %d s." % (ans, elapsed_time)

• I can't test it, but how well does your is_palindrome match up to the string version on PyPy? Jun 21, 2015 at 3:26

def is_palindrome(n):