Problem 73 - 1/2と1/3の間

微妙。疲れてきたかも。

1/2と1/3の間にある真既約分数を求める。

真既約分数を求めるのがちとめんどかったので、全部見てしまった。

だいたい範囲を絞っておいて、
gcdしてみる。
だいたいなので、キッチリ範囲チェック。

(define (problem73 n)
  (length (append-map
            (lambda (d)
              (filter (lambda (n)
                        (and
                          (= (gcd n d) 1)
                          (> (/ n d) 1/3)
                          (< (/ n d) 1/2)))
                      (iota (+ (- (quotient d 2) (quotient d 3)) 1)
                            (quotient d 3))))
            (iota (- n 3) 4))))

(time (problem73 10000))
; cpu time: 7443 real time: 7444 gc time: 681
; 5066251

1/2のチェックは要らないみたいだけど、一応付けておいた。

途中まで考察

オイラーの関数で、φ(n)で、0/n〜n/nまでの個数が出る。

2以外のφ(n)は偶数なので、半分にすれば、0〜1/2までの個数も出る。

0〜1/3までの個数を引けば出るんだけど・・・・