2026-11-11
Residues.hs
main :: IO ()
main = print (length [x | x <- [0 .. 1000 :: Int], x `mod` 3 == x `mod` 5, x `mod` 5 == x `mod` 7])
これは何を出力するでしょうか?
Answer
Output
30
内包表記の条件は、x を 3 で割った余り、5 で割った余り、7 で割った余りがすべて等しいことです。その共通の余りを r とすると、r は 3 で割った余りでもあるので 0, 1, 2 のどれかに限られます。そして x = r 自身は、r < 3 なのでどれで割っても余りが r になり、条件を満たします。
あとは r ごとに、条件を満たす数がどれだけあるかです。105 = 3 × 5 × 7 はどの数でも割り切れるので、x と x + 105 は3つの余りが同じで、105 ごとに同じ並びがくり返します。逆に、0 以上 105 未満の範囲で3つの余りが同じ数は1つしかありません。2つあればその差は 3 でも 5 でも 7 でも割り切れ、3つの数は互いに素なので差は 105 の倍数になるからです。1 したがって条件を満たすのは 105k, 105k + 1, 105k + 2 の形の数だけです。
0 から 1000 までの範囲では、k = 0 から 9 までの 10 区間にそれぞれ3個ずつあり、最後は 945, 946, 947 です。k = 10 の 1050 はもう範囲の外なので、個数は 10 × 3 = 30 になります。最初の 0, 1, 2 だけを見つけて 3 と答えたり、1000 / 105 を約 9.5 として端数の区間を数え損ねたりしやすいところです。
- 3つの余りの組から 0 以上 105 未満の数がちょうど1つ決まるというこの性質は、中国剰余定理(ちゅうごくじょうよていり、Chinese remainder theorem)と呼ばれます。互いに素な数で割った余りの組を指定すると、それらの積より小さい 0 以上の整数がちょうど1つ決まる、という定理です。