분자가 1일 분수를 단위 분수라고 합니다. 분모가 2에서 10까지인 단위 분수는 아래와 같습니다.
\begin{array}{lll} 1/2 & = & 0.5 \\ 1/3 & = & 0.\dot{3} \\ 1/4 & = & 0.25 \\ 1/5 & = & 0.2 \\ 1/6 & = & 0.1666 ... = 0.1\dot{6} \\ 1/7 & = & 0.142857142857... = 0.\dot{1}4285\dot{7} \\ 1/8 & = & 0.125 \\ 1/9 & = & 0.1111.... = 0.\dot{1} \\ 1/10 & = & 0.1 \end{array}숫자 위에 찍힌 점은 순환마디를 나타내는데, 1/6의 경우 순환마디는 ‘6’으로, 0.166666… 처럼 6이 무한히 반복됨을 뜻합니다. 같은 식으로 1/7은 6자리의 순환마디(142857)를 가집니다. d를 1000이하의 정수라고 할 때, 단위분수 1/d의 순환마디가 가장 긴 수는 무엇입니까?
http://euler.synap.co.kr/prob_detail.php?id=26
접근
분수를 소수로 표현하기 위해서는 실제로 나눗셈을 계속해나가면 된다. 단위 분수의 경우 1을 분모로 나누고, 그 나머지에 10을 곱해서 다시 분모로 나누고, 그 나머지에 10을 곱해서 분모로 나누는 것을 반복한다. 이 과정에서 한 번 나왔던 나머지가 다시 나오면 같은 나머지가 반복되는 구간이 순환마디가 된다. 여기서는 순환마디의 길이만 구하면 된다.
참고로 분모의 소인수가 2와 5만 존재하는 경우, 이 단위 분수는 유한소수가 되며, 순환마디의 길이가 0이 되어야 한다. 이 부분만 고려해주면 쉽게 풀리는 문제이다.
def len_repeat(n: int) -> int:
n = 1
paths: list[int] = []
while n != 0:
q, n = divmod(n, d)
if n in paths:
return len(paths) - path.index(n)
paths.append(n)
n *= 10
return 0
# 확인
for i in range(2, 11):
print(i, len_repeat(i))
제대로 작동하는 것이 확인되었으니, 이제 가장 긴 순환마디를 가지는 숫자를 찾아보자.
print(max((len_repeat(x), x) for x in range(2, 1001))[1])참고로 정답의 순환마디 길이는 무려 982나된다. (0010172939979654120040691759918616480162767039674465920651068158697863682604272634791454730417090539165818921668362156663275686673448626653102746693794506612410986775178026449643947100712105798575788402848423194303153611393692777212614445574771108850457782299084435401831129196337741607324516785350966429298067141403865717192268565615462868769074262461851475076297049847405900305188199389623601220752797558494404883011190233977619532044760935910478128179043743641912512716174974567650050864699898270600203458799593082400813835198372329603255340793489318413021363173957273652085452695829094608341810783316378433367243133265513733468972533062054933875890132248219735503560528992878942014242115971515768056968463886063072227873855544252288911495422177009155645981688708036622583926754832146490335707019328585961342828077314343845371312309257375381485249237029501525940996948118006103763987792472024415055951169888097660223804679552390640895218718209562563580874872838250254323499491353)
이는 실제로 위 함수를 약간 수정해서도 만들 수 있는데, 임의 정밀도를 사용할 수 있는 Decimal 타입을 사용하여 계산할 수도 있다. 정밀도 값을 크게 설정한 후 두 개의 Decimal 값을 나누면 원하는 개수의 유효숫자를 구할 수 있다.
from decimal import Decimal, getcontext
getcontext().prec = 1100
print(Decimal(1) / Decimal(983))
# Decimal('0.00101729....')