Problem Description

The palindromic number 595 is interesting because it can be written as the sum of consecutive squares: 6² + 7² + 8² + 9² + 10² + 11² + 12².

There are exactly eleven palindromes below one-thousand that can be written as consecutive square sums, and the sum of these palindromes is 4164. Note that 1 = 0² + 1² has not been included as this problem is concerned with the squares of positive integers.

Find the sum of all the numbers less than 10⁸ that are both palindromic and can be written as the sum of consecutive squares.

Analysis

To solve this problem requires a simple search to the square root of the limit (10⁸) or 5,000. We use a set to eliminate duplicate sum-of-squares.

Solution

Runs < 1 second in Python.

from Euler import is_palindromic
 
limit = 10**8
sqrt_limit = int(limit**.5)
pal = set()
 
for i in range(1, sqrt_limit):
  sos = i*i
  for j in range(i+1, sqrt_limit):
    sos += j*j
    if sos>=limit: break
    if is_palindromic(sos): pal.add(sos)
 
print "Answer to PE125 = ", sum(pal), len(pal)

Comments

• More information on the Euler module can be found on the tools page.
• Takes 371,234 iterations.
• The second number printed is the size of the set.