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 = *(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)