Euler Project: Problem 26

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 ¹/₇ has a 6-digit recurring cycle.

Find the value of d  1000 for which ¹/_d contains the longest recurring cycle in its decimal fraction part.

오랜 동안 고민했다. 마땅한 알고리듬이 떠오르지 않았다. 일반적인 방법론이 전혀...

한참을 고민 끝에 결국 구글신님께 계시를 받기로 하고 검색을 하였다.

순환소수에 대한 '정리'가 있음을 알게 되었다.

여기 자료가 매우 유용하였다. 여기(Japanese).

요점만 정리하면 다음과 같다.

#1. 기약분수(k/n)가 무한순환소수일때, 소숫점 첫째자리부터 길이 r의 순환구간이 반복되는 것과, 10^r == 1 (mod n)이 성립하는 것은 동치이다.

#2. 기약분수가 순수한 순환소수일때 분모는 반드시 10과 서로소 이다. 반대로 분모가 10과 서로소인 기약분수를 소수로 나타내면 반드시 순수한 순환소수가 된다. (순수한 순환소수란, 0.121212...같은 것. 0.3121212는 순수하지 않은 순환소수를 지칭.)

2와 5를 제거하는 이유는, reLen 알고리듬상 reLen이 무한루프에 빠져들기 때문임.

import Data.Numbers.Primes
import Data.List
import qualified Data.Set as Set
import Data.Ord 

main :: IO()
main = print $ fst $ maximumBy (comparing snd) $ zip [1..1000] $ map reciprocalLength [1..1000] 

reciprocalLength :: Integer -> Integer
reciprocalLength n = reLen $ remove2or5 n 

remove2or5 :: Integer -> Integer
remove2or5 n = product $ Set.toList $ Set.difference (Set.fromList $ primeFactors n) (Set.fromList [2,5])
--remove2or5 n = product $ delete 5 $ delete 2 $ nub $ primeFactors n 

reLen :: Integer -> Integer
reLen n
    | n == 0 || n == 1  = 0
    | otherwise         = head [ r | r <- [1..], 10^r `mod` n == 1] 

*Main> main
983