Tag: Python

Project Euler 25 (Python)

· Elliott · Project Euler, Python Solutions No comments - Tags: , ,

Question 25 from Project Euler:

The Fibonacci sequence is defined by the recurrence relation: Fn = Fn1 + Fn2, where F1 = 1 and F2 = 1. Hence the first 12 terms will be:
F1 = 1
F2 = 1
F3 = 2
F4 = 3
F5 = 5
F6 = 8
F7 = 13
F8 = 21
F9 = 34
F10 = 55
F11 = 89
F12 = 144
The 12th term, F12, is the first term to contain three digits.

What is the first term in the Fibonacci sequence to contain 1000 digits? 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

import time
start = time.time()
 
length = 0 ; x = 1 ; y = 2 ; n = z = 3
#y = previous term
#x is the term before that
#z = current term
#use n to count terms
while length < 1000:
    #create new term
    #reassign old values
    #set length
    z = x+y
    x, y = y, z
    length = len(str(z))
    n += 1
print n
 
print time.time()-start

Project Euler 24 (Python)

· Elliott · Project Euler, Python Solutions No comments - Tags: , ,

Question 24 from Project Euler:

A permutation is an ordered arrangement of objects. For example, 3124 is one possible permutation of the digits 1, 2, 3 and 4. If all of the permutations are listed numerically or alphabetically, we call it lexicographic order. The lexicographic permutations of 0, 1 and 2 are: 012 021 102 120 201 210

What is the millionth lexicographic permutation of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9? 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

import time, math
start = time.time()
 
def factorial(n):
    if n == 0:
        return 1
    else:
        return n * factorial(n-1)
 
target = 1000000
answer = []
digits = range(10)
nDigits = len(digits)
#the sorted permutation list will have 10! = 3628800 permutations
#solve a digit at a time
#narrowing the target and crossing off digits
while len(digits) != 1:
    x = factorial(nDigits-1)
    y = int(math.ceil(target/float(x)))
    answer.append(digits[y-1])
    digits.remove(digits[y-1])
    target -= x*(y-1)
    nDigits -= 1
#avoid being off by one digit
answer.append(digits[0])
 
print ''.join(map(str, answer))
 
print time.time()-start

Project Euler 23 (Python)

· Elliott · Project Euler, Python Solutions No comments - Tags: , ,

Question 23 from Project Euler:

A perfect number is a number for which the sum of its proper divisors is exactly equal to the number. For example, the sum of the proper divisors of 28 would be 1 + 2 + 4 + 7 + 14 = 28, which means that 28 is a perfect number.

A number n is called deficient if the sum of its proper divisors is less than n and it is called abundant if this sum exceeds n.

As 12 is the smallest abundant number, 1 + 2 + 3 + 4 + 6 = 16, the smallest number that can be written as the sum of two abundant numbers is 24. By mathematical analysis, it can be shown that all integers greater than 28123 can be written as the sum of two abundant numbers. However, this upper limit cannot be reduced any further by analysis even though it is known that the greatest number that cannot be expressed as the sum of two abundant numbers is less than this limit.

Find the sum of all the positive integers which cannot be written as the sum of two abundant numbers. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

import time
start = time.time() 
 
def sumDivisors(n, total=1):
    #look for divisors with modulus
    sqr = int((n**0.5)+1)
    for i in range(2, sqr):
        if n % i == 0:
            total += i + n / i
    if (n**0.5)+1 == sqr:
        total -= sqr
    return total
 
total = 0
abundants = set()
for n in range(1, 28123):
    #use sumDivisors to populate abundants set
    if sumDivisors(n) > n:
        abundants.add(n)
    #look in abundants for n - abundant
    #if it's not present then n is not the sum of two abundants
    if not any((n-a in abundants) for a in abundants):
        total += n
print total
 
print time.time()-start

Project Euler 22 (Python)

· Elliott · Project Euler, Python Solutions No comments - Tags: , ,

Question 22 from Project Euler:

Using names.txt, a 46K text file containing over five-thousand first names, begin by sorting it into alphabetical order. Then working out the alphabetical value for each name, multiply this value by its alphabetical position in the list to obtain a name score.

For example, when the list is sorted into alphabetical order, COLIN, which is worth 3 + 15 + 12 + 9 + 14 = 53, is the 938th name in the list. So, COLIN would obtain a score of 938 x 53 = 49714.

What is the total of all the name scores in the file? 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

