A unit fraction contains 1 in the numerator. The decimal representation of the unit fractions with denominators 2 to 10 are given:
1/2=0.5
1/3=0.(3)
1/4=0.25
1/5=0.2
1/6=0.1(6)
1/7=0.(142857)
1/8=0.125
1/9=0.(1)
1/10=0.1
Where 0.1(6) means 0.166666⋯, and has a 1-digit recurring cycle. It can be seen that 1/7 has a 6-digit recurring cycle.
Find the value of d<1000 for which 1/d contains the longest recurring cycle in its decimal fraction part.
분자가 1인 분수를 단위 분수(unit fraction)이라 한다. 분모가 2에서 10인 단위 분수는 다음과 같이 10진수로 나타낼 수 있다:
1/2=0.5
1/3=0.(3)
1/4=0.25
1/5=0.2
1/6=0.1(6)
1/7=0.(142857)
1/8=0.125
1/9=0.(1)
1/10=0.1
0.1(6)은 0.166666⋯을 의미하고, 1자리의 반복 사이클을 가지고 있다. 1/7은 6자리의 순환마디가 있음을 알 수 있다. d<1000일 때, 1/d이 가장 긴 순환마디를 가지는 d를 찾으시오.
--------------------------------------------------------------------------
분수 값에서 순환소수 값을 구하는 방법을 알면 쉽게 풀 수 있고, 이것은 초등학교 산수 수준의 문제인 것 같기는 한데 어떻게 구하는 지 전혀 아이디어가 떠오르지 않아 보류하고 지나갔던 문제이다.
다시 봐도 아이디어가 떠오르지 않아 분수를 순환소수로 구하는 요령을 인터넷으로 검색하고 그것을 파이썬 코드로 만들어서 답을 구할 수 있었다. 9를 계속 만들어가면서 나눠지면 그 때 있는 9의 갯수가 순환마디의 크기를 뜻하는 것이 되는데, 예를 들어, 분모가 6일 때 90을 나눌 수 있고, 이 때 9는 1개 있으므로 순환마디는 1이고, 분모가 7일 때 999999을 나눌 수 있고, 이 때 9가 6개 있으므로 순환마디 6이 된다.
2~999까지의 반복문 안에, 9의 갯수(순환마디)를 찾는 2개의 반복문으로 구성해서 문제를 풀었고, 답을 구하는데 28초가 걸려 그리 성능이 좋은 방법으로 구현하지 않았다는 것을 알았지만 묵혀둔 미결 문제를 해결한 기쁨이 더 컸다.