[Project Euler] Problem 26

원문: Problem 26

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을 포함한다. 분모가 2부터 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의 값을 찾아라.

정확하게 순환부를 찾기 위한 알고리즘을 생각했으나 찾지 못하고 검색을 해보았는데, 검색 결과에서 한 가지 아이디어를 얻을 수 있었다. 피제수를 제수로 나누는 연산이 한 번이라도 반복되면 그 부분에 대해서 순환이 생긴다는 것이다.(http://www.buggymind.com/123의 글의 댓글에서 아이디어를 얻음)

따라서 피제수를 제수로 나눈 나머지를 구했을 때 그 나머지가 지금까지 연산한 나머지 중에서 같은 것이 존재하게 되면 그 부분 이후로는 순환부라는 것을 알 수 있다.

Python

def check_cycle(d):
    remain_list = []
    dividend = 1 # 피제수
    n = 0 # 현재 피제수의 인덱스
    while True:
        remain = dividend % d # 나머지
        if remain in remain_list:
            return n - remain_list.index(remain)
        else:
            remain_list.append(remain)
            dividend = remain * 10
            n += 1

max_d = d = 2 
max_n = 0 
while d < 1000: 
    temp = check_cycle(d)
    if temp > max_n:
        max_n = temp
        max_d = d 
    d += 1

print(max_d)

접기