Project Euler #125: Palindromic sums

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