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

ansraghav100 + 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.

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.

aashish12kr + 3 comments I have passed all the testcase except 3-7. Can anyone suggest where am I wrong??

adityad85Asked to answer + 0 comments [deleted]rastogir + 1 comment I am getting wrong answer for all cases except first and last,and timeout error for testcase 8.works for sample case,works for 2 1000000000 1000000000 5 1 outputs 0 0.help?

sabeyrat + 0 comments At one point, I also had wrong answers for all cases except for the first and the last. For me, it was because I wasn't keeping track of the previously found sums. There are some consecutive squares that has the same answer. You shouldn't be adding the same number twice.

JaviSal + 0 comments I have exactly the same problem. 3-7 fail. I have checked the bounds, used long ints and avoided duplicate palindromes, but still don't get these tests.

Sort 22 Discussions, By:

Please Login in order to post a comment