Namaran

Code daily. Without assist.

2026-10-14

Meet.hs

next :: Int -> Int
next x = (x * x + 1) `mod` 10

main :: IO ()
main = print (take 1 [(i, t) | (i, t, h) <- zip3 [1 :: Int ..] tortoise hare, t == h])
  where
    tortoise = drop 1 (iterate next 3)
    hare = drop 1 (iterate (next . next) 3)

これは何を出力するでしょうか?

Answer

[(6,7)] です。

iterate next 3 は、3に next を0回、1回、2回と当てていった値の無限リスト 3, 0, 1, 2, 5, 6, 7, 0, 1, … です。7の次は 7 × 7 + 1 = 50 の一の位で0に戻るので、先頭の3を除くと 0, 1, 2, 5, 6, 7 の6つをくり返します。tortoise はこのリストの i 番目(i = 1, 2, …)を並べたもので、hare は next . next を当てていくので 2i 番目を並べたものです。

組を順に比べると、i が1から5までは (0, 1)、(1, 5)、(2, 7)、(5, 1)、(6, 5) と食い違い、i = 6 で両方が7になります。2つの位置の差はちょうど i なので、両方がくり返しの中に入っていれば、i がくり返しの長さ、つまり周期(period)の6の倍数になったところで同じ値を指します。take 1 は最初の一致だけを取り出し、無限リストの残りは評価されません。

1歩ずつ進む側と2歩ずつ進む側を同じ値に出会うまで動かすこのやり方は、フロイドの循環検出法(Floyd's cycle-finding algorithm)と呼ばれ、ウサギとカメのアルゴリズムともいいます。これまでに出た値を覚えておかなくても、列がくり返しに入っていることを確かめられます。