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 を越えない範囲で考えてやればいいと思っている.

追記

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