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
Answer: 233168
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
Answer: 4613732
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 = []
for p in primes_file.read().split('\n'):
primes.append(int(p))
composite = 600851475143
for p in primes:
if composite%p==0:
composite = composite/p
if composite==1:
print p
break
Answer: 6857
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
Answer: 906609
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 = []
for p in primes_file.read().split('\n'):
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
Answer: 232792560
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
Answer: 25164150
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')
print primes_file.read().split('\n')[10000]
Answer: 104743
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
Answer: 40824
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\).
Answer: 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
for p in primes_file.read().split('\n'):
if int(p) > 2000000:
break
sum += int(p)
print sum
Answer: 142913828922
Time: 314ms
