26. Reciprocal cycles

1. 개요

문제는 이곳에서 확인할 수 있다. 1보다 크고 1000보다 작은 어떤 자연수 \(d\)로 순환소수 \(1/d\)를 만들 수 있다. 예를 들어 \(1/6=0.1(6)\)이며 \(1/7=0.(142857)\)이다. 순환되는 부분이 가장 긴 \(d\)를 찾는 것이 목표이다. 

2. 구현: ver 1.0

나눗셈을 수행하면서 순환되는 부분이 어디에서 발생하는지 확인한다.  

# -*- coding: utf-8 -*-


def count_reciprocal_cycles(d):
    """나눗셈을 수행하면서 나머지가 0이면 순환되는 부분이 없으므로 0을 반환한다.
       나머지가 이미 발생한 나머지라면 순환이 시작되는 부분이므로 이 부분을 찾는다."""
    quotient_list, remainder_list = [], []
    n = 1

    while True:
        quotient, remainder = divmod(n, d)
        quotient_list.append(quotient)

        if remainder == 0 or (remainder != 0 and remainder in remainder_list):
            break

        remainder_list.append(remainder)
        n = remainder * 10

    if remainder == 0:
        return 0
    else:
        return len(quotient_list) - remainder_list.index(remainder) - 1

longest_recurring_cycle = 0
for d in range(1, 1000):
    recurring_cycle = count_reciprocal_cycles(d)

    if longest_recurring_cycle < recurring_cycle:
        print('d: ', d)
        print('recurring cycle: ', recurring_cycle)
        longest_recurring_cycle = recurring_cycle

답은 983이다.