The Inner Machinations of Walker

Project Euler Problem #77

Problem #77 concerns partitions of numbers where the summands in each partition are composed of the prime numbers less than the number. The question reads:

Project Euler Problem 77: Prime summations
It is possible to write ten as the sum of primes in exactly five different ways:
7 + 3
5 + 5
5 + 3 + 2
3 + 3 + 2 + 2
2 + 2 + 2 + 2 + 2
What is the first value which can be written as the sum of primes in over five thousand different ways?

You may notice that this problem is very similar to Problem #31 and Problem #76. As a result, my code for solving this problem is very similar to the code for each of those problems. This code was heavily inspired by Project Euler’s documentation for Problem #31. Here is my solution:

Solution #1: Dynamic Approach

As we did in Problem #31 and Problem #76, we can notice that adding larger potential summands (or larger primes in this case) will only add recursively to the same problem with smaller summands. Thus, it suffices to work up the list of summands, dynamically counting the number of partitions for each number up to n with each of the smaller summands and then recursively counting the partitions added by the highest summand. By calculating a list of potential summands with the Sieve of Eratosthenes, this approach can be used to find the number of partitions in this problem. Unfortunately, because an upper bound is not given, solving this problem will either involve arbitrary iteration or guessing and checking. I decided to use a mixture of both by repeatedly multiplying the maximum possible prime by 3. Here is an implementation of this approach in Python 2.7:

 '''
 Author: Walker Kroubalkian
 Dynamic Approach to Project Euler Problem #77
 '''

 import time
 
 def subProblem(n,m):
     numbers = sieveEratosthenes(n)
     ways = [0]*(n+1)
     ways[0] = 1
     for i in range(len(numbers)):
         for j in range(numbers[i], n+1):
             ways[j] = ways[j] + ways[j-numbers[i]]
     for x in range(n+1):
         if(ways[x]>m):
             return x
     return -1
 
 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 myPrimes
 
 def projectEulerProblemSeventySeven(m):
     c = 10
     while(True):
         a = subProblem(c, m)
         if(a!=-1):
             return a
         c*=3
 
 start = time.time()
 print projectEulerProblemSeventySeven(5000)
 print ("--- %s seconds ---" % (time.time()-start))
 
 '''
 Prints
 
 71
 --- 0.000175952911377 seconds ---
 
 for input of m = 5000.
 '''

And with that we’re done. For a small input of m = 1000, this dynamic approach managed to run in under a millisecond. It would be interesting to see if there is a more efficient solution for larger inputs.

Thanks for reading! See you tomorrow.

Project Euler Problem #76

Problem #76 concerns partitions of positive integers. The question reads:

Project Euler Problem 76: Counting summations
It is possible to write five as a sum in exactly six different ways:
4 + 1
3 + 2
3 + 1 + 1
2 + 2 + 1
2 + 1 + 1 + 1
1 + 1 + 1 + 1 + 1
How many different ways can one hundred be written as a sum of at least two positive integers?

You may notice that this solution is very similar to Project Euler Problem #31 which involved determining the number of ways certain amounts of currency could be represented with coins. The only difference is that in this question, the possible values of the coins include every positive integer. You may also recall that the more efficient solution I presented in Problem #31 came from Project Euler’s documentation. Thus, I will reuse their solution to solve this problem and give credit appropriately. Here is Project Euler’s Solution:

Solution #1: Dynamic Approach (Project Euler’s Approach)

