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 valuesof square numbers1) 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.7from math import floorfrom itertools import countdef 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 totaldef 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_dictdef 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 dicif __name__ == '__main__':    limit = 10**3    print palindromic_square_summable(limit)
Palindromes that are sum of consecutive squares
python;performance;programming challenge;python 2.7;palindrome
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] = 1Iterate 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] = 1Now it runs in less than a second on my laptop:>>> timeit(lambda:palindromic_square_summable(10**8), number=1)0.7864874959923327But 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] = 1Now it runs in less than half a second:>>> timeit(lambda:palindromic_square_summable(10**8), number=1)0.40678663086146116A 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 sumsNote 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 palindromesNow 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