Sunday, September 4, 2011

Python solution of Project Euler, problem 6

Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.

I don't have much to say about this solution. I found this one pretty trivial to implement with Python.  I'm posting my solution just to keep everything in sequence. :)  Basically, the question is asking to find x, where

x = (1 + 2 + .. + 100)2 - (12 + 12 + ... + 1002)
def main():
  N = 100
  sum1, sum2 = 0, 0
  for i in range(1, N + 1):
    sum1 += i
    sum2 += pow(i,2)
  return pow(sum1,2) - sum2

if '__main__' == __name__:
  print main()

Edit: the iterative solution was trivial, but the mathematical solution is much more efficient and clever:

Mathematical Solution (credit to Lov Loothra)
N = 100
s1 = N*(N + 1)/2 # sum of first N numbers
s2 = N*(N + 1)*(2*N + 1)/6 # sum of first N squares
print s1*s1 - s2

2 comments:

  1. Here's a link to my 'purely mathematical' solution for this problem: http://pastebin.com/vrGTvL3Q :P

    ReplyDelete
  2. Nice, I figured there would be a mathematically solution (and I also expected you would figure it out :)). I should brush up on my mathematics and formula derivation techniques.

    ReplyDelete