規約分数クイズ

元ネタは上記リンクから。
Common Lispで実装してみます。

(defun irreduciblefracs (n)
  (labels ((iter (p q lst)
      (if (= p q n)
   (mapcar #'(lambda (x)
        (apply #'/ x))
    (reverse lst))
   (iter (if (= p q)
      0
      (1+ p))
         (if (= p q)
      (1+ q)
      q)
         (if (= (gcd p q) 1)
      (cons `(,p ,q) lst)
      lst)))))
    (iter 0 1 nil)))

これはScheme臭くて嫌だ、って場合は次のようにしても良いかも。

(defun irreduciblefracs (n)
  (do ((p 0 (if (= p q)
  0
  (1+ p)))
       (q 1 (if (= p q)
  (1+ q)
  q))
       (lst nil (if (= (gcd p q) 1)
      (cons `(,p ,q) lst)
      lst)))
      ((= p q n)
       (mapcar #'(lambda (x)
     (apply #'/ x))
        (reverse lst)))))

いずれにしても、動作は次のようになります。

CL-USER> (irreduciblefracs 4)
(0 1 1/2 1/3 2/3 1/4 3/4)
CL-USER>