Problem 225

225 Tribonacci non-divisors

直前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

コンテンツ