Palindromes that are sum of consecutive squares

Question

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(str, range(first, 10 * first)):
            yield int(s + s[-(digits % 2)-1::-1])


def all_palindromes(minP, maxP):
    """Get a sorted list of all palindromes in intervall [minP, maxP]."""
    palindrom_generator = get_palindrome()
    palindrome_dict = dict()
    for palindrome in palindrom_generator:
        if palindrome > maxP:
            break
        if palindrome < minP:
            continue
        palindrome_dict[palindrome] = 1
    return palindrome_dict


def get_quadratic_sums(limit):
    """Get a list of all possible square sums"""
    max_square = int(floor( limit**0.5))
    partial_sums = [0]*(max_square+1)
    dic = dict()

    for i in range(1, max_square+1):
        partial_sums[i] = partial_sums[i - 1] + i**2
        for partial in partial_sums[0:i-1]:
            val = partial_sums[i] - partial
            dic[val] = 1
    return dic


if __name__ == '__main__':
    limit = 10**3
    print palindromic_square_summable(limit)

Answer 1

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:

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

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

3. 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.

4. 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
   

5. 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