【Project Euler】Problem 33: 桁を消して約分

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

問題 33：桁を消して約分

原文 Problem 33: Digit cancelling fractions

問題の要約：以下の例のように1より小さい分子・分母ともに2桁の分数の共通の1つの数字を消したときに約分になっているような分数（4つある）の積を約分したときの分母を求めよ

\frac{4 \underline{9}}{\underline{9}8}=\frac{4}{8}

条件を満たす分数は以下のような形をしているので、$n,d,i$を$n<d$の条件で全探索します。答えは4つの分数の積を約分した分母なので、pythonのFractionモジュールを使って自動的に約分しました。

\frac{10n+i}{10i+d} = \frac{n}{d} \ \ \ \   (n<d)

import itertools
from fractions import Fraction

prd = Fraction(1)
for n, d in itertools.combinations(range(1,10),2):
  for i in range(1,10):
    if (10*n+i)*d == (10*i+d)*n:
      print((10*n+i),(10*i+d), n, d )
      prd *= Fraction(n,d)

print(f"Answer is {prd.denominator}, (prodct={prd})")
#16 64 1 4
#19 95 1 5
#26 65 2 5
#49 98 4 8
#Answer is 100, (prodct=1/100)

（開発環境：Google Colab）