In my previous posts I have reviewed my solutions for 10 problems (problems 4-20). I have skipped some problems, for some solutions were lost. Now problems started to get more difficult and solutions had to get longer.

Problem 24

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?

My solution:

import itertools
x = 0
for i in list(itertools.permutations(range(10))):
	x += 1
	if(x == 1000000):
		print i
		break

Python has a really nice itertools library. I learned about it from a Python talk on “Easy AI with Python” (AI - Artificial Intelligence.) Count the number with each permutation and on the 1000000th one output it.

Problem 29

Consider all integer combinations of a__b for 2 ≤ a ≤ 5 and 2 ≤ b ≤ 5: 22=4, 23=8, 24=16, 25=32 32=9, 33=27, 34=81, 35=243 42=16, 43=64, 44=256, 45=1024 52=25, 53=125, 54=625, 55=3125 If they are then placed in numerical order, with any repeats removed, we get the following sequence of 15 distinct terms: 4, 8, 9, 16, 25, 27, 32, 64, 81, 125, 243, 256, 625, 1024, 3125 How many distinct terms are in the sequence generated by a__b for 2 ≤ a ≤ 100 and 2 ≤ b ≤ 100?

My solution:

numbers = []
for a in range(2, 101):
	for b in range(2, 101):
		if(not(a ** b in numbers)):
			numbers.append(a ** b)
print len(numbers)

Generate a list of distinct a ** b numbers, print out the length.

Problem 30

Surprisingly there are only three numbers that can be written as the sum of fourth powers of their digits: 1634 = 14 + 64 + 34 + 44 8208 = 84 + 24 + 04 + 84 9474 = 94 + 44 + 74 + 44 As 1 = 14 is not a sum it is not included. The sum of these numbers is 1634 + 8208 + 9474 = 19316. Find the sum of all the numbers that can be written as the sum of fifth powers of their digits.

My solution:

def canBeWritten(x):
	nums = str(x)
	sum = 0
	for i in nums:
		sum += int(i) ** 5
	if(sum == x):
		return True
	else:
		return False
found = []
for a in range(2, 1000000):
	if(canBeWritten(a)):
		found.append(a)
		print a
print ''
print sum(found)

Function that checks if the number can be written that way makes everything a bit cleaner. Loop through numbers (I didn’t see a point of looping over 1M, but if the answer would have been incorrect - I would have to do it), add required numbers to the list and calculate the sum based on that. You can skip using the list, but I wanted to see which numbers can be written that way .

Problem 34

145 is a curious number, as 1! + 4! + 5! = 1 + 24 + 120 = 145. Find the sum of all numbers which are equal to the sum of the factorial of their digits. Note: as 1! = 1 and 2! = 2 are not sums they are not included.

My solution:

import math
def sumEqualFactorial(x):
	number = str(x)
	factorialSum = 0
	for i in number:
		factorialSum += math.factorial(int(i))
	if(factorialSum == x):
		return True
	else:
		return False
suma = 0
for a in range(3, 1000000):
	if(sumEqualFactorial(a)):
		suma += a
print suma

To calculate the sum of each numbers factorials I converted the number to string for easier handling and used math.factorial() to calculate sum of factorials. This one seems to be straightforward.

Problem 35

The number, 197, is called a circular prime because all rotations of the digits: 197, 971, and 719, are themselves prime. There are thirteen such primes below 100: 2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, and 97. How many circular primes are there below one million?

My solution:

import math
primes = []
def isPrime(x):
	if x == 1:
		return False
	for z in primes:
		if(z == x):
			continue
		if(x % z == 0):
			return False
	return True
def isCircularPrime(x):
	number = list(str(x))
	for i in range(1, len(number)):
		y = number.pop(0)
		number.append(y)
		if(not(isPrime(int("".join(number))))):
			return False
	return True
for i in range(2, 1000000):
	if(isPrime(i)):
		primes.append(i)
count = 0
for a in primes:
	if(isCircularPrime(a)):
		count += 1
print count

This is a bit more complex at a first glance and there’s a bit more code, but actually the algorithm is relatively simple. Firstly we calculate prime numbers up to 1 million. Then we loop through each prime number to check if it is a circular prime. To check that function does some permutations transferring the number from the beginning to the end and each time checking if the number is prime. If the number is prime for all of permutations - the number is a circular prime. Increment the counter and move on!

Problem 36

The decimal number, 585 = 10010010012 (binary), is palindromic in both bases. Find the sum of all numbers, less than one million, which are palindromic in base 10 and base 2. (Please note that the palindromic number, in either base, may not include leading zeros.)

My solution:

def isPalindromic(x):
	binary = bin(x)
	binary = binary[2:]
	number = str(x)
	reversedBinary = binary[::-1]
	reversedNumber = number[::-1]
	if(binary == reversedBinary and number == reversedNumber):
		return True
	else:
		return False
sum = 0
for i in range(1, 1000000):
	if(isPalindromic(i)):
		sum += i
print sum

Loop through each number up to 1M, calculate binary for each number, reverse binary and the number itself and check for validity. “binary[2:]” just removes 0b symbols, that indicate, that the number is binary. “binary[::-1]” reverses the string/list.

Problem 37

The number 3797 has an interesting property. Being prime itself, it is possible to continuously remove digits from left to right, and remain prime at each stage: 3797, 797, 97, and 7. Similarly we can work from right to left: 3797, 379, 37, and 3. Find the sum of the only eleven primes that are both truncatable from left to right and right to left. NOTE: 2, 3, 5, and 7 are not considered to be truncatable primes.

