Problem 198 - Project Euler

まだ，解けていませんが，考えをまとめるために，メモ．

(つまり，間違ったことを書いている可能性アリ)

How many ambiguous numbers x = p/q, 0 x 1/100, are there whose denominator q does not exceed 10^8?

まず目につくのは，探索範囲の広さ．

0 < x < 1/100 で， 分母が 10^8 を越えない有理数xはざっと見積って10^12から10^16くらい(かなりテキトウ)．

なので，全探索は問題外．

一方，解のおおまかな個数を考える．

x = 1/2n は近似有理数として，0/1 と 1/n を持つ．

従って，解の個数はおおまかに見積って 10^8 くらい．

つまり，解を列挙するタイプのアルゴリズムは，無駄なく列挙したとしても，少くとも 10^8 くらいの計算が必要．

これはあまり，良いアルゴリズムではない．

そこで，曖昧数 x は二つの有理数 p/q, r/s の中点であること利用する．

(p/q, r/s の分母の小さいほうを探索するとすれば，探索範囲を 10^6 くらいにできるのでは，と楽観的に考える．)

x で考えるのではなく， p/q, r/s のほうで考えることにする．

p/q < r/s として，p/q を固定して，r/s を探すことにする(r/s は複数存在する)．

まず，条件として，p/q, r/s はあるFarey数列でとなりあっているので，

qr - ps = 1.

これより，r = (ps + 1)/q. r は整数であるから， s = -p^(-1) (mod q) を満たす．

p^(-1) (mod q) は拡張ユークリッドの互除法で求められる．

よって，r/s は求められる．(必要十分か？)

つぎに，x を考える． x = (p/q + r/s)/2 だから，

x = (ps + qr)/(2qs) = (2ps + 1) / (2qs).

気になるのは x が既約かどうか，つまり， gcd ( 2ps+1, 2qs) = 1 かということ．

まず，2ps+1 が 2 とも， s とも，互いに素であることは明らか．

よって，考えるべきは，2ps+1 と q が互いに素か．

2ps +1 = -2pp ^(-1) + 1 (mod q) = -1 (mod q) = kq -1 = (k-1)q + (q-1).

q-1 と q は互いに素だから，2ps+1 と q は互いに素．

なので，2qs が 10^8 を越えない範囲で考えてやればいいと思っている．

追記

実装したけど，どうやら間違っているらしい．う~ん．