The Inner Machinations of Walker

Project Euler Problem #97

Problem #97 concerns finding the last ten digits of a large Mersenne Prime. The question reads:

Project Euler Problem 97: Large non-Mersenne prime
The first known prime found to exceed one million digits was discovered in 1999, and is a Mersenne prime of the form 2^6972593−1; it contains exactly 2,098,960 digits. Subsequently other Mersenne primes, of the form 2^p−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×2^7830457+1.
Find the last ten digits of this prime number.

My solution for this problem involves a famous algorithm known as the Exponentiation by squaring or square and multiply algorithm. Here is my solution:

Solution #1: Square and Multiply Approach

The problem is equivalent to finding the remainder when the given number is divided by 10^10. Clearly, it will leave a remainder of 1 when divided by 2^10. Thus, it suffices to find the remainder when it is divided by 5^10, as afterwards the Chinese Remainder Theorem (CRT) can be used to find a corresponding remainder mod 10^10. The Exponentiation by squaring algorithm allows us to find this remainder quickly. First, the exponent 7830457 is written in binary. (11101110111101110111001). This binary representation tells us which powers of 2 can be added to get the given exponent. With the well known fact that 2^a * 2^b = 2^(a+b), it follows that if we can find the remainder when powers of the form 2^(2^n) are divided by 5^10, we can multiply those powers according to the binary representation to get the remainder when 2^7830457 is divided by 5^10. Finally, we can multiply the result by 28433 and add 1 to get the remainder when the Mersenne Prime is divided by 5^10, and afterwards CRT can be used to get the last 10 digits. Here is an implementation of this approach in Python 2.7:

 '''
 Author: Walker Kroubalkian
 Square and Multiply Approach to Project Euler Problem #97
 '''
 
 import time
 
 def squareAndMultiply(b,e,m):
     l = bin(e)[2:]
     a = len(l)
     exponents = []
     myExponent = b
     while(len(exponents)<a):
         exponents.append(myExponent)
         myExponent = (myExponent**2)%m
     total = 1
     c = l[::-1]
     for x in range(a):
         if(c[x] == '1'):
             total*=exponents[x]
             total%=m
     return total
 
 def projectEulerProblemNinetySeven(a,b,e,c,m):
     return (a*squareAndMultiply(b, e, m) + c)%m
 
 start = time.time()
 print projectEulerProblemNinetySeven(28433, 2, 7830457, 1, 10**10)
 print ("--- %s seconds ---" % (time.time()-start))
 
 print bin(7830457)
 
 '''
 Prints
 
 8739992577
 --- 5.29289245605e-05 seconds ---
 
 for input of a = 28433, b = 2, e = 7830457, c = 1, m = 10**10
 '''

And with that, we’re done. The Square and Multiply approach is very common in computer science, so I may reuse this code in other problems.

Thanks for reading! See you tomorrow.

Project Euler Problem #96

Problem #96 concerns solving Sudoku grids. The question reads:

I must confess, this is one of the problems where I’m not really sure why my solution is as efficient as it is. It took me a lot of troubleshooting to find a solution which could solve all of the grids in a reasonable amount of time. Here is my solution:

Solution #1: Brute Force Approach

