Consider the fraction, n/d, where n and d are positive integers. If n<d and HCF(n,d)=1, it is called a reduced proper fraction.
If we list the set of reduced proper fractions for d ≤ 8 in ascending order of size, we get:
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
It can be seen that there are 21 elements in this set.
How many elements would be contained in the set of reduced proper fractions for d ≤ 1,000,000?
n, d가 양의 정수인 분수 n/d를 생각해 보자. n<d이고 HCF(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
이 집합에는 21개 원소가 있는 것을 알 수 있다.
d가 1,000,000 이하일 때, 약분된 진분수에는 몇 개의 원소가 있는가?
--------------------------------------------------------------------------
71번 문제에서 몇글자 다른데 전혀 다른 문제가 되어 있다. 71번과 마찬가지로 분자가 분모보다 작고, 분자와 분모의 최대공약수가 1이 되는 분수 집합을 전제로 하고, 이번 문제에서는 그런 약분된 진분수가 분모가 1,000,000 이하인 경우 몇 개 있는지 물어보고 있다.
71번 문제에서는 전체 분수 값이 정렬된 상태를 요구했지만, 이번 문제는 정렬하는 과정 없이 답을 구할 수 있으므로 조금 더 쉽게 접근이 가능할 것 같다. 특정 분모 숫자에 대한 공약수가 1인 분자의 갯수는 69번 문제, 70번 문제를 해결할 때 사용했던 Φ(n)을 구하는 것과 동일하다. 다만, 69, 70번은 특정 조건을 만족하는 소수를 대상으로 계산하면 되었지만, 이번 문제는 가능한 분모 전체를 대상으로 구해야 하기 때문에 시간을 더 많이 요구하고 있다.
기존 문제에 사용한 방법을 이용해서 계산해봤지만, 1만개 계산에 6분 이상 소요되면서 전체를 계산하려면 최소 10시간 이상이 필요할 것으로 전망되어 다시 난감함을 느끼게 되었다. 특정 숫자에 대한 파이값을 계산하는 공식을 구글링을 통해 찾아 적용했는데(예를 들어 3과 5가 약수인 Φ(75)=75*(1-1/3)*(1-1/5)), 그래도 생각보다 시간이 많이 소요되었다. 몇가지 최적화를 해서 2시간 이상 실행 끝에 오답을 구했다.
각 숫자를 소인수분해 해서 공식을 적용했는데 프로그램을 잘 못 구성했는지 오답이 나왔고, 발상의 전환을 해서 소수가 나오면 해당 수(i)의 모든 배수를 대상으로 미리 (i-1/i)를 곱하는 형태로 구현했더니 기존 시간에 비해 터무니없이 빠르게 정답을 구할 수 있었다.
51번 이후에는 문제들은 이해되고 해결방안을 구현 가능하지만 극심한 성능문제가 발생하는 경우가 많이 나오고 있다. 단순 알고리즘 구현보다는 정수론 같은 수학을 이해하고 그것을 기반으로 효율적인 알고리즘 구현이 필요한 상황이 나오고 있어서, 수학공부까지 하면서 파이썬 공부를 위해 오일러 프로젝트를 계속 할 것인지 고민하는 상황이 계속 나오고 있는 것 같다.