As in Project Euler Problem #31, we can observe that adding larger types of currency can be thought of as adding to the same problem with only the smaller amounts of currency. Thus, we dynamically count the number of ways each total can be summed for each new currency. In this case, the currencies range in value from 1 to n-1. Once all of the currencies have been iterated through, we are done. Here is an implementation of this approach in Python 2.7. As listed above, this is very similar to Project Euler’s solution for Problem #31.

 '''
 Author: Walker Kroubalkian (Heavily inspired by Project Euler's Solution to Project Euler Problem #31)
 Dynamic Approach to Project Euler Problem #76
 '''
 
 import time
 
 def projectEulerProblemSeventySix(n):
     numbers = []
     for x in range(1,n):
         numbers.append(x)
     ways = [0]*(n+1)
     ways[0] = 1
     for i in range(len(numbers)):
         for j in range(numbers[i], n+1):
             ways[j] = ways[j] + ways[j-numbers[i]]
     return ways[n]
 
 start = time.time()
 print projectEulerProblemSeventySix(100)
 print ("--- %s seconds ---" % (time.time()-start))
 
 '''
 Prints
 
 190569291
 --- 0.000514030456543 seconds ---
 
 for input of n = 100.
 '''

And with that, we’re done. That only took half a millisecond to run. This is yet another example of the powers of dynamic programming.

Thanks for reading! See you tomorrow.

Project Euler Problem #75

Problem #75 concerns the perimeters of right triangles with integer side lengths. The problem reads:

Project Euler Problem 75: Singular integer right triangles
It turns out that 12 cm is the smallest length of wire that can be bent to form an integer sided right angle triangle in exactly one way, but there are many more examples.
12 cm: (3,4,5)
24 cm: (6,8,10)
30 cm: (5,12,13)
36 cm: (9,12,15)
40 cm: (8,15,17)
48 cm: (12,16,20)
In contrast, some lengths of wire, like 20 cm, cannot be bent to form an integer sided right angle triangle, and other lengths allow more than one solution to be found; for example, using 120 cm it is possible to form exactly three different integer sided right angle triangles.
120 cm: (30,40,50), (20,48,52), (24,45,51)
Given that L is the length of the wire, for how many values of L ≤ 1,500,000 can exactly one integer sided right angle triangle be formed?

My solution for this problem is quite bad, as it involves lots of brute force. My solution is very similar to my solution for Problem #9, so I may only provide a sketch of a solution here. Here is my solution:

Solution #1: Brute Force Approach

We know that a general Pythagorean triple in the integers can always be written in the form d(m^2-n^2), d(2mn), d(m^2+n^2). Thus, the perimeter of a general Pythagorean right triangle is d(2m^2+2mn) = 2md(m+n). Thus, for a given length L, it suffices to count the number of solutions to 2md(m+n) = L. This can be done by listing the factors of L to do casework on d. From this point, casework can be done by noting that m<m+n. Here is an implementation of this approach in Python 2.7. It is very similar to my solution for Problem #9.

 '''
 Author: Walker Kroubalkian
 General Pythagorean Triple Approach to Project Euler Problem #75
 '''
 
 import time
 from math import sqrt
 
 def listFactors(n):
     primes = []
     exponents = []
     c = 2
     while(c<=sqrt(n)):
         if(n%c==0):
             primes.append(c)
             t = 0
             while(n%c==0):
                 n/=c
                 t+=1
             exponents.append(t)
         c+=1
     if(n>1):
         primes.append(n)
         exponents.append(1)
     return sorted(listFactorsGivenFactorization(primes, exponents))
 
 def listFactorsGivenFactorization(p,e):
     total = []
     if(len(p) >= 1):
         for x in range(e[0]+1):
             total.append(p[0]**x)
     else:
         return [1]
     previousTotal = listFactorsGivenFactorization(p[1:], e[1:])
     
     actualTotal = []
     for a in total:
         for b in previousTotal:
             actualTotal.append(a*b)
     
     return actualTotal
 
 def countPythagoreanTriples(n):
     if(n%2==1):
         return -1
     found = []
     possibleD = listFactors(n/2)
     n/=2
     for d in possibleD:
         newProduct = n/d
         lowerBound = int(sqrt(newProduct/2))
         upperBound = int(sqrt(newProduct))
         for m in range(lowerBound, upperBound+1):
             if(m>0 and newProduct%m == 0):
                 o = newProduct/m-m
                 if(0<o<m):
                     triple = sorted([d*(m*m-o*o), 2*d*m*o, d*(m*m+o*o)])
                     if triple not in found:
                         found.append(triple)
                         if(len(found)>1):
                             return 2
     
     return len(found)
 
 def projectEulerProblemSeventyFive(n):
     total = 1
     for c in range(13,n+1):
         v = countPythagoreanTriples(c)
         if(v==1):
             total+=1
     return total
 
 start = time.time()
 print projectEulerProblemSeventyFive(1500000)
 print ("--- %s seconds ---" % (time.time()-start))
 
 '''
 Prints
 
 161667
 --- 37.5037260056 seconds ---
 
 for input of n = 1500000
 '''

