The Inner Machinations of Walker

Project Euler Problem #37

Problem #37 is yet another question on Project Euler that involves manipulating digits in primes. The question reads:

Project Euler Problem 37: Truncatable primes
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.

If you’ve seen my solution to some of the last few questions that have involved prime numbers, you can probably guess what I’m going to use.

Solution #1: Sieve Approach

We simply guess and check an upper bound for the 11th truncatable prime until we have found all of them. We use a Sieve of Eratosthenes to list all primes up to the upper bound and then check all primes less than the upper bound to find any ones that are truncatable. Here is an implementation of this approach in Python 2.7:

 '''
 Author: Walker Kroubalkian
 Sieve Approach to Project Euler Problem #37
 '''
 
 import time
 
 def sieveEratosthenes(n):
     myPrimes = []
     
     primePossible = [True]*(n+1)
     primePossible[0] = False
     primePossible[1] = False
     
     for (i,possible) in enumerate(primePossible):
         if possible:
             for x in range(i*i, (n+1), i):
                 primePossible[x] = False
             myPrimes.append(i)
 
     return [primePossible,myPrimes]
 
 def projectEulerProblemThirtySeven(n):
     allPrimeInfo = sieveEratosthenes(n)
     primePossible = allPrimeInfo[0]
     myPrimes = allPrimeInfo[1]
     
     truncatablePrimes = []
     
     for p in myPrimes:
         if(p>10):
             s = str(p)
             found = False
             for i in range(1,len(s)):
                 if((not primePossible[int(s[i:])]) or (not primePossible[int(s[0:i])])):
                     found = True
                     break
             if not found:
                 truncatablePrimes.append(p)
     
     if(len(truncatablePrimes)==11):
         total = 0
         for x in truncatablePrimes:
             total+=x
         return total
     else:
         return -1
 
 start = time.time()
 print projectEulerProblemThirtySeven(1000000)
 print ("--- %s seconds ---" % (time.time()-start))
 
 '''
 Prints

 748317
 --- 0.2643699646 seconds ---
 
 for input of n = 1000000
 '''

As shown above, the Sieve of Eratosthenes is very good when determining properties about large primes that involve smaller primes.

Thanks for reading!

Project Euler Problem #36

Problem #36 is one of the many problems on Project Euler that involves binary. The question reads:

Project Euler Problem 36: Double-base palindromes
The decimal number, 585 = 1001001001_2 (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.)

This problem is not particularly interesting, as we have already encountered many problems involving palindromes. Here is my solution:

Solution #1: Brute Force Approach

We simply iterate through all of the numbers less than 1,000,000 and check if each one is a palindrome in both base 10 and base 2. Here’s an implementation of this method in Python 2.7:

 '''
 Author: Walker Kroubalkian
 Brute Force Approach to Project Euler Problem #36
 '''

 import time

 def isPalindrome(x):
     return x%10!=0 and str(x) == str(x)[::-1]

 def projectEulerProblemThirtySix(n):
     total = 0
     for i in range(1,n):
         if(isPalindrome(i) and isPalindrome(int(bin(i)[2:]))):
             total+=i
     return total

 start = time.time()
 print projectEulerProblemThirtySix(1000000)
 print ("--- %s seconds ---" % (time.time()-start))
 '''

 Prints

 872187
 --- 0.415219783783 seconds ---

 for input of n = 1000000
 '''

As shown above, Python has very simple means of handling strings, and this can be used to detect palindromes without too much code. Python also has relatively simple means of converting numbers to and from binary. My solution to this problem probably isn’t as efficient as it could be, and I may come back to it eventually.

Thanks for reading! See you tomorrow.

Project Euler Problem #35:

Problem #35 is one of the many questions on Project Euler that involves manipulating digits in primes. Here is the question:

Project Euler Problem 35: Circular Primes
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?

If you’ve seen any of my solutions to other problems involving counting primes less than an upper bound, you can probably guess what my solution will be.

Solution #1: Sieve Approach

