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.