18 June, 2008
Project Euler: Problem 14
The following iterative sequence is defined for the set of positive integers:
n → n/2 (n is even)
n → 3n + 1 (n is odd)Using the rule above and starting with 13, we generate the following sequence:
13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1It can be seen that this sequence (starting at 13 and finishing at 1) contains 10 terms. Although it has not been proved yet (Collatz Problem), it is thought that all starting numbers finish at 1.
Which starting number, under one million, produces the longest chain?
NOTE: Once the chain starts the terms are allowed to go above one million.
A solution:
In order to not compute the entire sequence every time, the variable history is used to keep track of sequence lengths as we go. history[i] will be the length of the sequence that starts with i.
def next(n): # computes next term in the sequence
if n % 2 == 0:
return n/2
else:
return 3*n+1
history = [0,1]
for i in range(2,1000000):
num_terms = 0
num = i
done = False
while num > 1 and not done:
num = next(num)
if num < len(history): # number has been hit previously,
# so the length of the rest of the path is known.
num_terms += history[num]
done = True
num_terms += 1
history.append(num_terms)
print history.index(max(history))
17 June, 2008
Project Euler: Problem 13
Work out the first ten digits of the sum of the following one-hundred 50-digit numbers.
37107287533902102798797998220837590246510135740250
46376937677490009712648124896970078050417018260538
74324986199524741059474233309513058123726617309629
91942213363574161572522430563301811072406154908250
…
20849603980134001723930671666823555245252804609722
53503534226472524250874054075591789781264330331690
A solution:
Copy the list of numbers and save them in a text file (here, Euler13number.txt). Then things are pretty easy, thanks to Python’s magic handling of large numbers.
file = open('Euler13number.txt', 'r')
a = [int(line) for line in file]
b = str(sum(a))
print b[:10]
file.close()
Or, for an even more condensed version:
file = open('Euler13number.txt', 'r')
print str(sum([int(line) for line in file]))[:10]
file.close()
14 June, 2008
Project Euler: Problem 12
The sequence of triangle numbers is generated by adding the natural numbers. So the 7th triangle number would be 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. The first ten terms would be:
1, 3, 6, 10, 15, 21, 28, 36, 45, 55, …
Let us list the factors of the first seven triangle numbers:
1: 1
3: 1,3
6: 1,2,3,6
10: 1,2,5,10
15: 1,3,5,15
21: 1,3,7,21
28: 1,2,4,7,14,28We can see that 28 is the first triangle number to have over five divisors.
What is the value of the first triangle number to have over five hundred divisors?
A solution:
Below, the function prime_factors is given here.
from factor import prime_factors
from operator import mul
triangle_num = 3 # starting place: 1+2=3
max_factors = 2
to_add = 2
while max_factors <= 500:
to_add += 1
triangle_num += to_add
factors = prime_factors(triangle_num)
count = []
while len(factors) != 0:
count.append(factors.count(factors[0])) # how many of the first factor
del factors[:count[-1]] # take out all instances of first factor
# count is now a list of how many of each factor
# e.g. for 28 = 2*2*7, count = [2,1]
# number of all factors is then given by (2+1)*(1+1) because each factor
# will have the form (2**x)*(7**y) where x = 0 or 1 or 2, y = 0 or 1
not_just_prime_factors = reduce(mul, [count[i]+1
for i in range(len(count))])
max_factors = max(not_just_prime_factors, max_factors)
print triangle_num
print max_factors
5 June, 2008
Project Euler: Problem 11
Big block o’ numbers: (yeah, I’m paraphrasing)
08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08
49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00
81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65
52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 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 03 45 02 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 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21
24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72
21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95
78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92
16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57
86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58
19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40
04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66
88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69
04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36
20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16
20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54
01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48What is the greatest product of four numbers in any direction (up, down, left, right, or diagonally) in the 20×20 grid?
A solution:
from operator import mul
a = # the big block o' numbers, as a list of lists.
# Each element in a is a row of the grid.
max_prod = 0
for i in range(len(a)): # loop over rows
for j in range(len(a[i])-4): # loop over elements in single row
max_prod = max(reduce(mul, (a[i][j+k] for k in range(4))), max_prod)
# test vertically
for i in range(len(a[0])): # loop over columns
for j in range(len(a)-4): # loop over elements in single column
max_prod = max(reduce(mul, (a[j+k][i] for k in range(4))), max_prod)
# test diagonally
for i in range(len(a)-4): # loop over rows
for j in range(len(a[i])-4): # loop over elements in single row
max_prod = max(reduce(mul, (a[i+k][j+k] for k in range(4))), max_prod)
max_prod = max(reduce(mul, (a[i+3-k][j+k] for k in
range(3, -1, -1))), max_prod)
print max_prod
Putting it into a single loop would be better, but I was too lazy to figure out the conditions.
4 June, 2008
More Puzzles
In addition to the Project Euler problems that I’ve been working through, I came across The Python Challenge yesterday (via Code Ghar). It’s a series of programming riddles, and it looks like a nice complement to the all-math Project Euler. I’m at level 5 and so far the challenges have involved string manipulation, regular expressions, getting source code from websites, and other fun stuff that Project Euler won’t expose me to.
If you’re looking for a fun way to learn, check it out.
3 June, 2008
Project Euler: 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.
A solution:
import math
def isPrime(num):
if type(num) != int: return False
if num == 2: return True
if num < 2 or num % 2 == 0: return False
return not any(num % i == 0 for i in range(3, int(math.sqrt(num))+1, 2))
sum = 0
for i in range(2,2000000):
if isPrime(i): sum += i
print sum
Straightforward, yes?
Project Euler: Problem 9
A Pythagorean triplet is a set of three natural numbers, a < b < c, for which,
a2 + b2 = c2For example, 32 + 42 = 9 + 16 = 25 = 52.
There exists exactly one Pythagorean triplet for which a + b + c = 1000.
Find the product abc.
A solution:
First, the math part. We have two equations in three unknowns. Eliminating c gives 2000a+2000b-2ab=1000000. Then, solving for a gives a = (500000-1000b)/(1000-b). Now we can loop through values for b, looking for one that will give us a natural number result for a.
limit = 1000 # gotta stop somewhere
for i in range(1,limit):
if (500000 - 1000*i)%(1000-i) == 0: # ie, will make a natural number
b = i
a = (500000 - 1000*b)/(1000 - b)
c = 1000 - a - b
print "a = %d, b = %d, c = %d" %(a, b, c)
print "product is %d" %(a*b*c)
break
if i == limit-1: print "solution not found, try a higher limit"
2 June, 2008
Project Euler: 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
A solution:
from operator import mul
num = {that big number}
str_num = str(num) # turn the int to a string for indexing and iteration
product = 0
for i in range(len(str_num)-4):
product = max(reduce(mul, [int(str_num[j]) for j in range(i,i+5)]),
product)
print product
Python doesn’t allow for integers to be indexed, but it’s easy enough to switch over to a string for the indexing, and back to int for the math.
Project Euler: 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.
A solution:
biggest_palindrome = 0
for i in range(100,1000):
for j in range(100,1000):
num = i*j
if int(str(num)[::-1]) == num and num > biggest_palindrome:
biggest_palindrome = num
print "biggest palindrome is %d" % biggest_palindrome
Pretty straightforward, brute-force way to do it. Though knowing how to reverse a string (with str(a)[::-1]) is a neat trick.
Project Euler: Problem 3
The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143 ?
A solution:
We can use the factorize function written for Problem 5, but it needs to be modified. The number to be factored is so large that the upper limit of numbers that need to be checked as factors is of type long, rather than of type int. The range() function doesn’t like numbers that large (unsurprisingly, as that would be a very very very long list to store), so a while loop needs to be used instead of a for loop.
def factorize(num):
powers = []
limit = (num/2)+1
i = 2
while i <= limit:
while num % i == 0: # ie, i is a factor of num
powers.append(i)
num = num/i
i += 1
if num == 1: break # ie, all factors have been found
if len(powers) == 0: powers.append(num) # num is prime
return powers
This function can then be used to find the prime factors of the given number.
There are ways this method can be improved: if the factor 2 is handled separately before the while loop, then the loop only needs to be done for odd numbers, using half of the iterations. As well, a separate function that tests for primality could be called at the beginning: since a prime test only needs to check up to sqrt(number) instead of number/2, it can be a lot faster to know if the number itself is prime, rather than trying to find all of its factors.
