오일러 프로젝트 71
오일러 프로젝트 71 번 문제는 약간 쉬어가는 문제인지 이전의 몇 개 문제보다는 조금 쉽다. 바로 3/7 바로 앞에 오는 분모 백만 이하의 기약진분수를 찾는 문제이다.
n과 d가 양의 정수이고 n < d 인 분수 n/d을 GCD(n, d) = 1 일 때 기약 진분수라고 부르기로 합니다. d <= 8 인 기약 진분수들을 커지는 순으로 늘어놓으면 다음과 같습니다.
1/8, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2, 4/7, 3/5, 5/8, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 7/8
위에서 보듯이 3/7 바로 앞에는 2/5가 오게됩니다. d < 1,000,000 인 기약 진분수들을 커지는 순으로 늘어놓았을 때, 3/7 바로 앞에 오는 수의 분자는 얼마입니까?
접근
일일이 찾아내는 것은 답이 없다. 우리가 알고 싶은 것은 3/7보다 아주 근소하게 작은 기약 진분수이다. 만약 3/7 근처에 있는 기약 진분수의 집합 Q가 있다고 가정하자. 이들 값들은 모두 “거의 3/7″일 것이다. 그렇다면 3/7과의 거리가 짧으려면 분모가 크면 된다. 따라서 3/7을 넘지않으면서 가장 큰 분모를 가지는 분자/분모가 이에 근접할 가능성이 크다. (왜냐하면 분모의 크기가 한정되어 있기 때문에 무한정 늘어날 수는 없기 때문이다.)
예를 들어 9999에 대해서 생각해보자. 사실 어떤 임의의 수도 상관없다.
그런데 이 값은 기약 진분수가 아니다. 분모분자는 9999라는 거대한 공약수를 가지고 있기 때문에 3/7로 약분된다. 하지만 우리가 관심있는 값은 3/7을 넘지 않으면서 약분이 되지 않을 값이다.
이 값은 3/7에 매우 가까운 기약분수이다. 그리고 9999보다 큰 수를 사용하면 사용할 수록 분자와 분모값은 커질 것이고, 기약 분수의 특성상 분자와 분모가 함께 커지면 그 값은 커지고, 따라서 3/7에 더 가까운 수가 된다.
결국 답은 (999,999 * 3) / 7 이 된다.
풀이
코드가 필요 없는 문제이긴 한데, 굳이 검증해보고 싶다면 다음과 같이 쓸 수 있다.
/// Swift
print((1...999_999).filter{ $0 % 7 != 0 }.map{ 3 * $0 / 7}.max()!)
/// Python :: 백만개 분수를 만들어서 가장 큰 값의 분자를 출력한다.
from fractions import Fraction
print(max(Fraction(x*3//7, x) for x in range(1, 1000000)).numerator)다른 접근
분모가 N이하인 0~1 사이의 기약 진분수의 집합을 페어리 수열이라 한다.