That may look like a lot of code, but most of it is copy pasted from Problem #9. That code took over 37 seconds to run, so I will definitely need to come back to this problem at some point to look for a more efficient solution.

Thanks for reading! See you tomorrow.

Project Euler Problem #74

Problem #74 concerns the sum of the factorials of the digits in a number. The question reads:

Project Euler Problem 74: Digit factorial chains
The number 145 is well known for the property that the sum of the factorial of its digits is equal to 145:
1! + 4! + 5! = 1 + 24 + 120 = 145
Perhaps less well known is 169, in that it produces the longest chain of numbers that link back to 169; it turns out that there are only three such loops that exist:
169 → 363601 → 1454 → 169
871 → 45361 → 871
872 → 45362 → 872
It is not difficult to prove that EVERY starting number will eventually get stuck in a loop. For example,
69 → 363600 → 1454 → 169 → 363601 (→ 1454)
78 → 45360 → 871 → 45361 (→ 871)
540 → 145 (→ 145)
Starting with 69 produces a chain of five non-repeating terms, but the longest non-repeating chain with a starting number below one million is sixty terms.
How many chains, with a starting number below one million, contain exactly sixty non-repeating terms?

My solution for this problem is quite bad as it involves lots of brute force. Here is my solution:

Solution #1: Brute Force Approach

We simply store the loop length of every number less than 1,000,000 and count the number of starting points which loop with exactly 60 terms. We can do this somewhat dynamically, because once a loop is terminated, all numbers within the loop must have the same loop length. Here is an implementation of this approach in Python 2.7:

 '''
 Author: Walker Kroubalkian
 Brute Force Approach to Project Euler Problem #74
 '''
 
 import time
 
 def digitFactorial(n):
     factorials = [1,1,2,6,24,120,720,5040,40320,362880]
     total = 0
     for x in str(n):
         total+=factorials[int(x)]
     return total
 
 def projectEulerProblemSeventyFour(n,v):
     loops = [-1]*(n)
     loops[0] = 0
     loops[1] = 1
     for x in range(2,n):
         if(loops[x]==-1):
             temp = x
             found = []
             alreadyDone = False
             loopLength = -1
             while(temp not in found):
                 if(temp<n and loops[temp]!=-1):
                     loopLength = loops[temp]
                     alreadyDone = True
                     loops[x] = len(found)+loopLength
                     break
                 found.append(temp)
                 temp = digitFactorial(temp)
             if not alreadyDone:
                 myIndex = found.index(temp)
                 loopLength = len(found)-myIndex
                 for a in range(myIndex,len(found)):
                     loops[found[a]] = loopLength
                 loops[x] = len(found)
     total = 0
     for a in loops:
         if a == v:
             total+=1
     return total
 
 start = time.time()
 print projectEulerProblemSeventyFour(1000000, 60)
 print ("--- %s seconds ---" % (time.time()-start))
 
 '''
 Prints

 402
 --- 3.78305602074 seconds ---
 
 for input of n = 1000000, v = 60.
 '''

That took over 3.7 seconds to run. There must be a more efficient implementation of this solution. I may come back to this problem eventually to look for a faster solution.

Thanks for reading! See you tomorrow.

Project Euler Problem #73

Problem #73 concerns Farey Sequences. The problem reads:

Project Euler Problem 73: Counting fractions in a range
Consider the fraction, n/d, where n and d are positive integers. If n<d and HCF(n,d)=1, it is called a reduced proper fraction.
If we list the set of reduced proper fractions for d ≤ 8 in ascending order of size, we get:
1/8, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2, 4/7, 3/5, 5/8, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 7/8
It can be seen that there are 3 fractions between 1/3 and 1/2.
How many fractions lie between 1/3 and 1/2 in the sorted set of reduced proper fractions for d ≤ 12,000?

My solution to this problem is quite bad. Here is my solution:

Solution #1: Brute Force Approach

It is easy to estimate that the number of fractions with denominator d in this range is roughly phi(d)/6. However, determining the exact value requires some messy casework that I would rather avoid. Thus, I opted to use brute force on this problem. I simply iterated through all of the possible denominators less than or equal to 12,000, and then I iterated through all of the numerators within the range for each possible denominator. I used the Euclidean Algorithm to count the number of numerators which were relatively prime to the denominator. Here is an implementation of this approach in Python 2.7:

 '''
 Author: Walker Kroubalkian
 Euclidean Algorithm Approach to Project Euler Problem #73
 '''
 
 import time
 
 def gcd(a,b):
     if(min(a,b)==0):
         return max(a,b)
     if(a>b):
         return gcd(b,a%b)
     return gcd(a,b%a)
 
 def projectEulerProblemSeventyThree(n):
     total = 0
     for x in range(2,n+1):
         c = int(x/3)
         while(c*3<=x):
             c+=1
         while(c*2<x):
             if(gcd(c,x)==1):
                 total+=1
             c+=1
     return total
 
 start = time.time()
 print projectEulerProblemSeventyThree(12000)
 print ("--- %s seconds ---" % (time.time()-start))
 
 '''
 Prints
 
 7295372
 --- 20.5218679905 seconds ---
 
 for input of n = 12000.
 '''

And with that, we’re done. This solution took over 20 seconds to run. It could probably be greatly optimized by calculating the totient of each value and then using some casework depending on if the divisor is divisible by 2 or 3 or both. I may come back to implement this more efficient solution at some point.

Thanks for reading! See you tomorrow.

Project Euler Problem #72

Problem #72 concerns Farey sequences. The question reads:

Project Euler Problem 72: Counting fractions
Consider the fraction, n/d, where n and d are positive integers. If n<d and HCF(n,d)=1, it is called a reduced proper fraction.
If we list the set of reduced proper fractions for d ≤ 8 in ascending order of size, we get:
1/8, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2, 4/7, 3/5, 5/8, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 7/8
It can be seen that there are 21 elements in this set.
How many elements would be contained in the set of reduced proper fractions for d ≤ 1,000,000?

With a bit of knowledge about number theory, it is not too difficult to find a reasonable solution to this problem. Here is my solution:

Solution #1: Brute Force Approach

We can observe that a common fraction n/d is only proper if gcd(n,d) = 1. Thus, for a fixed value of d, only values of n such that 1<=n<d and gcd(n,d) = 1 will form valid common fractions. Thus, the number of common fractions with denominator d is phi(d), or Euler’s Totient Function applied at d. Thus, it suffices to find the sum of phi(d) for 2<=d<=1,000,000. This problem is equivalent to Problem #70, but less computationally intensive. Here is an implementation of this solution in Python 2.7. It is roughly the same as the solution for Problem #70.

 '''
 Author: Walker Kroubalkian
 Semi-Dynamic Approach to Project Euler Problem #72
 '''
 
 import time
 from math import sqrt
 
 def projectEulerProblemSeventyTwo(n):
     totients = [1,1]
     for x in range(2,n+1):
         v = -1
         if(x%2==0):
             if(x%4==0):
                 v = totients[x/2]*2
             else:
                 v = totients[x/2]
         else:
             c = 3
             myRoot = sqrt(x)
             while(c<=myRoot):
                 if(x%c==0):
                     if(x%(c*c)==0):
                         v = totients[x/c]*c
                     else:
                         v = totients[x/c]*(c-1)
                     break
                 c+=2
             if(c>myRoot):
                 v = x-1
         totients.append(v)
     total = 0
     for x in range(2,n+1):
         total+=totients[x]
     return total
 
 start = time.time()
 print projectEulerProblemSeventyTwo(1000000)
 print ("--- %s seconds ---" % (time.time()-start))
 
 '''
 Prints
 
 303963552391
 --- 2.71775197983 seconds ---
 
 for input of n = 1000000.
 '''