My solution:

import math
primes = []
def genPrimes(n): 
	if n==2: return [2]
	elif n<2: return []
	s=range(3,n+1,2)
	mroot = n ** 0.5
	half=(n+1)/2-1
	i=0
	m=3
	while m <= mroot:
		if s[i]:
			j=(m*m-3)/2
			s[j]=0
			while j>half:
				s[j]=0
				j+=m
		i=i+1
		m=2*i+3
	return [2]+[x for x in s if x]
def isPrime(x):
	if x == 1:
		return False
	for z in primes:
		if(z == x):
			continue
		if(x % z == 0):
			return False
	return True

def isTruncatable(x):
	number = str(x)
	length = len(number)
	for i in range(0, length): #truncate from left
		if(not(isPrime(int(number[i:])))):
			return False
	for i in range(0, length):
		if(not(isPrime(int(number[:(length - i)])))):
			return False
	return True
		
primes = genPrimes(1000000)
print primes
sum = 0
for a in range(8, 1000000):
	if(isTruncatable(a)):
		sum += a
		print a
print sum

Functions to generate prime numbers that I wrote myself weren’t that effective and fast, so I looked up a more elaborate solution for that (I know, I’m a bit cheating here), but that increased the speed by quite a bit. To check if the number is truncatable,  once again I’ve used python string. The function loops forwards and backwards through the number each time eliminating one more number.

Problem 45

Triangle, pentagonal, and hexagonal numbers are generated by the following formulae:

Triangle

T_n_=n(n+1)/2

1, 3, 6, 10, 15, …

Pentagonal

P_n_=n(3n−1)/2

1, 5, 12, 22, 35, …

Hexagonal

H_n_=n(2n−1)

1, 6, 15, 28, 45, …

It can be verified that T285 = P165 = H143 = 40755. Find the next triangle number that is also pentagonal and hexagonal.

My solution:

triangles = []
pentagonals = []
hexagonals = []
for i in range(1, 100000):
	triangles.append(i * (i + 1) / 2)
	pentagonals.append(i * (3 * i - 1) / 2)
	hexagonals.append(i * (2 * i - 1))
for i in triangles:
	if((i in pentagonals) and (i in hexagonals)):
		print i

To make things easier we generate lists of triangles, pentagonals and hexagonals. After that we loop through each number in triangles list (checking based on hexagonals rather than triangles would make it more efficient - less numbers to check) we only need to check if the number exists in other lists.

Problem 48

The series, 11 + 22 + 33 + … + 1010 = 10405071317. Find the last ten digits of the series, 11 + 22 + 33 + … + 10001000.

My solution:

import math
sum = 0
for i in range(1000):
	sum += i ** i
sum = str(sum)
print sum[-10:]

Loop through numbers up to 1000, calculate their powers and calculate their sum. Use Python list slicing to get the last 10 numbers easily.

Problem 56

A googol (10100) is a massive number: one followed by one-hundred zeros; 100100 is almost unimaginably large: one followed by two-hundred zeros. Despite their size, the sum of the digits in each number is only 1. Considering natural numbers of the form, ab, where a, b < 100, what is the maximum digital sum?

My solution:

maximum = 0
for a in range(1, 100):
	for b in range (1, 100):
		number = str(a ** b)
		number = [int(i) for i in number]
		suma = sum(number)
		if(suma > maximum):
			maximum = suma
print maximum

Use two loops to calculate a ** b. Convert a ** b to string and using Python list comprehension convert each element to an integer, thus creating a list of integers. Find the sum of those integers and that’s it.

Problem 92

A number chain is created by continuously adding the square of the digits in a number to form a new number until it has been seen before. For example,

44 → 32 → 13 → 10 → 1 → 1 85 → 89 → 145 → 42 → 20 → 4 → 16 → 37 → 58 → 89

Therefore any chain that arrives at 1 or 89 will become stuck in an endless loop. What is most amazing is that EVERY starting number will eventually arrive at 1 or 89. How many starting numbers below ten million will arrive at 89?

My solution:

def arrivesAt89(x):
	while(True):
		a = x
		x = sum([int(i) ** 2 for i in str(x)])
		if(a == x):
			return False
		if(x == 89):
			return True
count = 0
for i in range(1, 10000000):
	print i
	if(arrivesAt89(i)):
		count += 1
print count

To calculate the chain we use a loop. Just to make sure that we’re not stuck on the same number (e.g. 1 is the end of the chain), we check if current calculated one is not equal to previous one. If it is equal to previous one (such as we arrived at one) - the chain does not arrive at 89. If we detect number 89 in the chain, we break the loop immediately, because that is our goal.

Problem 97

The first known prime found to exceed one million digits was discovered in 1999, and is a Mersenne prime of the form 26972593−1; it contains exactly 2,098,960 digits. Subsequently other Mersenne primes, of the form 2p−1, have been found which contain more digits. However, in 2004 there was found a massive non-Mersenne prime which contains 2,357,207 digits: 28433×27830457+1. Find the last ten digits of this prime number.

My solution:

number = str(28433 * (2 ** 7830457) + 1)
print number[-10:]

The solution is shorter than the problem itself. We calculate the number and turn it into a string to get access to Python list slicing. Slice last ten digits and print them out.

At this point I have solved 29 problems and probably posted not as many solutions, but the goal is near. I will be posting another post soon, which will probably be the last one about my ProjectEuler solutions. Thanks for reading!