We simply use the Sieve of Eratosthenes to list all primes less than or equal to 1,000,000 and then check each one for the circular ability. Here is an implementation of this method in Python 2.7:

 '''
 Author: Walker Kroubalkian
 Sieve Approach to Project Euler Problem #35
 '''

 import time

 def sieveEratosthenes(n):
     myPrimes = []
     primePossible = [True]*(n+1)
     primePossible[0] = False
     primePossible[1] = False

     for (i,possible) in enumerate(primePossible):
         if possible:
             for x in range(i*i, (n+1), i):
                 primePossible[x] = False
             myPrimes.append(i)

     return [primePossible,myPrimes]

 def projectEulerProblemThirtyFive(n):
     allPrimeInfo = sieveEratosthenes(n)
     primePossible = allPrimeInfo[0]
     myPrimes = allPrimeInfo[1]

     total = 0

     for myPrime in myPrimes:
         theString = str(myPrime)
         found = False
         for x in range(len(theString)):
             if(not primePossible[int(theString[x:]+theString[0:x])]):
                 found = True
                 break
         if(not found):
             total+=1
     return total

 start = time.time()
 print projectEulerProblemThirtyFive(1000000)
 print ("--- %s seconds ---" % (time.time()-start))

 '''
 Prints

 55
 --- 0.270114898682 seconds ---

 for input of n = 1000000
 '''

As shown above, the Sieve of Eratosthenes continues to be invaluable for complex problems involving counting primes.

Thanks for reading! See you tomorrow.

Project Euler Problem #34:

Problem #34 is one of the many Project Euler problems that involves factorials. It involves an obscure type of number called an factorion. Factorions are numbers for which the sum of the factorials of the digits is equal to the number itself. The question reads:

Project Euler Problem #34: Digit factorials
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.

Once again, my solution for this problem involves iterative brute force.

Solution #1: Brute Force Approach

First we calculate an upper bound for the maximum number which is equal to the sum of the factorials of its digits. Clearly the sum of the factorials of the digits of a number is maximized when all of the digits are 9 for a fixed number of digits. Consequently, it suffices to find the minimum number of digits n for which a number formed with n digits of 9 is greater than the product of 9! and n. This can be done easily without much inefficiency.

Once the upper bound is calculated, we simply check every number less than the upper bound for this property. Here is an implementation of this approach in Python 2.7:

 '''
 Author: Walker Kroubalkian
 Brute Force Approach to Project Euler Problem #34
 '''

 import time

 def factorial(n):
     total = 1
     for c in range(2,n+1):
         total*=c
     return total

 def projectEulerProblemThirtyFour(n):
     factorials = []
     for x in range(10):
         factorials.append(factorial(x))
     a = 1
     while((10*a) - 1 < factorials[n]*a):
         a+=1
     total = 0
     final = factorials[n] * a
     for c in range(3,final+1):
         myString = str(c)
         subTotal = 0
         for x in myString:
             subTotal+=factorials[int(x)]
         if(subTotal==c):
             total+=c
     return total

 start = time.time()
 print projectEulerProblemThirtyFour(9)
 print ("--- %s seconds ---" % (time.time()-start))

 '''
 Prints

 40730
 --- 6.35254812241 seconds ---

 for input of n = 9
 '''

This solution clearly isn’t very efficient as it does not filter the numbers that need to be checked at all. However, it does run in under 10 seconds, which is better than I can say for some of my later solutions. I may come back to this problem at some point to search for a more efficient solution.

Thanks for reading!

Project Euler Problem #33:

Problem #33 is yet another question that can be killed with basic brute force. The question reads:

Project Euler Problem 33: Digit cancelling fractions
The fraction 49/98 is a curious fraction, as an inexperienced mathematician in attempting to simplify it may incorrectly believe that 49/98 = 4/8, which is correct, is obtained by cancelling the 9s.

We shall consider fractions like, 30/50 = 3/5, to be trivial examples.

There are exactly four non-trivial examples of this type of fractions, less than one in value, and containing two digits in the numerator and denominator.

