【Project Euler】Problem 38: 倍数の連結でパンデジタル

• 本記事はProjectEulerの「100番以下の問題の説明は記載可能」という規定に基づいて回答のヒントが書かれていますので、自分である程度考えてみてから読まれることをお勧めします。

問題 38. 倍数の連結でパンデジタル

原文 Problem 38: Pandigital multiples

問題の要約：以下の例のように$n>1$に$1,2,3, \dots$掛けたものを連結した9桁のパンデジタル数の最大値を求めよ

192 \times 1 = 192 \\
192 \times 2 = 384 \\
192 \times 3 = 576 \\
192 384 576 \rightarrow パンデジタル数　\\ \\
9 \times 1 = 9 \\
9 \times 2 = 18 \\
9 \times 3 = 27 \\
9 \times 4 = 36 \\
9 \times 5 = 45 \\
918273645 \rightarrow パンデジタル数　\\ \\

Problem 32: パンデジタル数の積ではitertools.permutationsを使いました。今回も同様ですが最大値だけを求めれば良いので大きい順に生成します。permutationsは「 iterable に応じた辞書式順序で出力されます」とのことなので元の文字列を"987654321"します。もし最大値だけでなくすべての答えを見たければ最後のbreakを消せばOKです。

from itertools import permutations

def PanProd(pans):
  for prds in [pans[:i] for i in range(1,4+1)]: # left substring of pans
    n, j = int(prds), 2
    while len(prds) < len(pans):  # concating the multiples 
      prds += str(n*j)
      j += 1
    if prds == pans:   # check prod concat equals to original pans
      return n
  return 0

# generate pandigital numbers in decending order
for pans in permutations("987654321"):  
  pans = ''.join(pans)
  n = PanProd(pans)
  if n > 0:
    print(f"Answer: {pans} n={n}")
    break

（開発環境：Google Colab）