Scheme:数遊び:既約分数

既約分数

結城浩さんの既約分数パズル。

問題：正の整数Nが与えられているとき、以下の条件を満たす既約分数p/qを「すべて」求めるアルゴリズムを示してください。条件は：

• p, qは整数(pは0以上で、qは1以上N以下).
• gcd(p, q) = 1 (pとqの最大公約数は1).
• 0 <= p/q <= 1.

Haskellによるエレガントな解法(本質的に、エラトステネスの篩と同質の方法だと 思う)はnobsunが示している。

• Programming:玉手箱:整数論:既約分数
• Cahier:2004-01-02:既約分数
• Cahier:2004-01-03:互いに素(ちょっと修正)
• comment:Cahier:2004-01-03

gcdを使うのは素直すぎるので、ここではFarey seriesというのを 使った解法を。これも割算が登場しない。

(define (farey n)
  (define (rec series n)
    (cond ((null? (cdr series)) series)
          ((= (+ (cdar series) (cdadr series)) n)
           (list* (car series)
                  (cons (+ (caar series) (caadr series))
                        (+ (cdar series) (cdadr series)))
                  (rec (cdr series) n)))
          (else (cons (car series) (rec (cdr series) n)))))
  (if (= n 1)
    '((0 . 1) (1 . 1))
    (rec (farey (- n 1)) n)))

gosh> (farey 6)
((0 . 1) (1 . 6) (1 . 5) (1 . 4) (1 . 3) (2 . 5) (1 . 2) (3 . 5) (2 . 3) (3 . 4) (4 . 5) (5 . 6) (1 . 1))

参考文献: John Conway and Richard Guy, The Book of Numbers, Springer-Verlag, 1996. 数の不思議な性質が易しく語られてて面白い本です。

• shelarcy: 余計かもしれませんが、邦訳 数の本, 根上生也訳, シュプリンガー・フェアラーク東京2001.

  (define (farey n)
    (define (rec series n)
      (if (null? (cdr series)) series
          (cons (car series)
                (let ((x (map + (car series) (cadr series)))
                      (y (rec (cdr series) n)))
                  (if (= (cadr x) n) (cons x y) y)))))
    (if (= n 1) '((0 1) (1 1))
        (rec (farey (- n 1)) n)))
  

(define (f n)
  (let loop ((x 1) (y 1) (r '((0 1))))
    (cond ((> x n) r)
          ((= y 0) (loop (+ x 1) x r))
          ((member (if (> (* y 2) x) (list (- x y) y) (list y (- x y))) r)
           (loop x (- y 1) (cons (list y x) r)))
          (else (loop x (- y 1) r)))))

Tag: Puzzle