If the product of these four fractions is given in its lowest common terms, find the value of the denominator.

You can probably guess what my solution to this problem will be if you have been reading the last few blog entries.

Solution #1: Brute Force Approach

We simply iterate through all pairs of two-digit integers. There are at most 90*90 = 8100 pairs to worry about, so this iteration is very simple. The complicated part is finding each case for equal digits to appear in the numerator and the denominator. Once all of the fractions are found, it is a simple matter of multiplying all of the numerators and multiplying all of the denominators and dividing the denominator product . by the greatest common divisor of the numerator and the denominator. This greatest common divisor can be determined by using the Euclidean Algorithm. Here is an implementation of this approach in Python 2.7:

 '''
 Author: Walker Kroubalkian
 Brute Force Approach to Project Euler Problem #33
 '''

 import time

 def gcd(a,b):
     if(b>a):
         return gcd(b,a)
     while(min(a,b)>0):
         temp = a%b
         a = b
         b = temp
     return max(a,b)

 def projectEulerProblemThirtyThree(n):
     fractions = []

     for a in range(10,n+1):
         for b in range(10,n+1):
             c = a/10
             d = a%10
             e = b/10
             f = b%10
             if(d == e and a!=b):
                 if(f*a==c*b):
                     fractions.append([a,b])

     numerator = 1
     denominator = 1
     for x in fractions:
         numerator*=x[0]         
         denominator*=x[1]

     return denominator/(gcd(numerator,denominator))

 start = time.time()
 print projectEulerProblemThirtyThree(99)
 print ("--- %s seconds ---" % (time.time()-start))

 '''
 Prints

 100
 --- 0.00145101547241 seconds ---

 for input of n = 99
 '''

As shown above, for small inputs brute force can generally get the job done fairly efficiently. I may return to this question eventually to find a more efficient general solution.

Thanks for reading! See you tomorrow.

Project Euler Problem #32:

Problem #32 is one of the many problems on Project Euler that concerns permutations of strings of text or numbers. The question reads:

Project Euler Problem 32: Pandigital products
We shall say that an n-digit number is pandigital if it makes use of all the digits 1 to n exactly once; for example, the 5-digit number, 15234, is 1 through 5 pandigital.

The product 7254 is unusual, as the identity, 39 x 186 = 7254, containing multiplicand, multiplier, and product is 1 through 9 pandigital. 

Find the sum of all products whose multiplicand/multiplier/product identity can be written as a 1 through 9 pandigital.

HINT: Some products can be obtained in more than one way so be sure to only include it once in your sum.

If you expected a solution that does not involve brute force, I’m sorry, but you’re probably going to be disappointed. Here’s my solution:

Solution #1: Brute Force Approach

We simply generate all permutations of the digits {1,2,3,4,5,6,7,8,9} and then iterate through each of them to find which can be written as a product equation. There are only two possibilities. Either the product will have a 1-digit number multiplied by a 4-digit number resulting in a 4-digit number or it will have a 2-digit number multiplied by a 3-digit number resulting in a 4-digit number. Here is an implementation of this method in Python 2.7:

 '''
 Author: Walker Kroubalkian
 Brute Force Approach to Project Euler Problem #32
 '''

 import time

 def listPermutations(myList):
     if(len(myList)==1):
         return [myList]
     a = myList[0]
     b = listPermutations(myList[1:])
     total = []
     for x in b:
         for c in range(len(x)+1):
             temp = x[0:c]
             temp.append(a)
             temp.extend(x[c:])
             total.append(temp)
     return total

 def projectEulerProblemThirtyTwo(myList):
     myList = listPermutations(myList)
     total = []

     for a in myList:
         b = 10*a[0]+a[1]         
         c = 100*a[2]+10*a[3]+a[4]         
         d = 1000*a[5]+100*a[6]+10*a[7]+a[8]
         if(b*c==d):             
             if d not in total:                 
                 total.append(d)         
         b = a[0]         
         c = 1000*a[1]+100*a[2]+10*a[3]+a[4]
         d = 1000*a[5]+100*a[6]+10*a[7]+a[8]         
         if(b*c==d):
             if d not in total:
                 total.append(d)

     final = 0
     for x in total:
         final+=x
     return final

 start = time.time()
 print projectEulerProblemThirtyTwo([1,2,3,4,5,6,7,8,9])
 print ("--- %s seconds ---" % (time.time()-start))

 '''
 Prints

 45228
 --- 0.590600013733 seconds ---

 for input of [1,2,3,4,5,6,7,8,9]
 '''

