## 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.

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;

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.

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

Similar solution using Gauss’s summation formula in SML:

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.