As always, we store the grids in a file and then read from the file to store the grids in arrays. As it turns out, the method I always used to solve Sudoku grids is not sufficient to solve every grid. My typical method is to look for cells that only certain digits can fill first. If none exist, then I search for rows, columns, and squares where only certain cells can have certain digits. These two methods are generally enough to solve reasonable Sudoku grids, and when I implemented them, they were able to solve roughly 40 of the grids in this problem in no time at all. For the other 10 grids, I resorted to brute force. Starting at the top of the grid and working down, I made guesses for each cell and looked for solutions with each of those guesses. If no solution existed, I would update the guess, and if no obvious solution existed, I would make another guess. This took a lot of trouble shooting to implement efficiently, and I am a bit confused why it is suddenly able to solve all of the grids quickly. Here is an implementation of this approach in Python 2.7:

 '''
 Author: Walker Kroubalkian
 Backtracking Brute Force Approach to Project Euler Problem #96
 '''
 
 import time
 
 def stringToArray(myString):
     a = []
     for x in myString:
         a.append(int(x))
     return a
 
 f = open("PE96Sudoku.txt","r")
 
 if f.mode=="r":
     contents = f.readlines()
     realContents = []
     i = 0
     for x in contents:
         if(i%10!=0):
             if x[len(x)-1]=="\n":
                 realContents.append(stringToArray(x[0:len(x)-1]))
             else:
                 realContents.append(stringToArray(x))
         i+=1
 else:
     raise ValueError("Cannot read from file")
 
 def countZeros(n):
     t = 0
     for x in n:
         for y in x:
             if y==0:
                 t+=1
     return t
 
 def copyArray(n):
     t = []
     for x in n:
         r = []
         for y in x:
             r.append(y)
         t.append(r)
     return t
 
 def optionCell(n,r,c):
     if(n[r][c]!=0):
         return []
     notPoss = []
     for x in range(9):
         notPoss.append(n[r][x])
         notPoss.append(n[x][c])
     lr = r-r%3
     tc = c-c%3
     for a in range(3):
         for b in range(3):
             notPoss.append(n[lr+a][tc+b])
     options = []
     for d in range(1,10):
         if d not in notPoss:
             options.append(d)
     return options
 
 def optionRow(n,r):
     rowOptions = []
     for c in range(9):
         rowOptions.append(optionCell(n,r,c))
     return rowOptions
 
 def potentialOptions(n):
     p = []
     for r in range(9):
         p.append(optionRow(n,r))
     return p
 
 def possibleGrid(n):
     p = potentialOptions(n)
     for r in range(9):
         for c in range(9):
             if n[r][c]==0 and len(p[r][c]) == 0:
                 return False
     return p
 
 def solveGrid(n):
     total = countZeros(n)
     v = possibleGrid(n)
     if v == False:
         return False
     while total>0:
         found = False
         for r in range(9):
             for c in range(9):
                 if len(v[r][c]) == 1 and n[r][c] == 0:
                     a = v[r][c][0]
                     n[r][c] = a
                     for x in range(9):
                         d = v[r][x]
                         if a in d:
                             d.remove(a)
                             v[r][x] = d
                     for x in range(9):
                         d = v[x][c]
                         if a in d:
                             d.remove(a)
                             v[x][c] = d
                     tr = r-r%3
                     lc = c-c%3
                     for x in range(3):
                         for y in range(3):
                             d = v[tr+x][lc+y]
                             if a in d:
                                 d.remove(a)
                                 v[tr+x][lc+y] = d
                     v[r][c] = []
                     found = True
                     break
             if found:
                 break
         if not found:
             return n
         total-=1
     return n
 
 def solveSudoku(n):
     possible = [n]
     maxZeros = countZeros(n)
     while(maxZeros>0):
         newPoss = []
         for x in possible:
             a = solveGrid(x)
             if a!=False:
                 zeroR = -1
                 zeroC = -1
                 for r in range(9):
                     for c in range(9):
                         if a[r][c]==0:
                             zeroR = r
                             zeroC = c
                 if zeroR>-1:
                     v = optionCell(a, zeroR, zeroC)
                     for z in v:
                         temp = copyArray(a)
                         temp[zeroR][zeroC] = z
                         newPoss.append(temp)
                 else:
                     return a
         possible = newPoss
         if len(possible)==0:
             return False
         for z in possible:
             v3 = countZeros(z)
             if v3==0:
                 return z
             if v3>maxZeros:
                 maxZeros = 3
     return possible[0]
 
 def isCorrectGrid(myGrid):
     for r in range(9):
         theRow = []
         for x in myGrid:
             if x==0 or x in theRow:
                 return False
             else:
                 theRow.append(x)
     for c in range(9):
         theCol = []
         for r in range(9):
             x = myGrid[r][c]
             if x==0 or x in theCol:
                 return False
             else:
                 theCol.append(x)
     for tr in range(0,9,3):
         for lc in range(0,9,3):
             theSquare = []
             for a in range(3):
                 for b in range(3):
                     x = myGrid[tr+a][lc+b]
                     if x==0 or x in theSquare:
                         return False
                     else:
                         theSquare.append(x)
     return True
 
 def projectEulerProblemNinetySix(n):
     l = len(n)
     total = 0
     for x in range(0,l,9):
         grid = n[x:x+9]
         a = solveSudoku(grid)
         if a==False or not isCorrectGrid(a):
             print False
         else:
             total+=100*a[0][0]+10*a[0][1]+a[0][2]
     return total
 
 start = time.time()
 print projectEulerProblemNinetySix(realContents)
 print ("--- %s seconds ---" % (time.time()-start))
 
 '''
 Prints
 
 24702
 --- 2.47313904762 seconds ---
 
 for input of given list of Sudoku Grids.
 '''

