225 Tribonacci non-divisors

Problem 225 – Project Euler

直前3項の和で定まる数列について.

tribonacci を Z_n の世界で考えると,Z_n は有限なので,ループになっている.

そのループが0を含むかどうか,判定する.

実はもっと効率化できる,たとえば,27の倍数は0を含まない.

でも,124番目だし,そんなことしなくてもリーズナブルな時間で解が求まる.

それにしても,この問題は出題時に解きたかった.

divide :: (Integral t) => t -> Bool
divide n = dpart n 1 1 3
dpart :: (Integral t) => t -> t -> t -> t -> Bool
dpart n 1 1 1 = False
dpart n p q r | r' ==     = True
| otherwise = dpart n q r r'
where r' = mod (p + q + r) n
p225 :: (Integral a) => Int -> a
p225 n = (!! (n - 1)).filter (not.divide) $ [27,29..]
main :: IO ()
main = print.p225 $ 124