So the quest of solving Euler problems continues. I discovered projecteuler.net quite a bit ago and for past month I’ve been solving some of them bit by bit. In my last post “Solving Euler problems” I walked you through my solutions for problems 4 to 6. Unfortunately started saving the solutions since 4th problem, so… I don’t have first three solutions in code, but those problems are solved.

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?

My solution:

primes = []
def isPrime(x):
	for i in primes:
		if(x % i == 0):
			return 0
	return 1
	
primeCount = 0
i = 2;
while(primeCount <= 10001):
	if(isPrime(i)):
		print i
		primes.append(i)
		primeCount = primeCount + 1
		if(primeCount == 10001):
			print i
			break
	i = i + 1

This one seemed to be straightforward. You need to generate prime numbers and increment a variable every time a prime number is found until the 10001st prime number is found. When you find it - print it and stop.

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

My solution:

number = '7316717653133062491922511967442\
65747423553491949349698352031277450632623\
95783180169848018694788518438586156078911\
29494954595017379583319528532088055111254\
06987471585238630507156932909632952274430\
43557668966489504452445231617318564030987\
11121722383113622298934233803081353362766\
14282806444486645238749303589072962904915\
60440772390713810515859307960866701724271\
21883998797908792274921901699720888093776\
65727333001053367881220235421809751254540\
59475224352584907711670556013604839586446\
70632441572215539753697817977846174064955\
14929086256932197846862248283972241375657\
05605749026140797296865241453510047482166\
37048440319989000889524345065854122758866\
68811642717147992444292823086346567481391\
91231628245861786645835912456652947654568\
28489128831426076900422421902267105562632\
11111093705442175069416589604080719840385\
09624554443629812309878799272442849091888\
45801561660979191338754992005240636899125\
60717606058861164671094050775410022569831\
55200055935729725716362695618826704282524\
83600823257530420752963450'
length = len(number)
largest = 0
batch = 0
for i in range(length + 1 - 5):
	batch = number[i:i+5]
	result = 1;
	for j in batch:
		result *= int(j)
	if(result > largest):
		largest = result
print largest

Product basically means multiplying 5 consecutive numbers. This one seemed like a great way to play a bit with Python lists. Python has a neat way to slice lists and strings can be sliced like lists, so take a batch of 5 numbers, multiply them together, mark it if it is the largest so far and move onto the next batch. Just not forget to deal with different data types or you will be greeted with an error.

Problem 9

A Pythagorean triplet is a set of three natural numbers, a < b < c, for which, a2 + b2 = c2 For example, 32 + 42 = 9 + 16 = 25 = 52. There exists exactly one Pythagorean triplet for which a + b + c = 1000. Find the product abc.

My solution:

for a in range(1, 1000):
	for b in range(1, 1000):
		c = 1000 - a - b
		if(c ** 2 == a ** 2 + b ** 2):
			print str(a) + ' ' + str(b) + ' ' + str(c)

Since there is only a single Pythagorean triplet, looks like this one will be another bruteforce algorithm. Since a + b + c = 1000, we only need to generate 2 parameters (e.g. a and b), because we can calculate the other one (in this case c) using the given formula. c ** 2 is just a way of math.pow(c, 2). Since it is just a puzzle and it does not need to be that much optimized, I got the solution and left it as it is, but there is a problem with my solution that I noticed only now. When the number is found the program would still continue looking for such number, so stopping the program is necessary when a solution is found (Actually you can find this mistake being made by many beginners, but good programmers shouldn’t waste resources.)

Problem 13

Work out the first ten digits of the sum of the following one-hundred 50-digit numbers.

37107287533902102798797998220837590246510135740250 46376937677490009712648124896970078050417018260538 74324986199524741059474233309513058123726617309629 91942213363574161572522430563301811072406154908250 … Removed, you can find the number HERE …. 53503534226472524250874054075591789781264330331690

My solution:

numbers = """37107287533902102798797998220837590246510135740250
46376937677490009712648124896970078050417018260538
74324986199524741059474233309513058123726617309629
91942213363574161572522430563301811072406154908250
... Removed, you can find the number at http://projecteuler.net/index.php?section=problems&id=13 ....
53503534226472524250874054075591789781264330331690"""
numbers = numbers.split("\n")
sum = 0
for i in numbers:
	sum += int(i)
print sum

This one is really easy to do in Python. Insert the numbers into a variable (triple quotes were used, because data spans across multiple lines), split the big number by new line markers to get a list of 50-digit numbers, calculate the sum and that’s it. If you’d invest a bit more time, you might want to use Python list slicing to get only 10 first numbers, because my solution outputs whole number.

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 → 1 It 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.

My solution:

def getLength(n):
	length = 0
	while n > 1:
		if(n % 2 == 0):
			n /= 2
		else:
			n = n * 3 + 1
		length += 1
	return length + 1

longest = 0
number = 0
for i in range(1000000):
	x = getLength(i)
	if(x > longest):
		longest = x
		number = i
print str(number) + ' is ' + str(longest) + ' long'

Yet another bruteforce solution. GetLength function is created only to make the main loop a bit cleaner (less code to worry about). Go through numbers 0-1000000, calculate each one’s chain length and output the largest.

Problem 16

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?

My solution:

number = 2 ** 1000
number = str(number)
sum = 0
for i in number:
	sum += int(i)
print sum

Without computers it would be really hard or maybe even impossible to do that (I do not know of any method to do that, but I certainly don’t know everything), but now in just a few lines you can get the solution in under a second. Calculate the number, convert it to string to access it as a list and get the sum of numbers.

Problem 20

n! means n × (n − 1) × … × 3 × 2 × 1 For example, 10! = 10 × 9 × … × 3 × 2 × 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!

My solution:

import math
number = math.factorial(100)
number = str(number)
sum = 0
for i in number:
	sum += int(i)
print sum

This solution is very similar to the one I wrote for Problem 16. To calculate the 100! I used Python math module, last calculations are made with a simple loop.

That’s it for now. I have more solutions already (and more complex) and will post them here in next few days. I think there will be one or two posts of solutions and another one of my thoughts on ProjectEuler and my experience. Thanks for reading!