project euler

프로젝트 오일러 026

1000 이하의 자연수 중에서, 1/d를 소수로 표현할 때, 순환마디가 가장 긴 수는?

sooop

sooop

— 3 min read
프로젝트 오일러 026
Photo by Keith Misner / Unsplash

문제

26번 문제
1000 이하의 <var>d</var> 중에서 1/<var>d</var> 이 가장 긴 순환마디를 갖는 수는?
사이냅소프트

나눗셈

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

손으로 하는 나눗셈을 따라가며 순환마디를 찾는 과정을 정리해봅시다. 1을 d로 나누는 것입니다.

  1. 나눌 수는 1부터 시작합니다. 혹시 나눌 수가 이전에 나온 적이 있다면, 그 수로부터 지금까지의 단계 수를 세어봅니다. 그 단계수가 순환마디의 길이가 됩니다.
  2. 나눌 수가 d보다 작으면 여기에 10을 곱하고 1번을 다시 시행합니다.
  3. 나눌 수를 넘지 않는 d의 배수를 찾습니다. 그리고 그 차이를 구합니다. 이 값이 나머지입니다. 나머지가 0이라면 순환하지 않는 소수입니다.
  4. 3의 나머지에 10을 곱한 후 1로 돌아갑니다.

자 그럼 이 과정을 파이썬 코드로 옮겨서 순환마디의 길이를 구해봅니다.

from typing import Tuple, List

def divs(d: int) -> Tuple[int, List[int]]:
    q = 10
    ds = []
    ns = []
    while True:
        if q in ds:
            begin = ds.index(q)
            end = len(ds)
            return (end - begin, ns[begin:end])
        x, y = divmod(q, d)
        if y == 0:
            return (0, [])
        ds.append(q)
        ns.append(x)
        q = y * 10

이 코드로 문제에서 예로 든 d=2, 3, ∙∙∙, 9까지의 순환마디를 모두 구하는 지 검증해봅시다.

for i in range(2, 10):
    print(i, divs(i))

# 2 (0, [])
# 3 (1, [3])
# 4 (0, [])
# 5 (0, [])
# 6 (1, [6])
# 7 (6, [1, 4, 2, 8, 5, 7])
# 8 (0, [])
# 9 (1, [1])

이 함수의 리턴 값 중 첫번째 요소가 순환마디의 길이입니다. 순환마디의 길이로 d 들을 정렬하려면, (길이, d)의 튜플을 만들어서 정렬한 후 d만 추출하면 됩니다. 비슷하게 max() 함수도 같은 식으로 이용할 수 있습니다. 

print(max((divs(d)[0], d) for d in range(1, 1001))[1])

답만 구한 것이 아니라 실제로 그 때의 순환마디의 길이와 순환마디도 모두 구한 상태입니다. 제법 긴 숫자니, 궁금하신 분들은 직접 출력해봐도 좋겠죠?

Read more