[Project Euler] Problem 33

원문: Problem 33

The fraction ⁴⁹/₉₈ is a curious fraction, as an inexperienced mathematician in attempting to simplify it may incorrectly believe that ⁴⁹/₉₈ = ⁴/₈, which is correct, is obtained by cancelling the 9s.

We shall consider fractions like, ³⁰/₅₀ = ³/₅, to be trivial examples.

There are exactly four non-trivial examples of this type of fraction, less than one in value, and containing two digits in the numerator and denominator.

If the product of these four fractions is given in its lowest common terms, find the value of the denominator.

분수 ⁴⁹/₉₈는 특이한 분수이다. 단순하게 만드는 시도에서 경험이 부족한 수학자는 ⁴⁹/₉₈ = ⁴/₈이 9를 소거하여 얻는 것이 맞는 것이라고 부정확하게 믿게 된다.

우리는 단순한 예제로써, ³⁰/₅₀ = ³/₅과 같은 분수를 생각할 수도 있다.

이러한 분수의 유형으로, 값이 1보다 작고, 분자와 분모에 2자리 숫자를 포함하는 '단순하지 않은' 예제가 정확히 4개 있다.

이 4개의 분수의 곱이 최소 공통 항으로 주어진다면, 분모의 값을 찾아라.

Python

약간의 수학을 가미해서 풀었다.

10x+y / 10z+x = y / z와 10y+x / 10x+z = y / z라는 식을 만족하면 되는 x, y, z를 찾으면 된다. 이때, x, y, z는 1 이상 9 이하이고, 그 결과가 1보다 작아야 하므로 y >= z 가 될 수 없다. (10y+x / 10z+x = y / z 와 같은 식도 있는데, 이 경우는 x가 0으로, 위에서 말한 단순한 예제에 속한다.)

import fractions

result = [1, 1]
for x in range(1, 10):
    for y in range(1, 10):
        for z in range(1, 10):
            if y >= z:
                continue
            numerator = 10 * x + y
            denominator = 10 * z + x
            if numerator * z == denominator * y:
                result[0] *= numerator
                result[1] *= denominator
        
            numerator = 10 * y + x
            denominator = 10 * x + z
            if numerator * z == denominator * y:
                result[0] *= numerator
                result[1] *= denominator

print(fractions.Fraction(*result).denominator)

접기