We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
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.
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.
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.
Project Euler #125: Palindromic sums
You are viewing a single comment's thread. Return to all 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.
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.
You get the formula (or a similar one) if you type into Wolfram Alpha: sum((a+kd)^2,k=0..n)
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.
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.