Problem #51 is one of the many problems that involves manipulating digits in prime numbers. The question reads:
Project Euler Problem 51: Prime digit replacements
By replacing the 1st digit of the 2-digit number *3, it turns out that six of the nine possible values: 13, 23, 43, 53, 73, and 83, are all prime.
By replacing the 3rd and 4th digits of 56**3 with the same digit, this 5-digit number is the first example having seven primes among the ten generated numbers, yielding the family: 56003, 56113, 56333, 56443, 56663, 56773, and 56993. Consequently 56003, being the first member of this family, is the smallest prime with this property.
Find the smallest prime which, by replacing part of the number (not necessarily adjacent digits) with the same digit, is part of an eight prime value family.
My solution for this problem definitely falls into the category of brute force. Here’s my solution:
Solution #1: Brute Force Approach
First, we can notice that the 10 different values which are formed by replacing sections of a prime number with the digits 0-9 should form an arithmetic sequence. If the common difference of this arithmetic sequence is not a multiple of 3, then we would expect at least 3 of the values to be multiples of 3, and thus, the family could have at most 7 primes. Thus, for a 8 prime value family to be found, the common difference should be a multiple of 3. Because the common difference for an arithmetic sequence created in this manner is the sum of powers of 10 representing which digits are being replaced, the common difference can only be a multiple of 3 if the number of digits that is being replaced is a multiple of 3. Thus, it suffices to investigate changing 3 of the digits in primes.
From this point, I proceed by brute force. I iterate through all of the prime numbers that could be the minimum number in the prime family. Then I create arrays representing the positions of the ‘0’, ‘1’, and ‘2’ digits in the prime. Then I list all subsets of each of these arrays with exactly 3 elements. For each subset, I list the possible numbers that can be found by increasing the respective digits in the positions in the subset. Finally, I count the number of primes in the set and check if it is greater than or equal to 8. Once a prime is found which generates at least 8 primes, the problem is solved. Here is an implementation of this long approach in Python 2.7:
'''
Author: Walker Kroubalkian
Brute Force Approach to Project Euler Problem #51
'''
import time
from math import sqrt
def listSubsets(myList,n):
l = len(myList)
if(l<n):
return []
if(n==0):
return [[]]
a = myList[0]
first = listSubsets(myList[1:],n)
second = listSubsets(myList[1:],n-1)
total = first[:]
for b in second:
c = b[:]
c.append(a)
total.append(sorted(c))
return total
def primePossibilities(x):
a = str(x)
l = len(a)
possibilities = []
twos = []
ones = []
zeros = []
for y in range(l):
v = int(a[y])
if(v==2):
twos.append(y)
elif(v==1):
ones.append(y)
elif(v==0):
zeros.append(y)
zeroTriples = listSubsets(zeros, 3)
oneTriples = listSubsets(ones, 3)
twoTriples = listSubsets(twos, 3)
for triple in zeroTriples:
firstIndex = triple[0]
secondIndex = triple[1]
thirdIndex = triple[2]
total = [x]
for c in range(1,10):
letter = str(c)
total.append(int(a[0:firstIndex] + letter+ a[firstIndex+1:secondIndex]+letter + a[secondIndex+1:thirdIndex]+letter+a[thirdIndex+1:]))
possibilities.append(total)
for triple in oneTriples:
firstIndex = triple[0]
secondIndex = triple[1]
thirdIndex = triple[2]
total = [x]
for c in range(2,10):
letter = str(c)
total.append(int(a[0:firstIndex] + letter+ a[firstIndex+1:secondIndex]+letter + a[secondIndex+1:thirdIndex]+letter+a[thirdIndex+1:]))
possibilities.append(total)
for triple in twoTriples:
firstIndex = triple[0]
secondIndex = triple[1]
thirdIndex = triple[2]
total = [x]
for c in range(3,10):
letter = str(c)
total.append(int(a[0:firstIndex] + letter+ a[firstIndex+1:secondIndex]+letter + a[secondIndex+1:thirdIndex]+letter+a[thirdIndex+1:]))
possibilities.append(total)
return possibilities
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 projectEulerProblemFiftyOne(n):
found = 0
possible = 3
current = -1
while(found<n):
if(isPrime(possible)):
a = primePossibilities(possible)
for replaced in a:
total = 0
for x in replaced:
if isPrime(x):
total+=1
if(total>=8):
current = possible
found+=1
possible+=2
return current
start = time.time()
print projectEulerProblemFiftyOne(1)
print ("--- %s seconds ---" % (time.time()-start))
'''
Prints
121313
--- 0.314001083374 seconds ---
for input of n=1
'''
And with that, we’re done. The solution surprisingly ran in only a third of a second. I expected the answer to be at least a few orders of magnitude higher. I may come back to this question eventually to look for a more efficient approach.
Thanks for reading! See you tomorrow.
The Inner Machinations of Walker 