프로젝트 오일러 026

나눗셈

분수를 소수로 표현하기 위해서는 분자를 분모로 나누는 나눗셈을 실제로 시행해보면 됩니다. 나눗셈을 손으로 푸는 과정을 진행해나가다가, 나눠야하는 수가 이전에 나온 적이 있는 값이라면, 그 만큼의 주기가 다시 반복된다는 의미입니다. (순환소수의 반복주기는 항상 맨 앞부터 시작하지는 않습니다.)

1을 임의의 자연수 d로 나누는 과정을 손으로 계산하는 방법을 따라가 봅시다.

1. 피제수를 나눌 수 있는 가장 큰 0~9사이의 정수를 찾고 이 값을 기록합니다.
2. 이 수와 제수를 곱하고 피제수에서 뺀 나머지를, 1에서 찾은 정수와 쌍으로 기록합니다.
3. 나머지가 이전에 구한 나머지와 같다면 이후의 계산은 그 구간을 반복할 것입니다.
4. 나머지가 0이 되었다면 이 값은 순환소수가 없습니다.
5. 나머지에 10을 곱하고 다시 1로 돌아갑니다.

자 그럼 이 과정을 파이썬 코드로 옮겨서 순환마디의 길이를 구해봅시다. 가장 긴 순환마디와 그 때의 d를 쌍으로 리턴하면 됩니다. 검증을 위해 이때의 순환마디도 같이 리턴하도록 해서 작은 범위에서 순환마디가 제대로 계산되는지 확인해보는 과정도 필요합니다.

def divs(d: int) -> tuple[int, int, list[int]]:
    ''' 1/d를 계산하여 순환마디의 길이와 순환마디를 구합니다.'''
    A = 1
    rs = []
    ns = []
    while True:
        x, y = divmod(A, d)

        if y == 0:
            # 나머지가 0이면 순환마디 없음
            return (0, d, [])

        if y in rs:
            # 중복된 나머지가 나타났다면,
            # 이전까지의 나머지 목록을 버리고 반환
            begin = rs.index(y)
            end = len(rs)
            return (end - begin, d, rs[begin:end])

        ns.append(x)
        rs.append(y)

        A = y * 10

print(max(divs(i+1)[:2] for i in range(1000)))