## Problem 1 - Multiples of 3 and 5

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.

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

``````

In [172]:

import math

``````
``````

In [51]:

def multiple35(n):
n3 = (n - 1) // 3
sum3 = 3 * n3 * (n3 + 1) // 2
n5 = (n - 1) // 5
sum5 = 5 * n5 * (n5 + 1) // 2
n15 = (n - 1) // 15
sum15 = 15 * n15 * (n15 + 1) // 2
return sum3 + sum5 - sum15

``````
``````

In [52]:

print(multiple35(1000))

``````
``````

233168

``````

## Problem 2 - Even Fibonacci numbers

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

``````

In [53]:

def fib(limit):
a = 1
b = 2
while b <= limit:
a, b = b, a + b
return [a, b]

``````

While k = 1, 2, 3... F(3k - 2) and F(3k): odd value items F(3k - 1): even value items

F(2) + F(5) + F(8) + ... + F(3k - 1) (even values = SE(3k - 1)) = 1 + F(1) + F(3) + F(4) + F(6) + (F7) + ... + F(3k - 3) + F(3k - 2) (odd values + 1)

Add up: 2 * SE(3k - 1) = 1 + F(1) + F(2) + ... + F(3k - 1) = 1 + S(3k - 1) = F(3k + 1) - 1 SE(3k - 1) = (F(3k + 1) - 1) / 2

``````

In [66]:

def even_sum(limit):
a, b = fib(limit)
if a % 2:
if b % 2:
## odd, odd
return (b - 1) // 2
## odd, even
return (a - 1) // 2
## even, odd
return (a + b - 1) // 2

``````
``````

In [74]:

fib(100)

``````
``````

Out[74]:

[89, 144]

``````
``````

In [75]:

even_sum(100)

``````
``````

Out[75]:

44

``````
``````

In [71]:

print(even_sum(4000000))

``````
``````

4613732

``````

## Problem 3 - Largest prime factor

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?

``````

In [91]:

def check_divisor(n, i):
while not n % i:
n //= i
return n

``````
``````

In [112]:

def largest_prime_factor(n):
n = check_divisor(n, 2)
if n == 1:
return 2
i = 3
while i <= math.sqrt(n):
n = check_divisor(n, i)
i += 2
if n > 2:
return n
return i - 2

``````
``````

In [115]:

print(largest_prime_factor(600851475143))

``````
``````

6857

``````

## Problem 4 - Largest palindrome product

A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 × 99.

Find the largest palindrome made from the product of two 3-digit numbers.

``````

In [159]:

def isPal(s):
return s == s[::-1]

``````
``````

In [ ]:

def firstPal(n):

``````
``````

In [ ]:

def largestPal(n):
for i in range(100, 1000):
if n % i == 0 and n / i >= 100 && n / i < 1000:
return n
return largestPal(firstPal(n - 1))

``````
``````

In [153]:

# pals = []
# for num in range(101101, 1000000):
#     if not isPal(str(num)):
#         continue
#     for i in range(100, int(math.sqrt(num) + 1)):
#         if num / i > 999:
#             continue
#         if num % i == 0:
#             pals.append(num)
#             break;

``````
``````

In [156]:

# pals = []
# for i in range(100, 1000):
#     for j in range(100, 1000):
#         ij = i * j
#         if isPal(str(ij)):
#             pals.append(ij)

``````
``````

In [157]:

n = 1000000

``````
``````

In [158]:

print(max([pal for pal in pals if pal < n]))

``````
``````

906609

``````

## Problem 5 - Smallest multiple

2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.

What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?

``````

In [133]:

def gcd(a, b):
while b != 0:
a, b = b, a % b
return a

``````
``````

In [137]:

def lcm(a, b):
return a * b // gcd(a, b)

``````
``````

In [150]:

def smallest_multiple(n):
s_m = 1
for num in range(1, n + 1):
s_m = lcm(s_m, num)
return s_m

``````
``````

In [151]:

print(smallest_multiple(20))

``````
``````

232792560

``````

## Problem 6 - Sum square difference

The sum of the squares of the first ten natural numbers is, 1^2 + 2^2 + ... + 10^2 = 385

The square of the sum of the first ten natural numbers is, (1 + 2 + ... + 10)^2 = 55^2 = 3025

Hence the difference between the sum of the squares of the first ten natural numbers and the square of the sum is 3025 − 385 = 2640.

Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.

### Sol

``````1^2 + 2^2 + ... + n^2 = n * (n + 1) * (2 * n + 1) / 6
1 + 2 + ... + n = n * (n + 1) /2
difference = n * (n + 1) * (n - 1) * (3 * n + 2) / 12``````
``````

In [169]:

def sum_square_diff(n):
return n * (n + 1) * (n - 1) * (3 * n + 2) // 12

``````
``````

In [171]:

print(sum_square_diff(100))

``````
``````

25164150

``````

## Problem 7 - 10001st prime

By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.

What is the 10 001st prime number?

``````

In [ ]:

``````