Project Euler Problem 1

February 10, 2015

We provide three solutions; the first has O(n) time and O(n) space complexity, the second has O(n) time and O(1) space complexity, and the third has O(1) time and O(1) space complexity.

Our first solution uses a sieve. Initialize an array from 1 to n with zeros. Then sieve on 3 and 5, resetting the 0 to the index of the array element. Finally, sum all of the array elements:

(define (one n)
  (let ((sieve (make-vector n 0)))
    (do ((i 3 (+ i 3))) ((<= n i))
      (vector-set! sieve i i))
    (do ((i 5 (+ i 5))) ((<= n i))
      (vector-set! sieve i i))
    (let loop ((i 0) (sum 0))
      (if (= i n) sum
        (loop (+ i 1) (+ sum (vector-ref sieve i)))))))

> (one 1000)
233168

Our second solution counts from 1 to n, checking each number for divisibility by 3 or 5; here’s an iterative solution:

(define (two-iter n)
  (let loop ((i 1) (sum 0))
    (cond ((= i n) sum)
          ((or (zero? (modulo i 3))
               (zero? (modulo i 5)))
            (loop (+ i 1) (+ sum i)))
          (else (loop (+ i 1) sum)))))

> (two-iter 1000)
233168

And here’s the same algorithm in a recursive setting:

(define (two-recur n)
  (cond ((zero? n) 0)
        ((or (zero? (modulo n 3))
             (zero? (modulo n 5)))
          (+ n (two-recur (- n 1))))
        (else (two-recur (- n 1)))))

> (two-recur 999)
233168

Our third solution makes use of Gauss’ formula for the sum of the numbers from 1 to n. The sum of multiples of k less than n is (1 + 2 + … + ⌊n/k⌋) × k, where the sum inside the parentheses is computed by n × (n + 1) / 2. Then we compute the Project Euler solution as the sum of the multiples of 3 plus the sum of the multiplies of 5, less the sum of the multiples of 15 that were counted twice:

(define (three n)
  (define (gauss n) (* n (+ n 1) 1/2))
  (+ (* 3 (gauss (quotient n 3)))
     (* 5 (gauss (quotient n 5)))
     (- (* 15 (gauss (quotient n 15))))))

> (three 999)
233168

You can run the program at http://programmingpraxis.codepad.org/8pO1kZ1C.

Pages: 1 2

