Problem #43 is yet another problem that involves digits and primes. This time, we’re looking at pandigital numbers where each subsequence is divisible by a different prime. Here’s the problem:
Project Euler Problem 43: Sub-string divisibility
The number, 1406357289, is a 0 to 9 pandigital number because it is made up of each of the digits 0 to 9 in some order, but it also has a rather interesting sub-string divisibility property.
Let d1 be the 1st digit, d2 be the 2nd digit, and so on. In this way, we note the following:
d2d3d4=406 is divisible by 2
d3d4d5=063 is divisible by 3
d4d5d6=635 is divisible by 5
d5d6d7=357 is divisible by 7
d6d7d8=572 is divisible by 11
d7d8d9=728 is divisible by 13
d8d9d10=289 is divisible by 17
Find the sum of all 0 to 9 pandigital numbers with this property.
My solution for this problem is probably one of the least optimized brute force solutions of all of my solutions for the first 50 problems. Therefore, I definitely want to look at this problem again in the future. Here’s my solution:
Solution #1: Brute Force Approach
We simply list all 0-9 pandigital numbers and check each one for the given property. By converting each number to a string and using Python’s interface for accessing substrings, this can be done very easily. It is also worth noting that it is better to start checking for the larger primes as less numbers will have substrings that are divisible by the larger primes. Here is an implementation of this method in Python 2.7:
'''
Author: Walker Kroubalkian
Brute Force Approach to Project Euler Problem #43
'''
import time
def listPermutations(myList):
if(len(myList)==1):
return [myList]
a = myList[0]
b = listPermutations(myList[1:])
total = []
for x in b:
for c in range(len(x)+1):
temp = x[0:c]
temp.append(a)
temp.extend(x[c:])
total.append(temp)
return total
def projectEulerProblemFortyThree(myList):
a = listPermutations(myList)
total = 0
for x in a:
y = ""
for b in x:
y+=str(b)
if(y[0]!="0" and int(y[7:10])%17==0 and int(y[6:9])%13==0 and int(y[5:8])%11==0 and int(y[4:7])%7==0 and int(y[3:6])%5==0 and int(y[2:5])%3==0 and int(y[1:4])%2==0):
total+=int(y)
return total
start = time.time()
print projectEulerProblemFortyThree([0,1,2,3,4,5,6,7,8,9])
print ("--- %s seconds ---" % (time.time()-start))
'''
Prints
16695334890
--- 10.1015229225 seconds ---
for input of myList =[0,1,2,3,4,5,6,7,8,9]
'''
Oh boy. This solution took over 10 seconds to run! I definitely need to return to this problem. However, it is nice to know that Python is able to generate all 3628800 permutations of the first 10 numbers in only 10 seconds, even with my sloppy recursive method.
Thanks for reading!
The Inner Machinations of Walker 