# Project Euler | Problems 1-9

"Without a tagline since 2010"

### Problem 1

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

Solution:

sum = 0
for i in range (1,1000):
if i%3==0 or i%5==0:
sum += i
print sum


Time: <1ms

### Problem 2

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, \ldots$$

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

Solution:

a = 1
b = 1
c = 1

sum = 0
while c < 4000000:
c = a + b
a = b
b = c
if c%2==0:
sum += c
print sum


Time: <1ms

### Problem 3

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

What is the largest prime factor of the number 600851475143 ?

Solution:

primes_file = open('../primes/primes.txt')
primes = []
primes.append(int(p))

composite = 600851475143
for p in primes:
if composite%p==0:
composite = composite/p
if composite==1:
print p
break


Time: 3ms

### Problem 4

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

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

Solution:

import math

def digit(n,i):
d = int(math.floor(n/pow(10,i)))
return d%10

def is_palindrome(n):
power = int(math.floor(math.log10(n)))
digits = []
for i in range(0,power+1):
digits.append(digit(n,i))

for i in range(0,len(digits)):
if digits[i] != digits[len(digits)-1-i]:
return False
return True

largest = -1
for i in range(999,100,-1):
for j in range(999,100,-1):
product = i*j
if is_palindrome(product):
if product > largest:
largest = product
print largest


Time: 10350ms

### Problem 5

$$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$$?

Solution:

n = 20
primes_file = open('../primes/primes.txt')
primes = []
prime_powers = []
if int(p)>n:
break
primes.append(int(p))
prime_powers.append(0)

for i in range(0,n+1):
for j in range(0,len(primes)):
a = i
m = 0
p = primes[j]
while a%p==0 and a!=0:
a = a/p
m += 1
if m > prime_powers[j]:
prime_powers[j] = m

product = 1
for j in range(0,len(primes)):
product *= pow(primes[j],prime_powers[j])
print product


Time: 1ms

### Problem 6

The sum of the squares of the first ten natural numbers is,

$$1^2 + 2^2 + \ldots + 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.

Solution:

This solution uses the standard expressions for the sum of squares of integers and sum of integers and then a dash of algebra for a super fast solution.

n = 100
print n*(n+1)*(3*n*n-n-2)/12


Time: <1ms

### Problem 7

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?

Solution:

primes_file = open('../primes/primes.txt')


Time: 2ms

### Problem 8

Find the greatest product of five consecutive digits in the 1000-digit number.
73167176531330624919225119674426574742355349194934
96983520312774506326239578318016984801869478851843
85861560789112949495459501737958331952853208805511
12540698747158523863050715693290963295227443043557
66896648950445244523161731856403098711121722383113
62229893423380308135336276614282806444486645238749
30358907296290491560440772390713810515859307960866
70172427121883998797908792274921901699720888093776
65727333001053367881220235421809751254540594752243
52584907711670556013604839586446706324415722155397
53697817977846174064955149290862569321978468622482
83972241375657056057490261407972968652414535100474
82166370484403199890008895243450658541227588666881
16427171479924442928230863465674813919123162824586
17866458359124566529476545682848912883142607690042
24219022671055626321111109370544217506941658960408
07198403850962455444362981230987879927244284909188
84580156166097919133875499200524063689912560717606
05886116467109405077541002256983155200055935729725
71636269561882670428252483600823257530420752963450


Solution:

n = '73167176531330624919225119674426574742355349194934969835203127745063262395
78318016984801869478851843858615607891129494954595017379583319528532088
05511125406987471585238630507156932909632952274430435576689664895044524
45231617318564030987111217223831136222989342338030813533627661428280644
44866452387493035890729629049156044077239071381051585930796086670172427
12188399879790879227492190169972088809377665727333001053367881220235421
80975125454059475224352584907711670556013604839586446706324415722155397
53697817977846174064955149290862569321978468622482839722413756570560574
90261407972968652414535100474821663704844031998900088952434506585412275
88666881164271714799244429282308634656748139191231628245861786645835912
45665294765456828489128831426076900422421902267105562632111110937054421
75069416589604080719840385096245544436298123098787992724428490918884580
15616609791913387549920052406368991256071760605886116467109405077541002
25698315520005593572972571636269561882670428252483600823257530420752963
450'

largest = 0
for i in range(0,995):
d1 = int(n[i+0])
d2 = int(n[i+1])
d3 = int(n[i+2])
d4 = int(n[i+3])
d5 = int(n[i+4])
product = d1*d2*d3*d4*d5
if product > largest:
largest = product
print largest


Time: 5ms

### Problem 9

A Pythagorean triplet is a set of three natural numbers, $$a b c$$, for which $$a^2 + b^2 = c^2$$
For example, $$3^2 + 4^2 = 9 + 16 = 25 = 5^2$$.

There exists exactly one Pythagorean triplet for which $$a + b + c = 1000$$.
Find the product $$abc$$.

Solution:

This problem is best suited to a pen and paper solution. A Pythagorean triple in its simplest form takes the form $$a^2+(2a+1)=(a+1)^2$$, which can be transformed by multiplying by a common factor $$n$$. Constraining the sum of the terms to $$1000$$ gives $$1000=n(2a+1+\sqrt{2a+1})=n(b^2+b)$$, and using the quadratic equation gives the solution $$b=-1/2+\sqrt{1+4000/n}/2$$. To find integer solutions then $$1+1000/n$$ must be a perfect square. The only value of $$n$$ which satisfies this condition is $$n=50, b=4$$. Putting this back into the equation gives $$(a,b,c)=(375,200,425)$$, with a product of $$31875000$$.

Time: N/A

### Problem 10

The sum of the primes below $$10$$ is $$2 + 3 + 5 + 7 = 17$$.

Find the sum of all the primes below two million.

Solution:

primes_file = open('../primes/primes.txt')
sum = 0