Project Euler 1

bruno.py

#!/usr/bin/env python

import sys

if sys.platform == "win32":
    from time import clock as default_timer
else:
    from time import time  as default_timer

def bruno(n):
    total = 0 # total of the multiples of 3 or 5 seen so far
    next_mult_3 = 0 # the next multiple of 3 to be considered
    next_mult_5 = 0 # the next multiple of 5 to be considered

    i = 0

    while i < n:
	if i % 3 == 0:
	    total += i
        elif i % 5 == 0:
	    total += i
	i+=1

    return total

def rbrito(n):
    total = 0 # total of the multiples of 3 or 5 seen so far
    next_mult_3 = 0 # the next multiple of 3 to be considered
    next_mult_5 = 0 # the next multiple of 5 to be considered

    while next_mult_3 < n or next_mult_5 < n:
        if next_mult_3 < next_mult_5:
            total += next_mult_3
            next_mult_3 += 3
        elif next_mult_3 > next_mult_5:
            total += next_mult_5
            next_mult_5 += 5
        else: # a common multiple, count only once
            total += next_mult_3
            next_mult_3 += 3
            next_mult_5 += 5
    return total

def n_choose_2(n):
    return n*(n-1)/2

def rbrito2(n):
    n = n-1 # Up to n-1
    sum_3 = 3 * n_choose_2(1 + n/3)
    sum_5 = 5 * n_choose_2(1 + n/5)
    sum_15 = 15 * n_choose_2(1 + n/15)
    return sum_3 + sum_5 - sum_15

if __name__ == '__main__':
    n = 10000
    start = default_timer()
    for i in xrange(1000):
        bruno(n)
    length = default_timer() - start
    print("Function bruno took:\t%f s." % length)

    start = default_timer()
    for i in xrange(1000):
        rbrito(n)
    length = default_timer() - start
    print("Function rbrito took:\t%f s." % length)

    start = default_timer()
    for i in xrange(1000):
        rbrito2(n)
    length = default_timer() - start
    print("Function rbrito2 took:\t%f s." % length)

@kinow, If I run the functions listed above 1000 times, here is what I get:

Function bruno took: 2.774621 s.
Function rbrito took: 0.944093 s.

But, just for fun, I will be including a new function that is faster. Than both of these.

@kinow, with the latest version of this program, here is the output that I get:

Function bruno took: 2.740573 s.
Function rbrito took: 0.970601 s.
Function rbrito2 took: 0.001944 s.

If I am not mistaken, the function rbrito2 is about 1400 times faster than bruno, and about 500 times faster than rbrito.

:-O

But it was fun trying to use the integer divisions and understand your implementation with a single loop.

Could I see this new version? Please.

@kinow, I made a mistake with my benchmarking, as I forgot that I had left my processor with its clock in dynamic frequency mode (read that as: "it starts at its minimum frequency and when necessary, it goes to a higher frequency").

This might have given my solutions an unfair advantage regarding to your solution, as it was executed first, with a possible lower clock.

I have now locked the frequencies at their lowest (which is good on its own, as the program takes a larger amount of time and the resolution of the clock doesn't play a role as large as before) and this is what I get in a Phenon II X4 910 @800mhz, with Linux 2.6.38, in 64 bit mode (Debian sid as userland):

Function bruno took: 8.062006 s.
Function rbrito took: 2.748817 s.
Function rbrito2 took: 0.004651 s.

Regarding the "new version", they are all listed in this gist (actually, right there at the top), as I updated the code in this repository. See the revisions listed at the right... If you have any questions, feel free to drop me an e-mail.