« Project Euler : Problem 25 | トップページ | Project Euler : Problem 27 ~ 関数をデータとして扱う »

2010年5月24日 (月)

Project Euler : Problem 26 ~ 循環節の長さ

 問題はこちらをご覧ください。

 

 基本的な考え方は、以前の記事のとおりです。

 さらに、「フェルマーの小定理」を検討すると、分母を d とした場合、

mod (10 ^ (d - 1)) d == 1
となるので、「順関節の長さ」は最大で "d - 1" となります。
 したがって以前の記事の考えを基にすると、「2」や「5」を因子に持つ d を分母とした場合、「循環節の長さ」は明らかに "d - 1" より短くなるので、調べる候補から外しても問題ないと思われます。
 また、「循環節の長さ」は最大で "d - 1" ということから、 d の候補を大きい方から調べていって、「循環節の長さ」が "d - 1" になるものが見つかったら、それが求める d となります。
-- 1/n の循環節の長さを数える。 count :: Int -> Int count n = 1 + length (takeWhile (/= 1) $ iterate calc $ calc 1) where calc x = rem (10 * x) n problem026 :: Int problem026 = head [x | x <- xs, gcd x 10 == 1, count x == x - 1] where xs = [999, 997 .. 2] main = print problem026
 関数 "count" に関して少し解説をすると、 "iterate calc $ calc 1" は「余りを 10 倍して n で割った余り」を無限リストの形で返します。
 余りが 1 になった時点から再び循環節の繰り返しが始まります。ですからそこで "count" は終了となるのですが、 "takeWhile" が終了条件に合致する項目を含まないことになっているので、正確な「循環節の長さ」を出すために 1 を加えた結果を答えとしています。

 参考までに、「 1/n の小数点以下の数字を無限リストで返す関数」を作って見ました。

underPoint :: Int -> [Int] underPoint n = [a | (a, _) <- iterate calc (calc (0, 1))] where calc (_, m) = quotRem (10 * m) n
*Main> take 20 $ underPoint 7 [1,4,2,8,5,7,1,4,2,8,5,7,1,4,2,8,5,7,1,4]

« Project Euler : Problem 25 | トップページ | Project Euler : Problem 27 ~ 関数をデータとして扱う »

Haskell」カテゴリの記事

Project Euler」カテゴリの記事

コメント

コメントを書く

コメントは記事投稿者が公開するまで表示されません。

(ウェブ上には掲載しません)

トラックバック

この記事のトラックバックURL:
http://app.cocolog-nifty.com/t/trackback/112020/48444900

この記事へのトラックバック一覧です: Project Euler : Problem 26 ~ 循環節の長さ:

« Project Euler : Problem 25 | トップページ | Project Euler : Problem 27 ~ 関数をデータとして扱う »

2016年7月
          1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
31            
フォト

最近のトラックバック

無料ブログはココログ