This solution is fairly efficient as there are only 9! = 362,880 permutations of the digits 1-9 but it could still be optimized. I may return to this question eventually to search for a more efficient solution.

Thanks for reading!

Project Euler Problem #31:

Problem #31 is one of the many Project Euler problems that can be efficiently solved with Dynamic Programming. The question reads:

Project Euler Problem 31: Coin sums
In England the currency is made up of pound, £, and pence, p, and there are eight coins in general circulation:

1p, 2p, 5p, 10p, 20p, 50p, £1 (100p) and £2 (200p).

It is possible to make £2 in the following way:

1x£1 + 1x50p + 2x20p + 1x5p + 1x2p + 3x1p

How many different ways can £2 be made using any number of coins?

The most obvious way to approach this question is by using casework. In fact, this is the solution I initially used when approaching this question. Here was my original solution:

Solution #1: Casework on Largest Coins Approach

We begin by doing casework on the number of £2 coins. For each case, we do casework on the number of £1 coins. For each sub-case, we do casework on the number of 50p coins. This can easily be iterated through recursion by dropping the largest coin at the call of each recursive layer. Here is an implementation of this method in Python 2.7:

 '''
 Author: Walker Kroubalkian
 Recursive Approach to Project Euler Problem #31
 '''

 import time

 def projectEulerProblemThirtyOne(n, currencies):
     currencies = sorted(currencies)[::-1]
     if(len(currencies)==1):
         if(n%currencies[0]==0):
             return 1
         else:
             return 0
     total = 0
     current = currencies[0]
     rest = currencies[1:]
     i = 0
     while(i*current<=n):
         total+=projectEulerProblemThirtyOne(n-i*current, rest)
         i+=1
     return total

 start = time.time()
 print projectEulerProblemThirtyOne(200, [1,2,5,10,20,50,100,200])
 print ("--- %s seconds ---" % (time.time()-start))

 '''
 Prints

 73682
 --- 0.0563788414001 seconds ---

 for input of n=200, currencies = [1,2,5,10,20,50,100,200]
 '''

As shown above, this approach is quite efficient for small inputs such as n = 200p. However, for larger inputs this solution becomes inefficient quite quickly. Luckily, we can use dynamic programming to make this much more efficient. Here is a dynamic approach that I found in Project Euler’s documentation on this question:

Solution #2: Dynamic Approach

We approach the problem dynamically by storing the number of possibilities for every amount between 0p and 200p and building the answers for larger amounts off of the answers for smaller amounts. This would normally cause a problem if we started with the largest currencies, but by starting with the smallest currencies and checking each currency one at a time, we do not have to worry about unnecessary ordering adding to our count. This approach came entirely from Project Euler’s documentation on this problem. Here is an implementation of this approach in Python 2.7:

 '''
 Author: Project Euler (with Python 2.7 implementation by Walker Kroubalkian)
 Very Dynamic Approach to Project Euler Problem #31
 '''

 import time

 def projectEulerProblemThirtyOne(coins, amount):
     ways = [0]*(amount+1)
     ways[0] = 1
     for i in range(len(coins)):
         for j in range(coins[i], amount+1):
             ways[j] = ways[j] + ways[j-coins[i]]
     return ways[amount]

 start = time.time()
 print projectEulerProblemThirtyOne([1, 2, 5, 10, 20, 50, 100, 200], 200)
 print ("--- %s seconds ---" % (time.time()-start))

 '''
 Prints

 73682
 --- 7.15255737305e-06 seconds ---

 for input of n=200, currency = [1,2,5,10,20,50,100,200]
 '''