And with that, we’re done. This solution took over 2.7 seconds to run. Because the problem is essentially equivalent to Problem #70, optimizing this problem is equivalent to optimizing that problem. I may come back to these problems at some point.

Thanks for reading! See you tomorrow.

Project Euler Problem #71

Problem #71 concerns Farey Sequences. The question reads:

Project Euler Problem 71: Ordered fractions
Consider the fraction, n/d, where n and d are positive integers. If n<d and HCF(n,d)=1, it is called a reduced proper fraction.
If we list the set of reduced proper fractions for d ≤ 8 in ascending order of size, we get:
1/8, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2, 4/7, 3/5, 5/8, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 7/8
It can be seen that 2/5 is the fraction immediately to the left of 3/7.
By listing the set of reduced proper fractions for d ≤ 1,000,000 in ascending order of size, find the numerator of the fraction immediately to the left of 3/7.

With some knowledge of Farey Sequences, this problem can be solved very efficiently. Here is my solution:

Solution #1: Farey Sequence Approach

It is well known that if n/d is the fraction that immediately precedes a/b in a term of the Farey Sequence, then d*a-b*n = 1. Thus, it suffices to find the maximum value of d less than or equal to 1,000,000 such that d*3 leaves a remainder of 1 when divided by 7. At this point, the numerator can be calculated from that value of d. Here is an implementation of this approach in Python 2.7:

 '''
 Author: Walker Kroubalkian
 Brute Force Approach to Project Euler Problem #71
 '''
 
 import time
 
 def projectEulerProblemSeventyOne(d,a,b):
     c = d
     while(c*a%b!=1):
         c-=1
     return (c*a-1)/b
 
 start = time.time()
 print projectEulerProblemSeventyOne(1000000, 3, 7)
 print ("--- %s seconds ---" % (time.time()-start))
 
 '''
 Prints
 
 428570
 --- 9.77516174316e-06 seconds ---
 
 for input of d = 1000000, a = 3, b = 7.
 '''

And with that, we’re done. This solution could be improved in the general case by first determining the modular inverse of a mod b. However, for values of d as small as 1,000,000, this optimization was not necessary.

Thanks for reading! See you tomorrow.

Project Euler Problem #70

Problem #70 concerns Euler’s Totient Function again. The problem reads:

Project Euler Problem 70: Totient permutation
Euler's Totient function, φ(n) [sometimes called the phi function], is used to determine the number of positive numbers less than or equal to n which are relatively prime to n. For example, as 1, 2, 4, 5, 7, and 8, are all less than nine and relatively prime to nine, φ(9)=6. The number 1 is considered to be relatively prime to every positive number, so φ(1)=1.
Interestingly, φ(87109)=79180, and it can be seen that 87109 is a permutation of 79180.
Find the value of n, 1 < n < 10⁷, for which φ(n) is a permutation of n and the ratio n/φ(n) produces a minimum.

My solution for this problem is quite bad as it takes longer than a minute to run. Thus, I will definitely return to this problem at some point. Here is my solution:

Solution #1: Bad Sieve Approach

