## Project Euler Problem 1

### February 10, 2015

Project Euler is a collection of math problems intended for computer solution, and is one of the inspirations for Programming Praxis. The first problem on Project Euler, which also regularly appears on lists of phone interview questions, asks you to:

Find the sum of all the multiples of 3 or 5 below 1000.

Your task is to write a program that solves Problem 1 for arbitrary n; since the problem is simple, you must provide at least three fundamentally different solutions. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Advertisement

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])
```