As shown above, dynamic approaches can be much more efficient than their recursive counterparts. As stated before, this solution was found in Project Euler’s documentation for this problem, and I take no credit in finding it.

Thanks for reading!

Project Euler Problem #30:

Problem #30 concerns numbers which are equal to the sum of powers of their digits. The question reads:

Project Euler Problem 30: Digit fifth powers
Surprisingly there are only three numbers that can be written as the sum of fourth powers of their digits:

1634 = 1^4+6^4+3^4+4^4
8208 = 8^4+2^4+0^4+8^4
9474 = 9^4+4^4+7^4+4^4

As 1 = 1^4 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.

Once again, my solution for this problem falls into the category of “Brute Force”. In this case, I do want to return to this question eventually as I believe I can make it far more efficient. Here’s my solution:

Solution #1: Brute Force Approach

We place an upper bound on numbers that could have this property by calculating the smallest number of digits such that even if every one of that number of digits were a 9, the sum of the fifth powers of the digits would still be less than the number itself. From this, the upper bound is defined as that number of digits multiplied by 9^5. Once this upper bound is calculated, it is a simple task of checking every number between 2 and the upper bound inclusive. Here is an implementation of this method in Python 2.7:

 '''
 Author: Walker Kroubalkian
 Brute Force Approach to Project Euler Problem #30
 '''

 import time

 def sumDigitPower(n,p):
     total = 0
     a = str(n)
     for x in a:
         total+=(int(x)**5)
     return total

 def projectEulerProblemThirty(p):
     a = 1
     while((10a) - 1 <= a(9p)):
         a+=1
     total = 0
     for x in range(2,(9p)a+1):
         if(x == sumDigitPower(x,p)):
             total+=x
     return total

 start = time.time()
 print projectEulerProblemThirty(5)
 print ("--- %s seconds ---" % (time.time()-start))

 '''
 Prints

 443839
 --- 0.88481593132 seconds ---

 for input of p = 5
 '''

As shown above, even with a nice upper bound, the simple brute force solution takes nearly a second. Solving the same problem for sixth powers of digits takes roughly 10 seconds (Apparently the only number in that case is 548834). I would like to return to this question eventually to find a more efficient solution.

Thanks for reading! See you tomorrow.

Project Euler Problem #29:

Problem #29 concerns counting perfect powers. The question reads:

Project Euler Problem 29: Distinct powers
Consider all integer combinations of a^b for 2≤a≤5 and 2≤b≤5:

2^2 = 4, 2^3 = 8, 2^4 = 16, 2^5 = 32
3^2 = 9, 3^3 = 27, 3^4 = 81, 3^5 = 243
4^2 = 16, 4^3 = 64, 4^4 = 256, 4^5 = 1024
5^2 = 25, 5^3 = 125, 5^4 = 625, 5^5 = 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 for this question falls into the category of “Brute Force”. However, it is still able to find the answer in the range from 2 to 10000 in under 10 seconds, so I believe it sufficiently efficient. I may decide to come back to this question eventually to search for a more efficient solution. Here is my solution:

Solution #1: Brute Force Approach

We simply iterate through the possible values of a. For each value of a that is not a perfect power, we automatically count all powers of that base a including its perfect powers within the range. For example, for a = 3, we count the powers with base 3, 9, 27, and 81 in one go. Then we use a sieve to store the fact that we’ve already checked 9, 27, and 81, and keep iterating through the values of a. Here is an implementation of this method in Python 2.7:

'''
Author: Walker Kroubalkian
Brute Force Approach to Project Euler Problem #29
'''

import time

def projectEulerProblemTwentyNine(n):
    checked = [False]*(n+1)
    checked[0] = True
    checked[1] = True
    total = 0
    for i in range(2,n+1):
        if(not checked[i]):
            p = 0
            power = i
            while(power<=n):
                checked[power] = True
                power*=i
                p+=1
            possible = [False]*(p*n+1)
            for a in range(1,p+1):
                for b in range(2,n+1):
                    possible[a*b] = True
            for x in possible:
                if x:
                    total+=1
    return total

