Problem 1. Find the sum of all the multiples of 3 or 5 below 1000.
As you have solved this problem we do not have to explain that all numbers divisible by 3
and/or by 5 should be counted.
So the first numbers to be added would be:
3, 5, 6, 9, 10, 12, 15 and so on.
A simple way to do this is to go through all numbers from 1 to 999 and test whether they are
divisible by 3 or by 5.
This would result in code like:
target=999
sum=0
for i=1 to target do
if (i mod 3=0) or (i mod 5)=0 then sum:=sum+i
output sum
(In some programming languages the mod operator is written as %)
Simple enough you might say.
But wait a minute: if we had asked to do the same for all numbers less than 1,000,000,000 that
is going to take quite a while. Perhaps you would like to try out that first (make sure your sum
variable does not overflow).
To get a more efficient solution you could also calculate the sum of the numbers less
than1000 that are divisible by 3, plus the sum of the numbers less than1000 that are divisible
by 5. But as you have summed numbers divisible by 15 twice you would have to subtract the
sum of the numbers divisible by 15.
If we now define a function:
Function SumDivisibleBy(n)
Details to be filled in
EndFunction
Then the answer would be
SumDivisibleBy(3)+SumDivisibleBy(5)-SumDivisibleBy(15)
Let’s look at the details of our function and take as example n=3.
We would have to add:
3+6+9+12+......+999=3*(1+2+3+4+...+333)
For n=5 we would get:
5+10+15+...+995=5*(1+2+....+199)
Now note that 199=995/5 but also 999/5 rounded down to the nearest integer.
In many programming languages there exists a separate operator for that: div or \.
If we now also note that 1+2+3+...+p=½*p*(p+1) our program becomes:
target=999
Function SumDivisibleBy(n)
p=target div n
return n*(p*(p+1)) div 2
EndFunction
Output SumDivisibleBy(3)+SumDivisibleBy(5)-SumDivisibleBy(15)







Problem 2
Find the sum of all the even-valued terms in the Fibonacci sequence
which do not exceed four million.
A direct translation of the problem statement would be a program like this:
limit=4000000
sum=0
a=1
b=1
while bif b mod 2=0 then sum=sum+b
h=a+b
a=b
b=h
output sum
Now let us see if we can get rid of the testing for even values.
Here is the beginning of the Fibonacci sequence with even numbers in red:
1 1 2 3 5 8 13 21 34 55 89 144 ...
a b c a b c a b c a b c
It is easy to prove that every third Fibonacci number is even.
It is not so difficult to change the program somewhat so that only every third number is
added:
limit=4000000
sum=0
a=1
b=1
c=a+b
while csum=sum+c
a=b+c
b=c+a
c=a+b
output sum
There is another beautiful structure hidden beneath this problem:
If we only write the even numbers:
2 8 34 144...
it seems that they obey the following recursive relation: E(n)=4*E(n-1)+E(n-2).
If we can prove that for the Fibonacci numbers the formula F(n)=4*F(n-3)+F(n-6) holds we
have proven this recursion.
The proof is on the following page. Perhaps you want to try that yourself first.
Copyright Project Euler, further distribution without the consent of the author(s) prohibited
Author: hk
F(n) = F(n-1) + F(n-2)
= F(n-2)+F(n-3)+F(n-2)=2 F(n-2) + F(n-3)
= 2(F(n-3)+F(n-4))+F(n-3))=3 F(n-3) + 2 F(n-4)
= 3 F(n-3) + F(n-4) + F(n-5) + F(n-6)
= 4 F(n-3) + F(n-6)
In the forum several other schemes can be found to avoid the testing for the Fibonacci
numbers to be even. If you did not find your method in this overview you might have a look

there.





Problem 9. Find the only Pythagorean triplet
(a, b, c), for which a + b + c = 1000.
Or, equivalently, find all Pythagorean triplets (a, b, c) with a + b + c = 1000.
The value 1000 is of course arbitrary, so we discuss the more general problem of
finding all Pythagorean triplets with a + b + c = s for some s.
It can easily be seen that for every Pythagorean triplet a > 3 and a + b + c is
even, you might want to prove that yourself.
9.1 The straightforward approach
The most straightforward approach is to simply loop over a and b and then check
whether a2 + b2 = (s − a − b)2. From the condition a < b < c, we conclude that
a 6 (s − 3)

3 and b < (s − a)

2.
That approach would lead to code along the lines of
s := 1000 // or whatever the perimeter should be
for a := 3 to (s-3) div 3
for b := (a+1) to (s-1-a) div 2
c := s-a-b
if c*c = a*a + b*b then
output (a,b,c)
end if
end for
end for
This algorithm is sufficiently fast for small enough s, but it doesn’t scale well.
If you multiply the value of s by a factor k, the span of each of the two loops
is multiplied by the same factor and since the loops are nested, the number of
cases to check is multiplied by k2. So if s is doubled, the programme takes
approximately four times as long and increasing the perimeter s by a factor of
10 increases the run time by a factor of approximately 100.
With a little work, you can find better bounds for the loops, thus considerably
speeding the algorithm up, but it will still have the same scaling behaviour. This
algorithm is definitely unsuitable for perimeters s > 1 000 000.
9.2 Using a parametrisation of Pythagorean triplets
A Pythagorean triplet (a, b, c) is by definition primitive if gcd(a, b, c) = 1. Since
for Pythagorean triplets one has gcd(a, b) = gcd(b, c) = gcd(c, a), such a triplet

