Project Euler #11

Problem 11

What is the greatest product of four adjacent numbers in any direction (up, down, left, right, or diagonally) in the 20×20 grid?

numbers = (( 8,  2, 22, 97, 38, 15,  0, 40,  0, 75,  4,  5,  7, 78, 52, 12, 50, 77, 91,  8),
           (49, 49, 99, 40, 17, 81, 18, 57, 60, 87, 17, 40, 98, 43, 69, 48,  4, 56, 62,  0),
           (81, 49, 31, 73, 55, 79, 14, 29, 93, 71, 40, 67, 53, 88, 30,  3, 49, 13, 36, 65),
           (52, 70, 95, 23,  4, 60, 11, 42, 69, 24, 68, 56,  1, 32, 56, 71, 37,  2, 36, 91),
           (22, 31, 16, 71, 51, 67, 63, 89, 41, 92, 36, 54, 22, 40, 40, 28, 66, 33, 13, 80),
           (24, 47, 32, 60, 99,  3, 45,  2, 44, 75, 33, 53, 78, 36, 84, 20, 35, 17, 12, 50),
           (32, 98, 81, 28, 64, 23, 67, 10, 26, 38, 40, 67, 59, 54, 70, 66, 18, 38, 64, 70),
           (67, 26, 20, 68,  2, 62, 12, 20, 95, 63, 94, 39, 63,  8, 40, 91, 66, 49, 94, 21),
           (24, 55, 58,  5, 66, 73, 99, 26, 97, 17, 78, 78, 96, 83, 14, 88, 34, 89, 63, 72),
           (21, 36, 23,  9, 75,  0, 76, 44, 20, 45, 35, 14,  0, 61, 33, 97, 34, 31, 33, 95),
           (78, 17, 53, 28, 22, 75, 31, 67, 15, 94,  3, 80,  4, 62, 16, 14,  9, 53, 56, 92),
           (16, 39,  5, 42, 96, 35, 31, 47, 55, 58, 88, 24,  0, 17, 54, 24, 36, 29, 85, 57),
           (86, 56,  0, 48, 35, 71, 89,  7,  5, 44, 44, 37, 44, 60, 21, 58, 51, 54, 17, 58),
           (19, 80, 81, 68,  5, 94, 47, 69, 28, 73, 92, 13, 86, 52, 17, 77,  4, 89, 55, 40),
           ( 4, 52,  8, 83, 97, 35, 99, 16,  7, 97, 57, 32, 16, 26, 26, 79, 33, 27, 98, 66),
           (88, 36, 68, 87, 57, 62, 20, 72,  3, 46, 33, 67, 46, 55, 12, 32, 63, 93, 53, 69),
           ( 4, 42, 16, 73, 38, 25, 39, 11, 24, 94, 72, 18,  8, 46, 29, 32, 40, 62, 76, 36),
           (20, 69, 36, 41, 72, 30, 23, 88, 34, 62, 99, 69, 82, 67, 59, 85, 74,  4, 36, 16),
           (20, 73, 35, 29, 78, 31, 90,  1, 74, 31, 49, 71, 48, 86, 81, 16, 23, 57,  5, 54),
           ( 1, 70, 54, 71, 83, 51, 54, 69, 16, 92, 33, 48, 61, 43, 52,  1, 89, 19, 67, 48))

n = len(numbers)

ans = 0
for i in range(0, n):
    for j in range(0, n):
        if i <  n-3:
            ans = max(ans, numbers[i][j]*numbers[i+1][j]*numbers[i+2][j]*numbers[i+3][j])
        if j < n-3:
            ans = max(ans, numbers[i][j]*numbers[i][j+1]*numbers[i][j+2]*numbers[i][j+3])
        if i<n-3 and j<n-3:
            ans = max(ans, numbers[i][j]*numbers[i+1][j+1]*numbers[i+2][j+2]*numbers[i+3][j+3])
        if i<n-3 and j>=3:
            ans = max(ans, numbers[i][j]*numbers[i+1][j-1]*numbers[i+2][j-2]*numbers[i+3][j-3])
            
print ans

Project Euler #10

Problem 10

Find the sum of all the primes below two million.

import math

def list_of_primes(n):
    primes = []
    primes.append(2)
    yield 2
    for i in xrange(3, n, 2):
        if is_prime(i, primes):
            primes.append(i)
            yield i

def is_prime(i, primes):
    i_sqrt = math.sqrt(i)
    for p in primes:
        if i%p == 0:
            return False
        elif p>i_sqrt:
            return True
    return True
        
print sum(list_of_primes(2000000))

# A much faster version using the sieve of Eratosthenes,
# which is faster for "small" numbers such as 2 million. 

import math

n = 2000000

flags = n * [True]

n_sqrt = int(math.sqrt(n))
for i in range(2, n_sqrt):
    if flags[i]:
        flags[2*i:n:i] = [False] * (int((n-1)/i)-1)

print sum(i for i in range(2,n) if flags[i])

Project Euler #9

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.

def prod_abc(n):
    a, b, c = 1, 2, n-3
    while a < n/3:
        if a*a+b*b == c*c:
            return a*b*c
        else:
            if c > b+2:
                a, b, c = a, b+1, c-1
            else:
                a, b, c = a+1, a+2, n-2*a-3