start = time.time()
print projectEulerProblemTwentyNine(100)
print ("--- %s seconds ---" % (time.time()-start))

'''
Prints

9183
--- 0.000976085662842 seconds ---

for input of n=100
'''

As shown above, there are times where the brute force solution is plenty efficient for your purposes.

Thanks for reading!

Project Euler Problem #28:

Problem #28 is the type of counting problem that is very annoying to do legitimately. The question reads:

Project Euler Problem 28: Number spiral diagonals
Starting with the number 1 and moving to the right in a clockwise direction a 5 by 5 spiral is formed as follows:

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

It can be verified that the sum of the numbers on the diagonals is 101.

What is the sum of the numbers on the diagonals in a 1001 by 1001 spiral formed in the same way?

As stated above, I find this problem to be very annoying. As a result, I decided to use one of my favorite strategies for solving problems involving complex patterns such as this. Here’s my solution:

Solution #1: Engineer’s Induction Approach

For those who don’t know, one of the most common techniques for writing mathematical proofs is mathematical induction. When proving a claim for all positive integers n, induction is the technique of proving the claim is true when n = 1, assuming it is true when n = x, and using that assumption to prove the claim is true when n = x+1. The technique is often compared to dominoes falling over each other representing each integer proving the claim for the next integer.

Engineer’s induction, on the other hand, is a far more practical technique involving patterns. The technique involves finding a pattern, observing it to be true for the first few terms, and then assuming it will be true forever. This technique can be used to trivialize incredibly complex problems such as Problem #27.

My observation was that looking strictly at the numbers above and to the right of 1 in the 5×5 spiral, we see the numbers 1, 9, and 25 in order. 9 – 1 = 8, and 25 – 9 = 16. 16 – 8 = 8. Doing the same for numbers below and to the right of 1, we see the numbers 1, 3, and 13. 3 – 1 = 2, and 13 – 3 = 10. 10 – 2 = 8. Continuing with the numbers below and to the left of 1, we see the numbers 1, 5, and 17. 5 – 1 = 4, and 17 – 5 = 12. 12 – 4 = 8. Finally, with the numbers above and to the left of 1, we see the numbers 1, 7, and 21. 7 – 1 = 6, and 21 – 7 = 14. 14 – 6 = 8. Based on these observations, I used Engineer’s Induction to find that the increase between each corner and the next corresponding corner would increase by 8 between each concentric ring centered around the 1 in the spiral. For example, 3 – 1 = 2, 13 – 3 = 10. I would expect the next difference to be 10 + 8 = 18 and therefore the next bottom left corner to be 13 + 18 = 31. We can quickly check that this is true. Assuming this pattern is true forever, we can use these observations to get a solution. Here is a solution that uses these observations that is written in Python 2.7:

 '''
 Author: Walker Kroubalkian
 Engineer's Induction Approach to Project Euler Problem #28
 '''

 import time

 def projectEulerProblemTwentyEight(n):
     total = 1
     layers = (n+1)/2
     last = 4
     for i in range(1,layers):
         last = last + (32*i-12)
         total+=last
     return total

 start = time.time()
 print projectEulerProblemTwentyEight(1001)
 print ("--- %s seconds ---" % (time.time()-start))

 '''
 Prints

 669171001
 --- 4.72068786621e-05 seconds ---

 for input of n = 1001
 '''

Entering this answer into Project Euler, we see that it is correct. Therefore, Engineer’s Induction solved the problem for us. Translation: I’m too lazy to actually solve this problem. It makes sense that the second finite differences between each ring should be constant as the top right corner of each (2n+1) x (2n+1) concentric ring is a new square number. Without being rigorous, this observation suggests that the pattern we found will continue.

Hopefully I didn’t annoy you too much by not providing a legitimate solution to this problem. Thanks for reading!