Problem #60 is one of the many Project Euler problems that involves manipulating digits in prime numbers. The question reads:
Project Euler Problem 60: Prime pair sets
The primes 3, 7, 109, and 673, are quite remarkable. By taking any two primes and concatenating them in any order the result will always be prime. For example, taking 7 and 109, both 7109 and 1097 are prime. The sum of these four primes, 792, represents the lowest sum for a set of four primes with this property.
Find the lowest sum for a set of five primes for which any two primes concatenate to produce another prime.
My solution for this question barely doesn’t run in under 30 seconds, so I definitely need to retry this problem at some point. Here is my current solution to this problem:
Solution #1: Brute Force Approach
We simply iterate through the possible values of the largest prime in a quintuple, checking all pairs of primes for the concatenation property until 5 primes are found for which all pairs within the quintuple have the concatenation property. This can be done by manually checking each new maximum prime with all smaller primes and storing a list of all concatenation primes respective to each new prime. (Sorry if that’s confusing, I’m not sure how to word it) For all primes which concatenate with at least 4 smaller primes, we can list all 4-element subsets of the smaller primes which concatenate with it and then check all pairs within each of those subsets. Once a subset satisfies the condition for all pairs, we’re done. Here is an implementation of this approach in Python 2.7:
'''
Author: Walker Kroubalkian
Brute Force Approach to Project Euler Problem #60
'''
import time
from math import sqrt
def isPrime(n):
if(n%2==0):
return False
c = 3
while(c<=sqrt(n)):
if(n%c==0):
return False
c+=2
return True
def concatenatePrime(a,b):
p1 = int(str(a)+str(b))
if not isPrime(p1):
return False
return isPrime(int(str(b)+str(a)))
def subsets(myList,n):
a = myList[0]
l = len(myList)
if(n>l):
return []
if(n==l):
return [myList]
if(n==0):
return [[]]
first = subsets(myList[1:],n-1)
total = subsets(myList[1:],n)
for x in first:
c = x[:]
c.append(a)
total.append(sorted(c))
return total
def projectEulerProblemSixty(n):
consideredPrimes = []
primeConcats = []
c = 3
found = 0
indexCheck = subsets([0,1,2,3],2)
current = [-1]
minSum = -1
while(found<n):
if(isPrime(c)):
if c not in consideredPrimes:
concatPossible = []
l = len(consideredPrimes)
for a in range(l):
if(concatenatePrime(consideredPrimes[a], c)):
concatPossible.append(a)
primeConcats[a].append(l)
if(len(concatPossible)>=4):
toCheck = subsets(concatPossible,4)
for a in toCheck:
haveFound = False
for b in indexCheck:
x = b[0]
y = b[1]
if a[x] not in primeConcats[a[y]]:
haveFound = True
break
if not haveFound:
found+=1
e = [c]
for z in a:
e.append(consideredPrimes[z])
subTotal = 0
for t in e:
subTotal+=t
if(current!=[-1]):
if(subTotal<minSum):
current = e
minSum = subTotal
else:
current = e
minSum = subTotal
consideredPrimes.append(c)
primeConcats.append(concatPossible)
c+=2
return minSum
start = time.time()
print projectEulerProblemSixty(1)
print ("--- %s seconds ---" % (time.time()-start))
'''
Prints
26033
--- 30.2959289551 seconds ---
for input of n = 1.
'''
And with that we’re done. Looking back on this, I really need to add some comments and make my code more clean. It’s pretty hideous and it took me a while to figure out my own code when writing this post (I wrote this code several months ago) In addition, I need to look for a more efficient algorithm because this took over 30 seconds to run.
Thanks for reading! See you tomorrow.
The Inner Machinations of Walker 