And with that, we’re done. That took nearly 2.47 seconds to run, so some of the grids really stretched the limits of my algorithm. I would like to see a cleaner algorithm for this problem at some point, and I may come back to this problem in the near future.

Thanks for reading! See you tomorrow.

Project Euler Problem #95

Problem #95 concerns chains formed by repeatedly replacing a number with the sum of its proper factors. The question reads:

Project Euler Problem 95: Amicable chains
The proper divisors of a number are all the divisors excluding the number itself. For example, the proper divisors of 28 are 1, 2, 4, 7, and 14. As the sum of these divisors is equal to 28, we call it a perfect number.
Interestingly the sum of the proper divisors of 220 is 284 and the sum of the proper divisors of 284 is 220, forming a chain of two numbers. For this reason, 220 and 284 are called an amicable pair.
Perhaps less well known are longer chains. For example, starting with 12496, we form a chain of five numbers:
12496 → 14288 → 15472 → 14536 → 14264 (→ 12496 → ...)
Since this chain returns to its starting point, it is called an amicable chain.
Find the smallest member of the longest amicable chain with no element exceeding one million.

My solution for this problem involves a ton of brute force. Here is my solution:

Solution #1: Brute Force Approach

First, we determine the sum of the proper factors of every number less than 1,000,000 by iterating through the possible divisors less than 500,000 and adding each divisor to every proper multiple of it. Next, we start from 1,000,000 and work down, checking each number for periodic behavior of amicable chains. We can perform this task dynamically, so numbers that are part of larger chains do not need to be checked multiple times. Here is an implementation of this approach in Python 2.7:

 '''
 Author: Walker Kroubalkian
 Sieve Approach to Project Euler Problem #95
 '''
 
 import time
 
 def projectEulerProblemNinetyFive(n):
     properSums = [0]*(n+1)
     for c in range(1,n/2+1):
         for d in range(2*c,n+1,c):
             properSums[d]+=c
     maxLoop = 5
     minNumber = 12496
     loopLengths = [-1]*(n+1)
     for e in range(n,0,-1):
         if loopLengths[e]==-1:
             t = 0
             f = properSums[e]
             loops = True
             found = [e]
             if(f!=e):
                 while(f!=e):
                     t+=1
                     if(f>n):
                         for x in found:
                             loopLengths[x] = 0
                         loops = False
                         break
                     if loopLengths[f]!=-1:
                         for x in found:
                             loopLengths[x] = loopLengths[f]
                             loops = False
                             break
                     if f in found:
                         a = found.index(f)
                         for x in found:
                             loopLengths[x] = len(found)-a
                         found = found[a:]
                         break
                     found.append(f)
                     v = properSums[f]
                     if(v==f or v==0):
                         for x in found:
                             loopLengths[x] = 0
                         loops = False
                         break
                     f = v
                 if loops:
                     for x in found:
                         loopLengths[x] = t
                     if t>maxLoop:
                         maxLoop = t
                         minNumber = found[0]
                         for x in found:
                             if x<minNumber:
                                 minNumber = x
                     elif t==maxLoop:
                         for x in found:
                             if x<minNumber:
                                 minNumber = x
                 else:
                     for x in found:
                         loopLengths[x] = 0
     return minNumber

 start = time.time()
 print projectEulerProblemNinetyFive(1000000)
 print ("--- %s seconds ---" % (time.time()-start))
 
 '''
 Prints
 
 14316
 --- 5.02517795563 seconds ---
 
 for input of n = 1000000.
 '''

And with that, we’re done. That took over 5 seconds to run. There must be a faster way to search for loops then the method I used. I definitely want to return to this problem at some point.

Thanks for reading! See you tomorrow.

Project Euler Problem #94

Problem #94 concerns triangles that are nearly equilateral and have integer area. The question reads:

Project Euler Problem 94: Almost equilateral triangles
It is easily proved that no equilateral triangle exists with integral length sides and integral area. However, the almost equilateral triangle 5-5-6 has an area of 12 square units.
We shall define an almost equilateral triangle to be a triangle for which two sides are equal and the third differs by no more than one unit.
Find the sum of the perimeters of all almost equilateral triangles with integral side lengths and area and whose perimeters do not exceed one billion (1,000,000,000).

My solution to this problem involves Pell Equations. Here is my solution:

Solution #1: Pell Equation Approach

