Palindromes that are sum of consecutive squares

I have been working on a Project Euler: 125, which took me ages to solve. The problem and source are cited below


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


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^2 + 1^2 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^8 that are both
palindromic and can be written as the sum of consecutive squares.

I firstly tried to figure out if there were some pattern in the square sums, however i found none. My solution ended sadly up being brute force one.

• 1) Generate all possible palindromes

• 2) Generate all possible values

of square numbers

1) Is fairly fast however 2) takes (understandably) ages. The code works and gives the correct answer, but it takes ages. I think the problem is memory.

Is there any faster way of checking whether a palindrome can be written as a sum of consecutive squares?

Any other suggestions for my code are also welcome. Python 2.7

```
from math import floor
from itertools import count

def palindromic_square_summable(limit):
"""
Finds all numbers p, such that
p = n^2 + (n+1)^2 + ... + m^2
and p is a palindrome. Eg 595 or 55.
"""
dic = get_quadratic_sums(limit)
pal = all_palindromes(2, limit)
total = 0
for key in pal:
try:
dic[key]
total += key
except:
pass
return total

def get_palindrome():
"""
Generator for palindromes.
Generates palindromes, starting with 0.
A palindrome is a number which reads the same in both directions.
"""
yield 0
for digits in count(1):
first = 10 ** ((digits - 1) // 2)
for s in map(s

The key problem with the performance of your code is get_quadratic_sums. This returns all sums of consecutive squares each of which is individually below the limit. But the vast majority of this work is wasted, because we are only interested in in sums of consecutive squares where the sum is below the limit.

So a very simple change to your code massively improves its performance. Where the code iterates over sums of squares:

for partial in partial_sums[0:i-1]:
    val = partial_sums[i] - partial
    dic[val] = 1

Iterate in reverse order (so that val is increasing) and stop when val is too large:

for partial in partial_sums[i-2::-1]:
    val = partial_sums[i] - partial
    if val >= limit:
        break
    dic[val] = 1

Now it runs in less than a second on my laptop:

>>> timeit(lambda:palindromic_square_summable(10**8), number=1)
0.7864874959923327

But we can do even better than that. Slicing a list in Python makes a copy of the sliced part of list. We can avoid the copy by iterating over the indices instead:

for j in xrange(i-2, -1, -1):
    val = partial_sums[i] - partial_sums[j]
    if val >= limit:
        break
    dic[val] = 1

Now it runs in less than half a second:

>>> timeit(lambda:palindromic_square_summable(10**8), number=1)
0.40678663086146116

A few more improvements:

-
int rounds towards zero, so you can write int(limit .5) instead of int(floor(limit .5)).

-
Since there have to be at least two squares in the sum, we only need to check up to int((limit / 2) ** .5).

-
get_quadratic_sums returns a dictionary whose keys are sums and whose values are always 1. But the values are never used, so it would make more sense to use Python's built-in sets:

def get_quadratic_sums(limit):
    """Return set of sums below limit of two or more consecutive squares."""
    max_square = int((limit / 2) ** .5) + 1
    partial_sums = [0] * max_square
    sums = set()
    _add = sums.add
    total = 0
    for i in xrange(1, max_square):
        total += i * i
        partial_sums[i] = total
        for j in xrange(i - 2, -1, -1):
            val = total - partial_sums[j]
            if val >= limit:
                break
            _add(val)
    return sums

Note the use of the local variable _add to remember the sums.add method: this avoids looking it up again on each loop iteration.

-
Similarly, all_palindromes can be changed to return a set instead of a dictionary:

def all_palindromes(limit):
    """Return set of palindromes below limit."""
    palindromes = set()
    _add = palindromes.add
    for p in get_palindrome():
        if p >= limit:
            break
        _add(p)
    return palindromes

-
Now that both of these functions return sets, you can just take their intersection, like this:

def palindromic_square_summable(limit=10**8):
    """Return the sum of palindromes below limit that are sums of two or
    more consecutive positive integers.

    """
    return sum(get_quadratic_sums(limit) & all_palindromes(limit))

This is even faster:

>>> timeit(palindromic_square_summable, number=1)
0.29244883195497096

StackExchange Code Review Q#128360, answer score: 6