We determine the value of Euler’s Totient Function for every value of n less than 1,000,000 with a sieve. We know that for all values of n and all primes p, phi(p*n) = p*phi(n) if n is divisible by p and phi(p*n) = (p-1)*phi(n) otherwise. Thus, we determine the value of the totient function for each number, working our way up with this approach. Once we’re done, we determine the ones that are permutations of the digits of the input and store the one with the maximum value of n/phi(n). Here is an implementation of this approach in Python 2.7:

 '''
 Author: Walker Kroubalkian
 Semi-Dynamic Approach to Project Euler Problem #70
 '''
 
 import time
 from math import sqrt
 
 def isPermutation(a,b):
     return sorted(str(a)) == sorted(str(b))
 
 def projectEulerProblemSeventy(n):
     totients = [1,1]
     minNumerator = -1
     minDenominator = 1
     
     for x in range(2,n+1):
         v = -1
         if(x%2==0):
             if(x%4==0):
                 v = totients[x/2]*2
             else:
                 v = totients[x/2]
         else:
             c = 3
             myRoot = sqrt(x)
             while(c<=myRoot):
                 if(x%c==0):
                     if(x%(c*c)==0):
                         v = totients[x/c]*c
                     else:
                         v = totients[x/c]*(c-1)
                     break
                 c+=2
             if(c>myRoot):
                 v = x-1
         totients.append(v)
         if(x%9==v%9):
             if(isPermutation(x, v)):
                 if(minNumerator == -1):
                     minNumerator = x
                     minDenominator = v
                 elif(minNumerator*v>minDenominator*x):
                     minNumerator = x
                     minDenominator = v
     return minNumerator
 
 start = time.time()
 print projectEulerProblemSeventy(10000000)
 print ("--- %s seconds ---" % (time.time()-start))
 
 '''
 Prints
 
 8319823
 --- 66.285148859 seconds ---
 
 for input of n = 10000000
 '''

And with that, we’re done. As stated above, this solution is very bad, as it takes over a minute to run in Python 2.7 on a decent computer. Thus, I will definitely return to this problem at some point to search for a better solution.

Thanks for reading! See you tomorrow.

Project Euler Problem #69

Problem #69 concerns multiplicative functions, and more specifically, Euler’s Totient Function. The question reads:

Once again, I apologize for not embedding this within WordPress. As it turns out, this problem can be done by hand with a little mathematical knowledge. Here’s my solution:

Solution #1: Mathematical Approach

This solution makes use of the fact that phi(n) is a multiplicative function. A function f on the natural numbers is called multiplicative if for all natural numbers m and n such that gcd(m,n) = 1, f(m)*f(n) = f(m*n). As it turns out, Euler’s Totient function phi(n) is a multiplicative function. As a result, the function F(n) = n/phi(n) is also a multiplicative function, because F(m)*F(n) = m*n/(phi(m)*phi(n)) = (m*n)/phi(m*n) = F(m*n). Thus, we can break this problem down into investigating the function for prime powers.

It is well known that phi(p^n) = (p-1)*p^(n-1) for primes p. Thus, F(p^n) = p/(p-1), regardless of the value of n. Thus, to maximize the value of F(n) while minimizing the value of n, it suffices to multiply n by all the distinct smallest possible values of p. (IE, the smallest primes) Doing this until a product greater than 1,000,000 is reached, we are finished. Here is an implementation of this approach in Python 2.7:

 '''
 Author: Walker Kroubalkian
 Mathematical Approach to Project Euler Problem #69
 '''
 
 import time
 from math import sqrt
 
 def isPrime(n):
     if(n<=1):
         return False
     if(n<4):
         return True
     if(n%2==0):
         return False
     c = 3
     while(c<=sqrt(n)):
         if(n%c==0):
             return False
         c+=2
     return True
 
 def projectEulerProblemSixtyNine(n):
     total = 1
     c = 2
     while(total<=n):
         if(isPrime(c)):
             if(total*c>n):
                 return total
             total*=c
         c+=1
     return total
 
 start = time.time()
 print projectEulerProblemSixtyNine(1000000)
 print ("--- %s seconds ---" % (time.time()-start))
 
 '''
 Prints
 
 510510
 --- 1.90734863281e-05 seconds ---
 
 for input of n = 1000000
 '''