We have two cases to consider. In the first, the triangle has sides x, x, and x+1. We can show that the area of this triangle is (x+1)*sqrt(3*x^2-2x-1)/4. Thus, it suffices to determine when 3*x^2-2x-1 = y^2 for some integer y. Treating this as a quadratic for x and solving, we get x = (2+2*sqrt(4+3y^2))/6. It is easy to show that y is not odd, so we can write y = 2*z. Thus, sqrt(4+12z^2) = 2*sqrt(1+3z^2) is an integer. It follows that a^2-3z^2 = 1 for some integer a. Thus, determining solutions for x is equivalent to determining solutions for z in this Pell Equation. We can observe that the first 3 solutions are (a,z) = (1,0), (2,1), (7,4). It follows that if (a,z) is a solution, (2*a+3*z, a+2*z) is the next solution. We can write x = (1+2*a)/3. We can observe that every other solution satisfies a%3 = 1, so it suffices to recursively generate every other solution. Doing so, we can find all almost equilateral triangles of the form x, x, x+1.

The other case is triangles of the form x, x, x-1. We can find that the area of this triangle is (x-1)*sqrt(3*x^2+2x-1)/4. Thus, 3x^2+2x-1 = y^2 for some value of y. Solving for x, we get x = (-2+sqrt(16+12y^2))/6. We can observe that this will result in the same Pell Equation, but this time the other half of the solutions will be acceptable, and we can get the value of x from x = (2a-1)/3. From this, we can recursively generate every solution. Here is an implementation of this approach in Python 2.7:

 '''
 Author: Walker Kroubalkian
 Pell Equation Approach to Project Euler Problem #94
 '''
 
 import time
 
 def projectEulerProblemNinetyFour(n):
     # l, l, l+1 Triangles
     y = 14
     x = 8
     pTotal = 0
     while(y<=n-2):
         pTotal+=(y+2)
         yTemp = 7*y+12*x
         xTemp = 4*y+7*x
         y = yTemp
         x = xTemp
     y = 52
     x = 30
     while(y<=n+2):
         pTotal+=(y-2)
         yTemp = 7*y+12*x
         xTemp = 4*y+7*x
         y = yTemp
         x = xTemp
     return pTotal
 
 start = time.time()
 print projectEulerProblemNinetyFour(10**9)
 print ("--- %s seconds ---" % (time.time()-start))
 
 '''
 Prints
 
 518408346
 --- 1.28746032715e-05 seconds ---
 
 for input of n = 10**9.
 '''

And with that, we’re done. This is a great example of the power of Pell Equations. The problem involved finding all triangles with perimeters less than 1,000,000,000, but with two simple Pell Equations, it could be solved in a hundredth of a millisecond.

Thanks for reading! See you tomorrow.

Project Euler Problem #93

Problem #93 concerns the values that can be obtained by evaluating arithmetic expressions with specific sets of digits. The question reads:

Project Euler Problem 93: Arithmetic expressions
By using each of the digits from the set, {1, 2, 3, 4}, exactly once, and making use of the four arithmetic operations (+, −, *, /) and brackets/parentheses, it is possible to form different positive integer targets.
For example,
8 = (4 * (1 + 3)) / 2
14 = 4 * (3 + 1 / 2)
19 = 4 * (2 + 3) − 1
36 = 3 * 4 * (2 + 1)
Note that concatenations of the digits, like 12 + 34, are not allowed.
Using the set, {1, 2, 3, 4}, it is possible to obtain thirty-one different target numbers of which 36 is the maximum, and each of the numbers 1 to 28 can be obtained before encountering the first non-expressible number.
Find the set of four distinct digits, a < b < c < d, for which the longest set of consecutive positive integers, 1 to n, can be obtained, giving your answer as a string: abcd.

My solution for this problem is very bad as it is essentially just pure brute force. Here is my solution:

Solution #1: Brute Force Approach