import time, string
start = time.time() 
 
names = open("names.txt").read().replace('"', '').split(',')
names.sort()
 
letterScores={'a':1, 'b':2, 'c':3, 'd':4, 'e':5, 'f':6, 
'g':7, 'h':8, 'i':9, 'j':10, 'k':11, 'l':12, 'm':13, 'n':14, 
'o':15, 'p':16, 'q':17, 'r':18, 's':19, 't':20, 'u':21, 
'v':22, 'w':23, 'x':24, 'y':25, 'z':26}
 
#loop through names, nest to loop chars
#use char and letterScores to tally up the total
total = 0
for index, name in enumerate(names):
    nameScore = 0
    for letter in range(len(name)):
        nameScore += letterScores[string.lower(name[letter])]
    total += nameScore * (index+1)
print total    
 
print time.time()-start

Project Euler 21 (Python)

· Elliott · Project Euler, Python Solutions No comments - Tags: , ,

Question 21 from Project Euler:

Let d(n) be defined as the sum of proper divisors of n (numbers less than n which divide evenly into n). If d(a) = b and d(b) = a, where a is not equal to b, then a and b are an amicable pair and each of a and b are called amicable numbers.

For example, the proper divisors of 220 are 1, 2, 4, 5, 10, 11, 20, 22, 44, 55 and 110; therefore d(220) = 284. The proper divisors of 284 are 1, 2, 4, 71 and 142; so d(284) = 220.

Evaluate the sum of all the amicable numbers under 10000. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

import time
start = time.time() 
 
def sumDivisors(n, total=1):
    #look for divisors with modulus
    for i in range(2, int(n**0.5)+1):
        if n % i == 0:
            total += i + n / i
    return total
 
total = 0
for i in range(2, 10000):
    #test for amicables
    if sumDivisors(i) > i and sumDivisors(sumDivisors(i)) == i:
        #tally up both numbers
        total += sumDivisors(i)+i
 
print total
 
print time.time()-start

Project Euler 20 (Python)

· Elliott · Project Euler, Python Solutions No comments - Tags: , ,

Question 20 from Project Euler:

n! means n x (n – 1) x … 3 x 2 x 1

For example, 10! = 10 x 9 x … 3 x 2 x 1 = 3628800,
and the sum of the digits in the number 10! is 3 + 6 + 2 + 8 + 8 + 0 + 0 = 27.

Find the sum of the digits in the number 100! 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

import time
start = time.time()
 
#find the number
n = 1
for i in range(1, 100):
    n = n * i
 
#convert to string
#convert chars to ints and add them to total
nStr = str(n)
answer = 0
for i in range(len(nStr)):
    answer += int(nStr[i])
 
print answer
 
print time.time()-start

Project Euler 19 (Python)

· Elliott · Project Euler, Python Solutions No comments - Tags: , ,

Question 19 from Project Euler:

You are given the following information, but you may prefer to do some research for yourself.

1 Jan 1900 was a Monday.
Thirty days has September,
April, June and November.
All the rest have thirty-one,
Saving February alone,
Which has twenty-eight, rain or shine.
And on leap years, twenty-nine.
A leap year occurs on any year evenly divisible by 4, but not on a century unless it is divisible by 400.

How many Sundays fell on the first of the month during the twentieth century (1 Jan 1901 to 31 Dec 2000)? 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

import time, datetime
start = time.time()
 
#loop years and nest for months
#get datetime object for first day
#test for sundays
total = 0
for year in range(1901, 2001):
    for month in range(1, 13):
        day = datetime.date(year, month, 1)
        if day.weekday() == 6:
            total += 1    
print total 
 
print time.time()-start

Project Euler 18 (Python)

· Elliott · Project Euler, Python Solutions No comments - Tags: , ,

Question 18 from Project Euler:

By starting at the top of the triangle below and moving to adjacent numbers on the row below, the maximum total from top to bottom is 23.
3
7 4
2 4 6
8 5 9 3

That is, 3 + 7 + 4 + 9 = 23.

Find the maximum total from top to bottom of the triangle below:
75
95 64
17 47 82
18 35 87 10
20 04 82 47 65
19 01 23 75 03 34
88 02 77 73 07 63 67
99 65 04 28 06 16 70 92
41 41 26 56 83 40 80 70 33
41 48 72 33 47 32 37 16 94 29
53 71 44 65 25 43 91 52 97 51 14
70 11 33 28 77 73 17 78 39 68 17 57
91 71 52 38 17 14 91 43 58 50 27 29 48
63 66 04 68 89 53 67 30 73 16 69 87 40 31
04 62 98 27 23 09 70 98 73 93 38 53 60 04 23 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

