Problem 225

Project Euler Haskell

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' == 0    = 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