And with that, we’re done. We easily could have done this problem by hand for small inputs such as 1,000,000. Even large inputs can be handled quite quickly.

Thanks for reading! See you tomorrow.

Project Euler Problem #68

Problem #68 concerns magic 5-gon rings that are very similar to magic squares. The question reads:

This is yet another problem that I dreaded solving for years because I thought it would be a pain to implement. Luckily, it’s not too bad with a little brute force. Here’s my solution:

Solution #1: Brute Force Approach

We do casework on the numbers in the outer circles. We know that if 10 is in one of the inner circles, it will appear twice in the string, and thus the string will have 1*2*2+4*1*2+5 = 17 digits. Thus, 10 must appear in one of the outer circles. Therefore, it suffices to check all (9 choose 4) = 126 subsets of the 9 digits to fill the other four outer circles. In addition, we can notice that if the sum of the numbers in the outer circles is t, then the sum of the five rows is t+2*(55-t) = 110-t. Because the sum of the five rows is five times the magic sum, we must have that t is a multiple of 5. From here, it suffices to check all 5! permutations of the 5 remaining digits for each acceptable subset and through brute force, the maximum 16-digit string can be found. Here is an implementation of this approach in Python 2.7:

 '''
 Author: Walker Kroubalkian
 Brute Force Approach to Project Euler Problem #68
 '''
 
 import time
 
 def subset(myList,n):
     if(n == 0):
         return [[]]
     l = len(myList)
     if(n>l):
         return []
     a = myList[0]
     b = subset(myList[1:],n)
     c = subset(myList[1:],n-1)
     for x in c:
         t = x[:]
         t.append(a)
         t = sorted(t)
         b.append(t)
     return b
 
 def complement(a,b):
     c = []
     for x in a:
         if x not in b:
             c.append(x)
     return c
 
 def permutations(myList):
     l = len(myList)
     if(l==1):
         return [myList]
     a = myList[0]
     b = permutations(myList[1:])
     total = []
     for x in b:
         for z in range(l):
             t = x[0:z]
             t.append(a)
             t.extend(x[z:])
             total.append(t)
     return total
 
 def projectEulerProblemSixtyEight():
     maxFound = -1
     digits = [1,2,3,4,5,6,7,8,9]
     arrangements = subset(digits,4)
     for x in arrangements:
         t = 0
         for y in x:
             t+=y
         if(t%5==0):
             theSum = (100-t)/5
             
             a = sorted(x)
             c = complement(digits,x)
             d = permutations(c)
             e = a
             e.append(10)
             for w in d:
                 v = []
                 for z in range(5):
                     temp = theSum-(w[z]+w[(z+1)%5])
                     v.append(temp)
                 v = sorted(v)
                 possible = True
                 for f in range(5):
                     if(v[f]!=e[f]):
                         possible = False
                         break
                 if(possible):
                     s = ""
                     s+=str(e[0])
                     for a in range(5):
                         if(w[a]+w[(a+1)%5] == theSum - e[0]):
                             break
                     s+=str(w[a])+str(w[(a+1)%5])
                     for b in range(1,5):
                         temp = theSum-(w[(a+b)%5]+w[(a+b+1)%5])
                         s+=str(temp)
                         s+=str(w[(a+b)%5])
                         s+=str(w[(a+b+1)%5])
                     if(int(s)>maxFound):
                         maxFound = int(s)
     return str(maxFound)
 
 start = time.time()
 print projectEulerProblemSixtyEight()
 print ("--- %s seconds ---" % (time.time()-start))
 
 '''
 Prints
 
 6531031914842725
 --- 0.0102789402008 seconds ---
 
 for given puzzle.
 '''

And with that, we’re done. Even with the crazy amount of brute force we had to do, the program only took 10 milliseconds to run.

Thanks for reading. See you tomorrow.