We simply look at every subset of 4 of the digits and count the number of consecutive values that can be found by listing the value of every integer arithmetic expression that can be written. Here is an implementation of this approach in Python 2.7:

 '''
 Author: Walker Kroubalkian
 Brute Force Approach to Project Euler Problem #93
 '''
 
 import time
 
 def subset(myList,n):
     l = len(myList)
     if(l==0):
         if(n==0):
             return [[]]
         return []
     if(l<n):
         return []
     if(l==n):
         return [sorted(myList)]
     a = myList[0]
     total = subset(myList[1:],n)
     possible = subset(myList[1:],n-1)
     for x in possible:
         t = x[:]
         t.append(a)
         total.append(sorted(t))
     return total
 
 def permutations(myList):
     l = len(myList)
     if(l==0):
         return []
     if(l==1):
         return [myList]
     a = myList[0]
     b = permutations(myList[1:])
     total = []
     for c in b:
         for x in range(l):
             t = c[0:x]
             t.append(a)
             t.extend(c[x:])
             total.append(t)
     return total
 
 def allTuples(myList,n):
     if(n==0):
         return [[]]
     b = allTuples(myList,n-1)
     total = []
     for x in b:
         for y in myList:
             z = x[:]
             z.append(y)
             total.append(z)
     return total

 def insertOperations(myList):
     operationTriples = allTuples(["+","-","*","/"],3)
     parentheseOptions = [" o o o ","( o o )o ","( o )o o ", "( o )o( o )","(( o )o )o "]
     final = []
     wrongCount = 0
     for p in parentheseOptions:
         for o in operationTriples:
             s = ""
             c = 0
             d = 0
             for x in p:
                 if x==" ":
                     s+=str(float(myList[c]))
                     c+=1
                 elif(x=="o"):
                     s+=str(o[d])
                     d+=1
                 else:
                     s+=x
             try:
                 myValue = eval(s)
                 if(myValue-int(myValue)==0):
                     if int(myValue) not in final:
                         final.append(int(myValue))
                 else:
                     wrongCount+=1
             except:
                 wrongCount+=1
     return final
 
 def projectEulerProblemNinetyThree():
     quadruples = subset([0,1,2,3,4,5,6,7,8,9],4)
     maxFound = 28
     maxQuadruple = [1,2,3,4]
     for x in quadruples:
         y = permutations(x)
         total = []
         for z in y:
             w = insertOperations(z)
             for a in w:
                 if a>0 and a not in total:
                     total.append(a)
         c = 1
         while c in total:
             c+=1
         if(c>maxFound):
             maxFound = c
             maxQuadruple = x
     s = ""
     for a in maxQuadruple:
         s+=str(a)
     return s
 
 start = time.time()
 print projectEulerProblemNinetyThree()
 print ("--- %s seconds ---" % (time.time()-start))
 
 '''
 Prints
 
 1258
 --- 15.6847269535 seconds ---
 
 for given problem.
 '''

And with that, we’re done. That took over 15 seconds to run, so I may return to this problem eventually to look for a more efficient solution.

Thanks for reading! See you tomorrow.

Project Euler Problem #92

Problem #92 concerns the results when numbers are repeatedly replaced by the square of their digits. The question reads:

Project Euler Problem 92: Square digit chains
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 for this problem is very bad as it takes longer than a minute to run. Here is my solution:

Solution #1: Brute Force Approach

Starting from 10,000,000 and working down, we manually check whether each number ends at 1 or 89 and then store all intermediate numbers based on whether they end in 1 or 89. With this approach, it is possible to dynamically determine whether each smaller number will end in a loop. Here is an implementation of this approach in Python 2.7:

 '''
 Author: Walker Kroubalkian
 Dynamic Approach to Project Euler Problem #92
 '''
 
 import time
 
 def squareDigits(x):
     a = str(x)
     total = 0
     for b in a:
         total+=int(b)**2
     return total
 
 def projectEulerProblemNinetyTwo(n):
     found = [-1]*(n)
     found[1] = 1
     found[89] = 89
     total = 0
     for c in range(n-1,1,-1):
         endsOne = True
         if(found[c]==-1):
             temp = c
             change = []
             while(temp!=89 and temp!=1 and (temp>n or found[temp]==-1)):
                 if(temp<=c):
                     change.append(temp)
                 temp = squareDigits(temp)
             if(temp == 89 or found[temp] == 89):
                 endsOne = False
                 total+=1
             if endsOne:
                 for x in change:
                     found[c] = 1
             else:
                 for x in change:
                     found[c] = 89
         else:
             if(found[c] == 89):
                 total+=1
     return total
 
 start = time.time()
 print projectEulerProblemNinetyTwo(10000000)
 print ("--- %s seconds ---" % (time.time()-start))
 
 '''
 Prints
 
 8581146
 --- 105.508774042 seconds ---
 
 for input of n = 10000000.
 '''

And with that, we’re done. That took over 100 seconds to run, so I will definitely want to look back at this question at some point. However, it appears that dynamically finding the answer can work even when it requires the creation of an array with 10,000,000 elements.

