Problem #38 is one of the many problems on Project Euler that requires permutations of the digits 1-9, also known as pandigitals. The question reads:
Project Euler Problem 38: Pandigital multiples
Take the number 192 and multiply it by each of 1, 2, and 3:
192 × 1 = 192
192 × 2 = 384
192 × 3 = 576
By concatenating each product we get the 1 to 9 pandigital, 192384576. We will call 192384576 the concatenated product of 192 and (1,2,3)
The same can be achieved by starting with 9 and multiplying by 1, 2, 3, 4, and 5, giving the pandigital, 918273645, which is the concatenated product of 9 and (1,2,3,4,5).
What is the largest 1 to 9 pandigital 9-digit number that can be formed as the concatenated product of an integer with (1,2, ... , n) where n > 1?
You can probably guess that my solution to this problem will involve brute force. However, there is a way to make the brute force more efficient with information in the problem.
Solution #1: Brute Force Approach
Using the fact that 918273645 is a pandigital number with this property, we know that the largest pandigital number must be larger than 918273645. Thus, the number that generates the largest pandigital number should be greater than a prefix of 918273645. If it has 2 digits, it should be greater than or equal to 91. If it has 3 digits, it should be greater than or equal to 918. Continuing with this reasoning, we only have to check numbers between each prefix and the next smallest power of 10. Here is an implementation of this method in Python 2.7:
'''
Author: Walker Kroubalkian
Brute Force Approach to Project Euler Problem #38
'''
import time
from collections import Counter
def pandigital(n):
a = str(n)
c = 2
while(len(a)<9):
a+=str(n*c)
c+=1
if(len(a)!=9):
return -1
if Counter(a) == Counter("123456789"):
return int(a)
return -1
def projectEulerProblemThirtyEight(maxKnown):
c = 2
temp = maxKnown
while(c<=4):
start = int(str(maxKnown)[0:c]) + 1
while(start<10**c):
v = pandigital(start)
if(v>temp):
temp = v
start+=1
c+=1
return temp
start = time.time()
print projectEulerProblemThirtyEight(918273645)
print ("--- %s seconds ---" % (time.time()-start))
'''
Prints
932718654
--- 0.00893306732178 seconds ---
for input of n = 918273645
'''
As shown above, brute force iteration can be fairly efficient if you put a bit of thought into using it.
Thanks for reading!
The Inner Machinations of Walker 