# Project Euler #125: Palindromic sums

# Project Euler #125: Palindromic sums

priyamvad_mishra + 4 comments Sum of square of each number of an AP with first term a and common difference d, is given by Σn^2(a,d) = n.(a^2)+(1/6).(d^2).n.(n-1).(2n-1)+a.n.d.(n-1) ; n is number of terms So if you put a=1 and d=1 You get, Σn^2(1,1)

= n+(1/6).n.(n-1).(2n-1)+n.(n-1) = n^2+(1/6).n.(n-1).(2n-1) = n(n+(1/6).(n-1).(2n-1)) = (n/6).(6n+2.n^2 - 3n + 1) = (n/6).(2.n^2 + 3n + 1) = (1/6).n.(n+1).(2n+1) Which is formula for Σn2. So by using Σn^2(a,d) formula, we don’t need to get the sum using loop, we can directly get the sum of square of AP till nth term using this. For example, In 3^2+5^2+7^2, a=3 and d=2 and n=3 So if we put it in above formula, we get 83.Hope this will eliminate the timeouts, along with the fact that if sum of first 2 terms exceeds limit till you have to search palindrome(N), you should break the loop.

raghavgarg1257 + 1 comment can you explain how did you get that formula? I have used this formula but still getting timeout on every testcase except the sample testcase.

holgerschl + 0 comments You get the formula (or a similar one) if you type into Wolfram Alpha: sum((a+kd)^2,k=0..n)

kryptonite123 + 0 comments I'm unable to understand your last statement. "along with the fact that if sum of first 2 terms exceeds limit till you have to search palindrome(N), you should break the loop" ?

Are you following brute force approach to compute sigma(a^2(n,d)) for all possible combinations of a,n. Or are you using some pruning strategry by prestoring all possible palindromes. and looking for few combinations for a,n that will get to the desired palindrome. Thanks for the post.

vishwass + 0 comments [deleted]cantonios + 0 comments You probably don't want to use that formula. You have to double-loop anyways, one for starting number, the other for # of terms. It's much faster to add on a j*j than to compute that summation formula.

This problem really only comes down to having a fast palindrome check.

ghosh_saikat4000 + 0 comments Note - If a certain number can be written as the sum of consecutive squares in more than one ways, it must be counted ONLY once.

kitchent + 0 comments Was passing with 100.00 with Pypy 2 but only 47.06 with Python 2. After all, there often exists a better approach than brute force.

aronquemarr + 0 comments This times out whenever difference is 1. (Ignore the main)

from math import * # Returns a congruence class of a specified modulus and residue, # constrained in [lower, upper] def congruence_class(residue, modulus, lower, upper, order = 'asc'): residue = residue % modulus strict_lower = (lower//modulus)*modulus + residue if strict_lower < lower: strict_lower += modulus strict_upper = (upper//modulus)*modulus + residue if strict_upper > upper: strict_upper -= modulus if order == 'asc': return range(strict_lower, strict_upper + 1, modulus) elif order == 'desc': return range(strict_upper, strict_lower - 1, -modulus) # Returns true if any consecutive sequence of numbers # in the desc sorted array adds up to target def is_consecutive_sum(desc_array, start, end, target): #print("desc_array [{0}:{1}] = {2}".format(start, end, desc_array[start:end])) if (end - start) <= 1: return False result = sum(desc_array[start:end]) if result == target: return True elif result > target: return\ is_consecutive_sum(desc_array, start, end-1, target)\ or\ is_consecutive_sum(desc_array, start+1, end, target) else: return False # Checks every congruence class def is_palindrome_sum_of_squares(number, difference): limit = int(sqrt(number)) #The limit can be optimized? for i in range(0, difference): AP = congruence_class(i, difference, 1, limit, 'desc') squaredAP = list(map(lambda x: x*x, AP)) if is_consecutive_sum(squaredAP, 0, len(squaredAP), number): return True # Generator to yield palindromes def generate_palindromes(start, stop, step = 1): for x in range(start, stop, step): if str(x) == str(x)[::-1]: yield x # What the problem actually requires def sum_of_desired_palindromes(number, difference): palindrome_sums = 0 for i in generate_palindromes(1, number+1): if is_palindrome_sum_of_squares(i, difference): palindrome_sums += i return palindrome_sums if __name__ == "__main__": print(sum_of_desired_palindromes(10, 1))

SANJAY_GOLCHHA + 0 comments brute froce approach is not working it is showing TLE how can i optimize more , any suggestions ???

prasanth270 + 2 comments First Test Case executed Successfully but the others fail saying 'Timed Out'. How do I Finish this? Any Info could be helpfull. Thanks

maruthi12Asked to answer + 0 comments Test for random cases till 10^9 and check if u get the right answer.Also try optimizing the loop's execution speed.

Bishwajit_007 + 0 comments Lol Same Except first one all others failing....

Karayi + 0 comments i am getting wrong answer for test cases 29,31and 32 please help.thanks

kalai_andev + 1 comment whats is meant by timeout??? how to resolve that !! My testcases except testcase 0 is showing timeout. Is it due to more time complexity of my code?

mikesflowersAsked to answer + 0 comments Yes, it is due to the time complexity of your code. All of the tests can be solved in <10s. If your code exceeds 10s on any testcase then it is aborted and considered a fail.

Sort 23 Discussions, By:

Please Login in order to post a comment