Saturday, August 6, 2011

Learning Python with Project Euler: Problem 1

This one is short and simple. There was really nothing to learn as far as Python goes, the constructs are similar to Ruby, though I'm sure there's a nicer way to write it. I'll also write my Ruby implementation which is a littler shorter. I'll likely try to write more efficient implementations in both languages.

The problem:
Add all the natural numbers below one thousand that are multiples of 3 or 5.

My Python implementation:
vsum, i = 0, 0
while i < 1000:
  vsum += i if i % 3 == 0 or i % 5 == 0 else 0
  i += 1
print 'sum: ' + str(vsum)

My Ruby implementation:
sum = 0
(0...1000).each { |v| sum += (v % 3 == 0 or v % 5 == 0) ? v : 0 }
puts "sum: #{sum}"

Contribution by Lov Loothra (250+ times faster than mine):
import sys
def main():
    N = 999

    #sum of all multiples of 3 < 1000
    sum3 = (N/3*(N - N%3 + 3))/2

    #sum of all multiples of 5 < 1000
    sum5 = (N/5*(N - N%5 + 5))/2

    #sum of all multiples of 3 & 5 (i.e. 15) < 1000
    sum15 = (N/15*(N - N%15 + 15))/2

    #final result
    print sum3 + sum5 - sum15

3 comments:

  1. I've posted a purely mathematical solution to this on Pastebin: http://pastebin.com/vgGBkJ3M

    ReplyDelete
  2. Awesome, very clever! I can't believe I didn't think to try a mathematical-only approach. I've been shamed since I do have a B.S. in mathematics.

    By comparison, your mathematical solution is about ~250 times faster (though my benchmark could be flawed, I wouldn't be surprised if it was actually more than that). If you don't mind, I'd like to post your solution here for future reference if that pastebin gets deleted.

    ReplyDelete
  3. Thanks for posting my solution! Please feel free to post, use or critique any code I share. Feedback and sharing is the only way we can learn! :)

    And the only reason I thought of that solution was cause I'm prepping math for some tests I have to take in a couple of weeks. :P

    ReplyDelete