print prod_abc(1000)

Project Euler #8

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

def find_gp5(n):
    l = len(n)
    p = 0
    for i in range(0, l-5):
        d = [int(c) for c in n[i:i+5]]
        p_i = 1
        for ii in range(0,5):
            p_i *= d[ii]
        if p<p_i:
            p = p_i
    return p

print find_gp5("73167176531330624919225119674426574742355349194934\
96983520312774506326239578318016984801869478851843\
85861560789112949495459501737958331952853208805511\
12540698747158523863050715693290963295227443043557\
66896648950445244523161731856403098711121722383113\
62229893423380308135336276614282806444486645238749\
30358907296290491560440772390713810515859307960866\
70172427121883998797908792274921901699720888093776\
65727333001053367881220235421809751254540594752243\
52584907711670556013604839586446706324415722155397\
53697817977846174064955149290862569321978468622482\
83972241375657056057490261407972968652414535100474\
82166370484403199890008895243450658541227588666881\
16427171479924442928230863465674813919123162824586\
17866458359124566529476545682848912883142607690042\
24219022671055626321111109370544217506941658960408\
07198403850962455444362981230987879927244284909188\
84580156166097919133875499200524063689912560717606\
05886116467109405077541002256983155200055935729725\
71636269561882670428252483600823257530420752963450")

Project Euler #7

Probelm 7

What is the 10001st prime number?

def find_nth_prime(n): 
    primes = [2]
    p = 2
    for i in range(1, n):
        p = next_prime(primes)
        primes.append(p)
    return p

def next_prime(primes):
    if primes[-1] == 2:
        return 3
    i = primes[-1] + 2
    while True:
        iisprime = True
        for p in primes:
            if i%p == 0:
                iisprime = False
                break
        if iisprime:
            return i
        else:
            i = i+2

print find_nth_prime(10001)

# Improved version based on the following facts 
# (1) all primes greater than 3 can be written as 6*k +- 1.
# (2) if a number N cannot be divided by all primes less or 
#      equal to sqrt(N), N is a prime.

import math

known_primes = [2,3]

def find_nth_prime(n):
    if n==1:
        return 2
    if n==2:
        return 3
    nprimes = 2
    k = 1
    while True:
        i = 6*k-1
        if is_prime(i):
            nprimes += 1
            if nprimes == n:
                return i
        i += 2
        if is_prime(i):
            nprimes += 1
            if nprimes == n:
                return i
        k += 1

def is_prime(i):
    global known_primes
    i_sqrt = math.sqrt(i)
    for p in known_primes:
        if i%p == 0:
            return False
        if p>i_sqrt:
            known_primes.append(i)
            return True
    known_primes.append(i)
    return True

print find_nth_prime(10001)

Project Euler #6

Problem 6

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

def sum_of_squares(n):
    return sum([i**2 for i in range(1,n+1)])

def square_of_sum(n):
    return sum(range(1,n+1))**2

print square_of_sum(100) - sum_of_squares(100)

Project Euler #5

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 number that is evenly divisible by all of the numbers from 1 to 20?

# gcd: greatest common divisor
def gcd(m, n):
    while not n == 0:
        m, n = n, m%n
    return m

def find_smallest_divisible(n):
    m = n
    for i in range(2,n):
        if not m%i == 0:
            m = m * i / gcd(m, i)
    return m

print find_smallest_divisible(20)

Project Euler #4

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 × 99.

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

def make_p(i5, i4, i3):
    i0, i1, i2 = i5, i4, i3
    return i5*100000 + i4*10000 + i3*1000 + i2*100 + i1*10 +i0

def next(i5, i4, i3):
    if i3 > 0:
        return i5, i4, i3-1
    elif i4 > 0:
        return i5, i4-1, 9
    else:
        return i5-1, 9, 9

def prod_test(i543):
    m = make_p(*i543)
    for n in xrange(100, 1000):
        if (n*n > m):
            break
        elif m%n == 0 and m/n<1000:
            return True
    return False

# 997799 is the largest palindrome less than 999 X 999
# Let's start from here
i543 = (9, 9, 7)
while not prod_test(i543):
    i543 = next(*i543)
print make_p(*i543)

Project Euler #3

Problem 3

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

What is the largest prime factor of the number 600851475143 ?

def lpf(n):
    primes = [2]
    p = 2
    while True:
        while n%p == 0:
            n = n / p;
        if n==1:
            break;
        p = next_prime(primes)
        primes.append(p)
    return p

def next_prime(primes):
    if primes[-1] == 2:
        return 3
    i = primes[-1] + 2
    while True:
        iisprime = True
        for p in primes:
            if i%p == 0:
                iisprime = False
                break
        if iisprime:
            return i
        else:
            i = i+2

print lpf(600851475143)

Project Euler #2

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, …

Find the sum of all the even-valued terms in the sequence which do not exceed four million.

a, b = 1, 2
ans = 0
while b < 4000000:
    if b%2 == 0:
       ans += b 
    a, b = b, a+b
    
print ans