c Project Euler, further distribution without the consent of the author(s) prohibited
Author: daniel.is.fischer
is primitive if and only if gcd(a, b) = 1. As was already known to the ancient
Greeks, all primitive Pythagorean triplets can be represented as
(9.1) a = m2 − n2, b = 2 · m · n, c = m2 + n2,
with m > n > 0, perhaps exchanging a and b to have a < b. These formulae
always produce a Pythagorean triplet, but it will be primitive if and only if
exactly one of m, n is even and gcd(m, n) = 1.
From any Pythagorean triplet you get a primitive one by dividing out the greatest
common divisor, so every Pythagorean triplet has a unique representation
(9.2) a = (m2 − n2) · d, b = 2 · m · n · d, c = (m2 + n2) · d,
with m > n > 0, gcd(m, n) = 1 and exactly one of m, n even – d is the greatest
common divisor of a, b and c.
Using that parametrisation we see
(9.3) a + b + c = 2 · m · (m + n) · d.
So to find a Pythagorean triplet (a, b, c) with a + b + c = s, we have to find a
divisor m (> 1) of s

2 and an odd divisor k (= m+ n) of s

2m with m < k < 2m
and gcd(m, k) = 1. Then set n = k − m, d = s

2mk and plug these into (9.2).
A fairly simple implementation of that algorithm might look like
s2 := s div 2
mlimit := d
p
s2e − 1
for m := 2 to mlimit
if s2 mod m = 0 then
sm := s2 div m
while sm mod 2 = 0 // reduce the search space by
sm := sm div 2 // removing all factors 2
end while
if m mod 2 = 1 then k := m+2 else k := m+1
while k < 2*m and k 6 sm
if sm mod k = 0 and gcd(k,m) = 1 then
d := s2 div (k*m)
n := k-m
a := d*(m*m-n*n)
b := 2*d*m*n
c := d*(m*m+n*n)
output (a,b,c)
end if
k := k+2
end while
end if
end for

c Project Euler, further distribution without the consent of the author(s) prohibited
Author: daniel.is.fischer
where d e is the ceiling function, i.e. dxe is the smallest integer i > x. This
implementation is rather fast and scales well, s 6 1010 are processed in fractions
of a second. However, at the expense of more complicated code, it can still be
improved a bit by making use of the primefactorisation of s

2.
9.3 The parametrisation of Pythagorean triplets
9.3.1 Verification of the conditions for primitive triplets
Let us repeat the conditions:
The Pythagorean triplet (a, b, c) = (m2 − n2, 2mn,m2 + n2), m > n > 0 is
primitive if and only if gcd(m, n) = 1 and exactly one of m and n is even.
If gcd(m, n) = d > 1, then obviously d2 is a common divisor of a, b and c, and if
m and n are both odd, a, b and c are all even, so the conditions are necessary.
On the other hand, if exactly one of m and n is even and the triplet is not
primitive, let p be a prime dividing a, b and c. Since a and c are odd, so is p.
Any odd prime dividing b must divide at least one of m and n, say p divides m.
Then p also divides m2. But as p also divides c = m2 + n2, p divides n2 (and n),
too. From that follows gcd(m, n) > 1 and thus the sufficiency of the conditions.
9.3.2 Derivation of the parametrisation
Let T = (a, b, c) be a Pythagorean triplet and x = a

c, y = b

c. Then (x, y) is a
point on the unit circle with rational coordinates and all triplets obtained from
T by multiplying a, b and c with the same rational number—and only these—
will lead to the same point. Conversely, if x = p

q, y = r

q are positive rational
numbers with x2 + y2 = 1, then (p, r, q) is a Pythagorean triplet (not necessarily
with a < b). Now consider a straight line with positive slope s passing through
(0,−1). A parametrisation of that line is given by (t, s · t−1), t 2 R. The second
point of intersection of that line and the unit circle is obtained by solving the
equation
(9.4) t2 + (s · t − 1)2 = 1.
Rearranging this equation leads to (s2 + 1) · t2 = 2st. The nonzero solution
is thus t1 = (2s)

(s2 + 1) and the intersection then has coordinates x = t1 and
y = s · t1−1 = (s2 − 1)

(s2 + 1). It can be seen that both coordinates are rational
and positive if and only if s is rational and greater than 1. So if s = m

n with
m > n > 0 then x = (2mn)

(m2 + n2), y = (m2 − n2)

(m2 + n2) and we obtain
the Pythagorean triplet (a, b, c) = (2mn,m2 − n2,m2 + n2).

c Project Euler, further distribution without the consent of the author(s) prohibited
Author: daniel.is.fischer
If we start with a primitive triplet (a, b, c), the slope of the line passing through
(0,−1) and
􀀀
a

c, b

c

is (b + c)

a = m

n, where the second is the reduced form, i.e.
gcd(m, n) = 1. Then T = (2mn,m2 − n2,m2 + n2) is a multiple of (a, b, c).
If m and n have different parity, we’re done, because then T is also primitive as
we saw above, therefore it follows that T = (a, b, c).
If m and n are both odd, let u = (m + n)

2, v = (m − n)

2. Since m and n
are odd and m = u + v, n = u − v, one of u and v is even, the other odd, and
gcd(u, v) = 1. Further
2mn = 2(u + v)(u − v) = 2(u2 − v2)
) mn = u2 − v2,
m2 − n2 = (u2 + 2uv + v2) − (u2 − 2uv + v2) = 4uv
)
m2 − n2
2
= 2uv,
m2 + n2 = (u2 + 2uv + v2) + (u2 − 2uv + v2) = 2(u2 + v2)
)
m2 + n2
2
= u2 + v2,
(9.5)
so T1 = (u2 − v2, 2uv, u2 + v2) is a primitive triplet which is also a multiple of
(a, b, c), hence T1 = (a, b, c).

c Project Euler, further distribution without the consent of the author(s) prohibited
Author: daniel.is.fischer