Thanks for reading! See you tomorrow.

Project Euler Problem #91

Problem #91 concerns right triangles whose vertices lie on lattice points. The question reads:

My solution for this problem involves a bit of brute force. Here’s my solution:

Solution #1: Brute Force Casework Approach

We have several cases to consider. The first is if the right angle is either at the origin or on one of the axes. If the right angle is at the origin, there are clearly n*n triangles where x,y <= n. If the right angle is on the x-axis, there are also n*n triangles, as there are n choices for the location of the right angle, and n choices for the y-coordinate of the 3rd vertex. By symmetry, there are also n*n triangles with a right angle on the y-axis.

The next case is that the hypotenuse is on one of the axes. Note that if the hypotenuse has length c, then the number of right triangles with that hypotenuse on one of the two axes is double the number of values l such that l*(c-l) is a perfect square, because it can be shown by similar triangles that the altitude to the hypotenuse would be the square root of l*(c-l). By checking values of l up to c/2, we can add 4 for each value of l. If c is even, then there are an additional 2 isosceles right triangles.

The final case is when none of the sides of the triangle lies on one of the axes. In this case, it suffices to investigate each vector <a,c> with a,c <= n and then to count vectors <b,d> with a*b+c*d = 0 such that <a+b,c+d> lies in the square. The fact that two vectors are orthogonal if and only if their dot product is 0 is very useful here. After this, we are done. Here is an implementation of this approach in Python 2.7:

 '''
 Author: Walker Kroubalkian
 Brute Force Approach to Project Euler Problem #91
 '''
 
 import time
 
 def projectEulerProblemNinetyOne(n):
     total = 3*n*n
     squares = []
     for h in range(n+1):
         squares.append(h*h)
     for c in range(1,n+1):
         for l in range(1,(c+1)/2):
             if l*(c-l) in squares:
                 total+=4
         if(c%2==0):
             total+=2
     for a in range(1,n+1):
         firstTerm = 0
         for c in range(a+1,n+1):
             firstTerm += a
             for b in range(1,n+1):
                 secondTerm = squares[b]
                 if((secondTerm-firstTerm)%b==0):
                     d = (secondTerm-firstTerm)/b
                     if 1<=d<=n:
                         total+=2
     return total
 
 start = time.time()
 print projectEulerProblemNinetyOne(50)
 print ("--- %s seconds ---" % (time.time()-start))
 
 '''
 Prints
 
 14234
 --- 0.00694298744202 seconds ---
 
 for input of n = 50.
 '''

And with that, we’re done. The trickiest optimization I used was using the fact that two vectors are perpendicular iff their dot product is 0. Other than that, this was a pure brute force solution. It ran in under 7 ms, so I am probably satisfied with this solution for now.

Thanks for reading! See you tomorrow.

Project Euler Problem #90

Problem #90 concerns pairs of dice that can be rearranged to form all of the 2-digit square numbers. The question reads:

My solution for this problem is very brute force-heavy, so I may come back to this problem to look for a more efficient solution. Here is my solution:

Solution #1: Brute Force Approach

We simply list all 6-element subsets of the 10 digits and check every pair for each 2-digit square number. Most square numbers are simple to check. The ones that contain 9 or 6 are a bit more complex as any time a 6 appears, it can also be a 9 by flipping the cube. Thus, the squares which contain 9 or 6 must be handled separately. After doing this, the number of possible pairs can be counted. Here is an implementation of this approach in Python 2.7:

 '''
 Author: Walker Kroubalkian
 Brute Force Approach to Project Euler Problem #90
 '''
 
 import time
 
 def subset(myList,n):
     l = len(myList)
     if(l==0):
         if(n==0):
             return [[]]
         return []
     if(l<n):
         return []
     if(l==n):
         return [sorted(myList)]
     a = myList[0]
     total = subset(myList[1:],n)
     possible = subset(myList[1:],n-1)
     for x in possible:
         t = x[:]
         t.append(a)
         total.append(sorted(t))
     return total
 
 def projectEulerProblemNinety():
     total = subset(["0","1","2","3","4","5","6","7","8","9"],6)
     simpleSquares = ["01","04","25","81"]
     complexSquares = ["09","16","36","49","64"]
     allFound = []
     for a in total:
         for b in total:
             if(a!=b):
                 possible = True
                 for x in simpleSquares:
                     if not ((x[0] in a and x[1] in b) or (x[1] in a and x[0] in b)):
                         possible = False
                         break
                 for y in complexSquares:
                     for c in y:
                         if c!="6" and c!="9":
                             letter = c
                             break
                     if not ((letter in a and ("6" in b or "9" in b)) or (letter in b and ("6" in a or "9" in a))):
                         possible = False
                         break
                 
                 if possible:
                     myPair = sorted([a,b])
                     if myPair not in allFound:
                         allFound.append(myPair)
     return len(allFound)
 
 start = time.time()
 print projectEulerProblemNinety()
 print ("--- %s seconds ---" % (time.time()-start))
 
 '''
 Prints
 
 1217
 --- 0.110777139664 seconds ---
 
 for given problem.
 '''

