Let's say that a number with 1 to n used only once in every digit is a pandigital number with n digits: For example, the 5-digit number 15234 is a pandigital with 1 to 5.
7254 has an interesting property. Write 39 x 186 = 7254, and it becomes a pandigital with a number to be multiplied, a number to be multiplied, and a product of 1 to 9.
Find the sum of the products such that the number to be multiplied / the number to be multiplied / the product is Pandigital from 1 to 9.
HINT: Some products have one or more multiply / multiply / product combinations, but count only once. http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2032
There are 9! Pandigital numbers because of their significance. That is, decimal numbers from 0 to less than 9! Correspond to each of the Pandigital numbers. The answer is obtained by converting this decimal number less than 9! To a pandigital number, dividing the pandigital number, and determining whether or not the condition is satisfied. Also, paying attention to HINT, the value of the product is memorized and the same calculation is excluded. (It's probably more efficient to first create a function that simply extracts the product. In addition, since it can be seen from a simple consideration that the product to be calculated cannot be 3 digits or 5 digits, the following code is set to 4 digits.
import math
def create_pandigital(target,n,seeds):
ret = ''
while n > 0:
kaijo = math.factorial(int(n))
(q, r) = (target//kaijo, target%kaijo)
ret += str(seeds.pop(q))
target = r
n -= 1
return ret + str(seeds[0])
def main():
N = 10
MAX = math.factorial(int(N-1))
ans = 0
seeds = []
seq = range(1,N)
ls = []
for target in range(3,MAX):
seeds[:] = seq
n = N - 2
pan = create_pandigital(target, n, seeds)
for i in range(1,4):
if not (pan[:4] in ls) and int(pan[:4]) == (int(pan[4:4+i+1]) * int(pan[4+i+1:])):
ls.append(pan[:4])
ans += int(pan[:4])
break
print ans
main()
Recommended Posts