책 이야기

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인 분수를 단위 분수(unit fraction)이라 한다. 분모가 2에서 10인 단위 분수는 다음과 같이 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를 찾으시오.

--------------------------------------------------------------------------

분수 값에서 순환소수 값을 구하는 방법을 알면 쉽게 풀 수 있고, 이것은 초등학교 산수 수준의 문제인 것 같기는 한데 어떻게 구하는 지 전혀 아이디어가 떠오르지 않아 보류하고 지나갔던 문제이다.

다시 봐도 아이디어가 떠오르지 않아 분수를 순환소수로 구하는 요령을 인터넷으로 검색하고 그것을 파이썬 코드로 만들어서 답을 구할 수 있었다. 9를 계속 만들어가면서 나눠지면 그 때 있는 9의 갯수가 순환마디의 크기를 뜻하는 것이 되는데, 예를 들어, 분모가 6일 때 90을 나눌 수 있고, 이 때 9는 1개 있으므로 순환마디는 1이고, 분모가 7일 때 999999을 나눌 수 있고, 이 때 9가 6개 있으므로 순환마디 6이 된다.

2~999까지의 반복문 안에, 9의 갯수(순환마디)를 찾는 2개의 반복문으로 구성해서 문제를 풀었고, 답을 구하는데 28초가 걸려 그리 성능이 좋은 방법으로 구현하지 않았다는 것을 알았지만 묵혀둔 미결 문제를 해결한 기쁨이 더 컸다.

The number, 197, is called a circular prime because all rotations of the digits: 197, 971, and 719, are themselves prime.

There are thirteen such primes below 100: 2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, and 97.

How many circular primes are there below one million?

숫자 197의 자릿수를 바꿔 만들어지는 197, 971, 719 모두가 소수이기 때문에 순환소수(circular prime)이라 불린다.

100 이하의 수에는 2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, 97의 13개 순환소수가 있다.

백만 이하의 수에는 몇 개의 순환소수가 있는가?

--------------------------------------------------------------------------

순환소수라 불렀지만 수학 용어는 아니고 임의로 붙인 명칭이다. 숫자를 한 방향으로 회전시키면서 나온 숫자가 소수인지 판별하면 된다.

단순하게 생각해보면 2부터 백만까지 반복해가면서 소수인지 판별하고, 자릿수를 바꿔 만들어지는 수가 모두 소수인지 판별하는 방법이 있다. 하지만, 소수인지 판별하는 것이 상대적으로 시간이 많이 소요되는 과정이기 때문에 성능이 나쁠 것 같아 다른 접근을 하기로 했다.

미리 2부터 백만까지의 소수를 리스트로 만들어 놓고, 리스트에 있는 소수를 대상으로 자릿수를 바꿔 만들어지는 수가 만들어 놓은 소수 리스트에 있는지 확인하는 방식으로 소수 여부를 판별하게 했다. 그리고, 조금 더 계산 속도를 빠르게 만드는 방법으로는 소수인 숫자 어딘가에 짝수나 5의 배수가 있으면 순환하는 중 1의 자리에 오게 되면 소수가 아니게 되기 때문에(2의 배수 or 5의 배수), 각 자릿수 중에 0,2,4,6,8과 5가 있으면 소수가 아닌 것으로 보고 다음 숫자로 넘어가게 할 수 있다.