And with that, we’re done. That may have been a brute force solution, but it still only took just over a tenth of a second to run.

Thanks for reading! See you tomorrow.

Project Euler Problem #89

Problem #89 concerns the number of characters in Roman numerals. The question reads:

Project Euler Problem 89: Roman numerals
For a number written in Roman numerals to be considered valid there are basic rules which must be followed. Even though the rules allow some numbers to be expressed in more than one way there is always a "best" way of writing a particular number.
For example, it would appear that there are at least six ways of writing the number sixteen:
IIIIIIIIIIIIIIII
VIIIIIIIIIII
VVIIIIII
XIIIIII
VVVI
XVI
However, according to the rules only XIIIIII and XVI are valid, and the last example is considered to be the most efficient, as it uses the least number of numerals.
The 11K text file, roman.txt (right click and 'Save Link/Target As...'), contains one thousand numbers written in valid, but not necessarily minimal, Roman numerals; see About... Roman Numerals for the definitive rules for this problem.
Find the number of characters saved by writing each of these in their minimal form.
Note: You can assume that all the Roman numerals in the file contain no more than four consecutive identical units.

As it turns out, this was the last problem in the first hundred problems that I solved. I thought I would have to use an obscure Python library to solve it, but luckily I noticed the following trick:

Solution #1: Inefficient Pattern Approach

We can observe that there are only so many patterns of characters for a particular digit in Roman numerals which can be legal when written with an inefficient number of digits. Specifically, when dealing with a 9 in the hundreds place, “DCCCC” is legal, but “CM” is more efficient. When dealing with a 4 in the hundreds place, “CCCC” is legal, but “CD” is more efficient. When dealing with a 9 in the tens place, “LXXXX” is legal but “XC” is more efficient. When dealing with a 4 in the tens place, “XXXX” is legal but “XL” is more efficient. When dealing with a 9 in the ones place, “VIIII” is legal but “IX” is more efficient. Finally, when dealing with a 4 in the ones place, “IIII” is legal but “IV” is more efficient. Thus, to convert a Roman numeral to its most efficient form, it suffices to convert these patterns to their most efficient forms. The only thing we need to look out for is the order in which we do it: “DCCCC” must be replaced for “CCCC”, etc. Once we have done that, we can count the number of unnecessary characters. Here is an implementation in Python 2.7:

 '''
 Author: Walker Kroubalkian
 String Parsing Approach to Project Euler Problem #89
 '''
 
 import time
 from re import sub
 
 f = open("PE89RomanNumerals.txt","r")
 
 if f.mode=="r":
     contents = f.readlines()
     realContents = []
     for x in contents:
         realContents.append(str(x))
 else:
     raise ValueError("Cannot read from file")
 
 finalContents = []
 for x in realContents:
     if x[len(x)-1]=="\n":
         finalContents.append(x[0:len(x)-1])
     else:
         finalContents.append(x)
 
 def replace(big,small,rep):
     s = len(small)
     while(True):
         try:
             x = big.index(small)
             big = big[0:x]+rep+big[x+s:]
         except:
             break
     return big
 
 def projectEulerProblemEightyNine(myList):
     total = 0
     for x in myList:
         v = len(x)
         go = True
         while(go):
             temp = x
             x = replace(x,"DCCCC","CM")
             x = replace(x,"LXXXX","XC")
             x = replace(x,"VIIII","IX")
             x = replace(x,"CCCC","CD")
             x = replace(x,"XXXX","XL")
             x = replace(x,"IIII","IV")
             if(x==temp):
                 go = False
                 total+=(v-len(x))
     return total
 
 start = time.time()
 print projectEulerProblemEightyNine(finalContents)
 print ("--- %s seconds ---" % (time.time()-start))
 
 '''
 Prints
 
 743
 --- 0.00833415985107 seconds ---
 
 for input of given list of Roman Numerals
 '''