6 Responses to “Project Euler Problem 1”

  1. Three ways…
    (1) Brute force overall entries and summing them!
    (2) Brute force summing muliples of 5, multiples of 3 and removing duplicate multiples of 15…
    (3) Same as 2 but using formulae to compute sum – no need to brute force…

    sub bf {
    my $n = shift;
    my $t = 0;
    $t+= $_ foreach grep { !($_ % 3) || !($_ % 5) } 1..($n-1);
    return $t;
    }

    sub x {
    my $n = shift;
    return _x($n,3)+_x($n,5)-_x($n,15);
    }

    sub _x {
    my($n,$f)=@_;
    my $s = 0;
    my $t = 0;
    while($t<$n) {
    $s+=$t;
    $t+=$f;
    }
    return $s;
    }

    sub yy {
    my $n = shift;
    return _y($n,3)+_y($n,5)-_y($n,15);
    }

    sub _y {
    my($n,$f)=@_;
    $n = int (($n-1)/$f);
    return $f * ($n+1)*$n/2;
    }

    printf "%7d %20d %20d %20d\n", $_, bf($_), x($_), yy($_) foreach @ARGV;

  2. Rutger said

    My solution in Python.
    Easy to extend, just add your own function as long as it starts with “solve_” and returns the result as an int.

    #project euler 1
    import time
    
    # naive solution, iterate through all numbers
    def solve_brute_force(up_until):
    	result = 0
    	for i in range(up_until):
    		if (not i % 3) or (not i % 5):
    			result += i
    	return result
    
    # Wheeled, jumps from one number %3 or %5 to the next
    def solve_wheel_multiples(up_until):
    	i = 0
    	first_numbers = []
    	for i in range(0, 3*5+1):
    		if (not i % 3) or (not i % 5):
    			first_numbers.append(i)
    	wheel = []
    	for i in range(1,len(first_numbers)):
    		wheel.append(first_numbers[i] - first_numbers[i-1])
    	result = 0
    	idx = 0
    	len_wheel = len(wheel) #no need to copute it each iteration
    	number_mod3_or_mod5 = 0
    	while number_mod3_or_mod5 < up_until:
    		result += number_mod3_or_mod5
    		number_mod3_or_mod5 += wheel[idx]
    		idx = (idx + 1) % len_wheel
    	return result
    
    # Math, sum(1/2(n*(n+1)) * k) where n = #k < up_until, for k in 3,5 minus 15
    def solve_plain_math(up_until):
    	num_3 = (up_until-1) / 3 
    	x = (num_3 * (num_3+1))/2
    	num_5 = (up_until-1) / 5 
    	y = (num_5 * (num_5+1))/2
    	num_15 = (up_until-1) / 15 
    	z = (num_15 * (num_15+1))/2
    	return x*3 + y*5 - z*15
    
    # iterate through each solve methods dynamically (Python rocks :) !!)
    for method in [method for method in dir() if method.startswith("solve_")]:
    	print "\nRunning method:", method
    	start_time = time.time()
    	up_until = 1000
    	print locals()[method](up_until)
    	print "Run time (s):", time.time() - start_time
    
  3. Rutger said

    Above code outputs for n = 1000:

    Running method: solve_brute_force
    233168
    Run time (s): 0.0

    Running method: solve_plain_math
    233168
    Run time (s): 0.0

    Running method: solve_wheel_multiples
    233168
    Run time (s): 0.0

    ——————————————————–

    For n = 10000000:

    Running method: solve_brute_force
    23333331666668
    Run time (s): 1.47399997711

    Running method: solve_plain_math
    23333331666668
    Run time (s): 0.0

    Running method: solve_wheel_multiples
    23333331666668
    Run time (s): 0.986999988556

  4. Paul said
    def euler1a(): # simple
        return sum(i for i in range(1000) if i % 3 == 0 or i % 5 == 0)
    
    def euler1b(): # with sieve
        sieve = [0] * 1000
        sieve[3::3] = [1] * len(sieve[3::3])
        sieve[5::5] = [1] * len(sieve[5::5])
        return sum(i for i, s in enumerate(sieve) if s)
            
    def euler1c(): # with Gaussian sum
        def sumg(start, stop, inc):
            n = (stop - start) // inc + 1
            return n * start + inc * n * (n - 1) // 2
        return sumg(3, 999, 3) + sumg(5, 999, 5) - sumg(15, 999, 15)
    
  5. mcmillhj said

    Similar solution using Gauss’s summation formula in SML:

    fun sumMultiples3and5LessThanN n =
        let fun gaussian n = (n * (n + 1)) div 2
        in
                3 * gaussian(n div 3)
            +  5 * gaussian(n div 5)
            - 15 * gaussian(n div 15)
        end
    
  6. Jussi Piitulainen said

    Only two ways but they are more different. I suppose the sampling method
    is O(sample size) space, while the gambling method is O(1) space, but the
    sample size can be considered a constant. These count 0 as a multiple.

    import random
    
    def sampling(three = 3, five = 5, thousand = 1000, size = 500):
        sample = random.sample(range(thousand + 1), size)
        count = sum(1 for m in sample if (m % three == 0 or m % five == 0))
        return (count / size) * thousand
    
    def gambling(three = 3, five = 5, thousand = 1000, size = 500):
        count = sum(1 for m in ( random.randrange(thousand + 1)
                                 for _ in range(size) )
                    if (m % three == 0 or m % five == 0))
        return (count / size) * thousand
    
    if __name__ == '__main__':
        print('science says', sorted((sampling() for _ in range(11)))[5])
        print('gambler says', sorted((gambling() for _ in range(11)))[5])
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: