中国の剰余定理

逆ポーランド記法の電卓があるらしいと知り、hpの10,000円くらいの高機能電卓、それもなぜかグラフ表示までできるようなやつをみてびっくり、amazonのレビューも筋金入りの数学オジサマがたの巣窟となっている感があり、いやはや世の中にはいろんな世界があるものだと逃げ帰ってきた次第です。
で、hp 50g ハイエンド グラフ電卓という電卓のレビューで、

しかしながら2300を超えるといわれる関数には、整数a, b, cを与えてau + bv = cを満たす整数u, vを計算するIACUVという関数や、中国の剰余定理の解を求めるICHINREMやCHINREMなど数学の専門家でもなければなかなかお目にかかることのないものまで含まれています。

この電卓にはいっぱい関数が入ってるらしい。
そ、そうですか。
言われてみれば普通の√とかもあれ、関数か。どころか、加減乗除ぜんぶ関数だ。それのもっといろんなことができるのが関数電卓だということなんだな。
あたしがこの電卓を買っても全然アレなので買うつもりはないけど、
中国の余剰定理
という一文に目が止まりました。なにこれ。なんだかマイナーな関数の搭載がされているという話ですが、そういう定理があるのね。
んでWikipediaの「中国の剰余定理」を見てみる事にしました。

『孫子算経』には、「3で割ると2余り、5で割ると3余り、7で割ると2余る数は何か」という問題とその解法が書かれている。中国の剰余定理は、この問題を他の整数についても適用できるように一般化したものである。

あら、シンプルな話。これならあたしにも何とかできそう。
#孫子算経というのは中国の古い書物で、数学や暗号について書かれたものだそうです。

解いてみる

三種類の数で割った剰余がそれぞれtrueだったらナンチャラ、というのを書けばいいんだろう。
[1..]とかで順番に洗っていけばいいんだわな。
[1..]だと終わりがないからいかんな。さしあたり[1..100]とかにしとこう。見つからなかったら1000とか10000とか数字を上げていけばよろしい。
#ちなみに、うっかり見ちゃったので、上の条件を満たすのは最小で23だということまでは把握しています。ちぇ。

こんなかんじ？

Prelude> let foo x = (x `mod` 3 == 2, x `mod` 5 == 3,x `mod` 7 ==2 )

さっそくためします。

Prelude> foo 23
(True,True,True)
Prelude> foo 22
(False,False,False)
Prelude> foo 8
(True,True,False)

うん。んー、うん。

Prelude> :t foo
foo :: Integral a => a -> (Bool, Bool, Bool)

タプルで返ってくるのは不便だ。ぜんぶ満たしてたらTrueでいいんだけど。

Prelude> let foo x = (x `mod` 3 == 2 && x `mod` 5 == 3 && x `mod` 7 ==2 )
Prelude> :t foo
foo :: Integral a => a -> Bool

どうかな。

Prelude> foo 23
True
Prelude> foo 22
False
Prelude> foo 8
False

書き方あってたみたい。で、リストの中から条件に合うものを拾うのはfilterだということなので、

Prelude> :t filter
filter :: (a -> Bool) -> [a] -> [a]

Boolが返る関数とリストを渡すのね。

Prelude> filter foo [1..100]
[23]

お。

Prelude> filter foo [1..1000]
[23,128,233,338,443,548,653,758,863,968]

おお。
実に大したことはないんですが、嬉しい。
少なくともいまのうちは、htmlだcgiだバッチだと吠えるよりは、こういう算数あそびに使ってるほうがいいのかも。

そーいえば

takeで先頭n個の取得ができるんだった。

Prelude> take 1 filter foo [1..1000]

:1:1:
    The function `take' is applied to four arguments,
    but its type `Int -> [a0] -> [a0]' has only two
    In the expression: take 1 filter foo [1 .. 1000]
    In an equation for `it': it = take 1 filter foo [1 .. 1000]

あちゃー。
そうか、このままだと take 1 で拾おうとするリストが”filter”になっちゃうんだ。
$つけよう。

Prelude> take 1 $ filter foo [1..1000]
[23]
Prelude> take 1 $ filter foo [1..]
[23]

これなら[1..1000]じゃなくて、[1..]でいいんだな。Lazyはよい。
少し賢くなった気分。