And with that, we’re done. That ran in only 8 milliseconds. I would like to find a Python library that can convert between decimal and Roman numerals, but that can wait for another day.

Thanks for reading! See you tomorrow.

Project Euler Problem #88

Problem #88 concerns numbers which can be expressed as both the sum and the product of the numbers in the same set of numbers. The question reads:

Project Euler Problem 88: Product-sum numbers
A natural number, N, that can be written as the sum and product of a given set of at least two natural numbers, {a₁, a₂, ... , a_k} is called a product-sum number: N = a₁ + a₂ + ... + a_k = a₁ × a₂ × ... × a_k.

For example, 6 = 1 + 2 + 3 = 1 × 2 × 3.

For a given set of size, k, we shall call the smallest N with this property a minimal product-sum number. The minimal product-sum numbers for sets of size, k = 2, 3, 4, 5, and 6 are as follows.

k=2: 4 = 2 × 2 = 2 + 2
k=3: 6 = 1 × 2 × 3 = 1 + 2 + 3
k=4: 8 = 1 × 1 × 2 × 4 = 1 + 1 + 2 + 4
k=5: 8 = 1 × 1 × 2 × 2 × 2 = 1 + 1 + 2 + 2 + 2
k=6: 12 = 1 × 1 × 1 × 1 × 2 × 6 = 1 + 1 + 1 + 1 + 2 + 6

Hence for 2≤k≤6, the sum of all the minimal product-sum numbers is 4+6+8+12 = 30; note that 8 is only counted once in the sum.

In fact, as the complete set of minimal product-sum numbers for 2≤k≤12 is {4, 6, 8, 12, 15, 16}, the sum is 61.

What is the sum of all the minimal product-sum numbers for 2≤k≤12000?

My solution involves investigating the factorizations of numbers and relating them to this property. Here is my solution:

Solution #1: Brute Force Approach

We can observe that for a given number product-sum number n, the product is formed by some factorization of n and enough 1’s that the sum of the numbers in the factorization and the 1’s is equal to n. Thus, to find all product-sum numbers, it suffices to investigate all factorizations of different numbers. Specifically, we can guarantee that for sets of size k, the minimum sum-product number is less than or equal to 2*k because the set k, 2, 1, 1, . . . 1 with k-2 1’s has both a sum and a product of 2*k. Thus, it suffices to check every factorization of every number less than 2*12,000 = 24,000.

We can dynamically get every factorization for every number up to 24,000 by appending each factor to each factorization of smaller numbers. Next, it suffices to check each factorization and store the minimum sum-product number for each possible size of the set. Here is an implementation of this approach in Python 2.7:

 '''
 Author: Walker Kroubalkian
 Brute Force Approach to Project Euler Problem #88
 '''
 
 import time
 from math import sqrt
 
 def projectEulerProblemEightyEight(n):
     answers = [0]*(n+1)
     factorizations = [[],[],[[2]],[[3]],[[2,2],[4]]]
     for c in range(5,2*n+1):
         factors = []
         for x in range(2,int(sqrt(c))+1):
             if(c%x==0):
                 a = factorizations[c/x]
                 for p in a:
                     possible = True
                     for z in p:
                         if z<x:
                             possible = False
                             break
                     if possible:
                         t = p[:]
                         t.append(x)
                         factors.append(sorted(t))
         factors.append([c])
         factorizations.append(factors)
     for x in range(4,2*n+1):
         factors = factorizations[x]
         for p in factors:
             t = 0
             for y in p:
                 t+=y
             if(len(p)>1 and t<=x):
                 i = len(p)+x-t
                 if(i<=n):
                     v = answers[i]
                     if(v==0):
                         answers[i] = x
     found = []
     total = 0
     for x in answers:
         if x not in found:
             total+=x
             found.append(x)
     return total
 
 start = time.time()
 print projectEulerProblemEightyEight(12000)
 print ("--- %s seconds ---" % (time.time()-start))
 
 '''
 Prints
 
 7587457
 --- 0.840548992157 seconds ---
 
 for input of n = 12000
 '''

And with that, we’re done. That approach ran in under a second. There is probably a cleaner way to implement this approach, but I’m satisfied with the results. I may come back to this problem eventually to search for a better solution.

Thanks for reading! See you tomorrow.