Problem 71 - 3/7よりちょっと小さい分数

もうちょいいこう。

100万以下の真既約分数を小さい順に並べて、3/7の左側に来る分数の分子を答える。

素直に並べたら、100万の2乗回はかかるのでムリっぽい。

んじゃ、と思って3/7以下に絞ってみたけど、1000分割位で破綻。100万 * 40万回なので当然ムリ。

ということで、例えば、3/7で検索するなら、

1/3が最初に見つかる。次は2/5が引っかかる。次はよくわからんけど、3以上/dとなるので、最後に見つかった分子より大きい数が来るはず。

分子ベースで見ていけば100万*ちょっと回位でいけそう。

(define (problem71 splits rat)
  (letrec ((iter
             (lambda (n d nm dm)
               (cond ((= d splits) (list nm dm))
                     ((>= (/ n d) rat) (iter nm (+ d 1) nm dm))
                     ((> (/ n d) (/ nm dm)) (iter (+ n 1) d n d))
                     (else
                       (iter (+ n 1) d nm dm))))))
    (iter 1 1 1 splits)))

(problem71 8 3/7) ; (2 5)
(problem71 10 3/7) ; (2 5)
(problem71 100 3/7) ; (41 96)
(problem71 1000 3/7) ; (428 999)
(problem71 10000 3/7) ; (4283 9994)
(problem71 100000 3/7) ; (42854 99993)
(problem71 1000000 3/7) ; (428570 999997)

よかった。終わったよ。

お、100万から下っていけばすぐ見つかりそうだ。と思ったけど、結構面倒だな・・・。