Problem #111 concerns 10-digit primes with lots of repeated digits. The question reads:
My solution to this problem can best be described as a brute force approach. Here’s my solution:
Solution #1: Brute Force Approach
We simply search for primes with each digit. Through brute force it is possible to check every possible position of the repeated digits. Once the largest number of possible repeated digits is verified, brute force can be used to find every prime with those repeated digits. Here’s an implementation of this approach in Python 2.7:
'''
Author: Walker Kroubalkian
Brute Force Approach to Project Euler Problem #111
'''
import time
from math import sqrt
def isPrime(n):
if(n%2==0):
return False
c = 3
upper = sqrt(n)
while(c<=upper):
if(n%c==0):
return False
c+=2
return True
def convertNDigits(n,x):
a = str(x)
while len(a)<n:
a = "0" + a
return a
def allPermutations(myList):
l = len(myList)
if l==0:
return [[]]
if(l==1):
return [myList]
a = myList[0]
b = allPermutations(myList[1:])
total = []
for x in b:
for z in range(l):
new = x[0:z]
new.append(a)
new.extend(x[z:])
if new not in total:
total.append(new)
return total
def projectEulerProblemOneHundredEleven(n):
final = 0
for d in range(0,10):
for m in range(n,-1,-1):
total = 0
order = []
for x in range(m):
order.append(1)
for x in range(m,n):
order.append(0)
v = allPermutations(order)
for x in range(0,10**(n-m)):
a = convertNDigits(n-m, x)
possible = True
for q in a:
if q == str(d):
possible = False
break
if possible:
for z in v:
s = ""
b = 0
for y in z:
if y==1:
s+=str(d)
else:
s+=a[b]
b+=1
if int(s[0])>0 and isPrime(int(s)):
total+=int(s)
if total>0:
final+=total
break
return final
start = time.time()
print projectEulerProblemOneHundredEleven(10)
print ("--- %s seconds ---" % (time.time()-start))
'''
Prints
612407567715
--- 0.370451927185 seconds ---
for input of n = 10.
'''
And with that, we’re done. The main problems here were implementing casework based on potential leading zeroes. This solution was more than efficient enough for this problem, so I probably will not return to this problem.
Thanks for reading! See you tomorrow.
The Inner Machinations of Walker 