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.
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?
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.
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?
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.
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.
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 .
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.
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.
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?
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!
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.)
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.
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.
import math primes =  def genPrimes(n): if n==2: return  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 +[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.
Triangle, pentagonal, and hexagonal numbers are generated by the following formulae:
1, 3, 6, 10, 15, …
1, 5, 12, 22, 35, …
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.
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.
The series, 11 + 22 + 33 + … + 1010 = 10405071317. Find the last ten digits of the series, 11 + 22 + 33 + … + 10001000.
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.
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?
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.
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?
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.
The first known prime found to exceed one million digits was discovered in 1999, and is a Mersenne prime of the form 269725931; it contains exactly 2,098,960 digits. Subsequently other Mersenne primes, of the form 2p1, have been found which contain more digits. However, in 2004 there was found a massive non-Mersenne prime which contains 2,357,207 digits: 2843327830457+1. Find the last ten digits of this prime number.
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!
Subscribe via RSS