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

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