import time
start = time.time()
 
triangle = [
    [75,],
    [95, 64,],
    [17, 47, 82,],
    [18, 35, 87, 10,],
    [20,  4, 82, 47, 65,],
    [19,  1, 23, 75,  3, 34,],
    [88,  2, 77, 73,  7, 63, 67,],
    [99, 65,  4, 28,  6, 16, 70, 92,],
    [41, 41, 26, 56, 83, 40, 80, 70, 33,],
    [41, 48, 72, 33, 47, 32, 37, 16, 94, 29,],
    [53, 71, 44, 65, 25, 43, 91, 52, 97, 51, 14,],
    [70, 11, 33, 28, 77, 73, 17, 78, 39, 68, 17, 57,],
    [91, 71, 52, 38, 17, 14, 91, 43, 58, 50, 27, 29, 48,],
    [63, 66,  4, 68, 89, 53, 67, 30, 73, 16, 69, 87, 40, 31,],
    [ 4, 62, 98, 27, 23,  9, 70, 98, 73, 93, 38, 53, 60,  4, 23,],
    ]
 
#work up from the bottom row
for row in range(len(triangle)-1, 0, -1):
    for col in range(row):
        #assign the number in the row above each adjacent pair
        #to the greatest value of that pair
        triangle[row-1][col] += max(triangle[row][col], triangle[row][col+1])
 
print triangle[0][0]
 
print time.time()-start

Project Euler 17 (Python)

· Elliott · Project Euler, Python Solutions No comments - Tags: , ,

Question 17 from Project Euler:

If the numbers 1 to 5 are written out in words: one, two, three, four, five, then there are 3 + 3 + 5 + 4 + 4 = 19 letters used in total.

If all the numbers from 1 to 1000 (one thousand) inclusive were written out in words, how many letters would be used? 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

import time
start = time.time()
 
def num2txt(n):
    if n == 1000:
        return len('onethousand')
 
    words = {1:'one',2:'two',3:'three',4:'four',5:'five',6:'six',7:'seven',
    8:'eight',9:'nine',10:'ten',11:'eleven',12:'twelve',13:'thirteen',
    14:'fourteen',15:'fifteen',16:'sixteen',17:'seventeen',
    18:'eighteen',19:'nineteen',20:'twenty',30:'thirty',40:'forty',
    50:'fifty',60:'sixty',70:'seventy',80:'eighty',90:'ninety',
    100:'hundred',1000:'thousand'}
 
    total = 0
    hundreds = n / 100 #digit from hundreds column
    tens = n % 100 / 10 #digit from tens column
    ones = n % 10 #digit from ones column
 
    if hundreds > 0: #3 digit number
        total += len(words[hundreds]) #digit as text (eg: one)
        total += len(words[100]) #hundred
        if tens > 1: #two digit number > 19
            total += len(words[tens*10])+3 #+3 accounts for "and"
            if ones > 0:
                total += len(words[ones])
        elif tens == 1: #teen or ten/eleven/twelve
            total += len(words[ones+10])+3
        elif ones > 0: #and digit (eg: "andone")
            total += len(words[ones])+3
    elif tens > 0: #2 digit number
        if tens == 1: #teen or ten/eleven/twelve
            total += len(words[ones+10])
        else:
            if tens > 1: #two digit number > 19
                total += len(words[tens*10])
                if ones > 0:
                    total += len(words[ones])
    else: #single digit number
        total += len(words[ones])
 
    return total
 
print sum(map(num2txt, range(1, 1001)))
 
print time.time()-start

Project Euler 16 (Python)

· Elliott · Project Euler, Python Solutions No comments - Tags: , ,

Question 16 from Project Euler:

215 = 32768 and the sum of its digits is 3 + 2 + 7 + 6 + 8 = 26.

What is the sum of the digits of the number 21000? 

1
2
3
4
5
6
7
8
9
10
11
12

import time
start = time.time()
 
#set value as string
numStr = str(2**1000)
#loop by char, convert to int and add to total
total = 0
for i in range(len(numStr)):
    total += int(numStr[i])
print total
 
print time.time()-start