I was looking for an interesting computational problem on Rosetta Code and I found out that a common lisp implementation of Farey Sequence was missing. So, I am going to implement one. I took my implementation from the scala version with some modifications. I also uploaded a version to Rosetta Code before I posted here.
Here is my implementation:
(defun farey (n)
(labels ((helper (begin end)
(let ((med (/ (+ (numerator begin) (numerator end))
(+ (denominator begin) (denominator end)))))
(if (<= (denominator med) n)
(append (helper begin med)
(list med)
(helper med end))))))
(append (list 0) (helper 0 1) (list 1))))FAREYLet us test:
(format nil "~{~{~2d: ~{~a ~}~}~^~%~}"
(loop for i from 1 to 11 collect (list i (farey i)))) 1: 0 1
2: 0 1/2 1
3: 0 1/3 1/2 2/3 1
4: 0 1/4 1/3 1/2 2/3 3/4 1
5: 0 1/5 1/4 1/3 2/5 1/2 3/5 2/3 3/4 4/5 1
6: 0 1/6 1/5 1/4 1/3 2/5 1/2 3/5 2/3 3/4 4/5 5/6 1
7: 0 1/7 1/6 1/5 1/4 2/7 1/3 2/5 3/7 1/2 4/7 3/5 2/3 5/7 3/4 4/5 5/6 6/7 1
8: 0 1/8 1/7 1/6 1/5 1/4 2/7 1/3 3/8 2/5 3/7 1/2 4/7 3/5 5/8 2/3 5/7 3/4 4/5 5/6 6/7 7/8 1
9: 0 1/9 1/8 1/7 1/6 1/5 2/9 1/4 2/7 1/3 3/8 2/5 3/7 4/9 1/2 5/9 4/7 3/5 5/8 2/3 5/7 3/4 7/9 4/5 5/6 6/7 7/8 8/9 1
10: 0 1/10 1/9 1/8 1/7 1/6 1/5 2/9 1/4 2/7 3/10 1/3 3/8 2/5 3/7 4/9 1/2 5/9 4/7 3/5 5/8 2/3 7/10 5/7 3/4 7/9 4/5 5/6 6/7 7/8 8/9 9/10 1
11: 0 1/11 1/10 1/9 1/8 1/7 1/6 2/11 1/5 2/9 1/4 3/11 2/7 3/10 1/3 4/11 3/8 2/5 3/7 4/9 5/11 1/2 6/11 5/9 4/7 3/5 5/8 7/11 2/3 7/10 5/7 8/11 3/4 7/9 4/5 9/11 5/6 6/7 7/8 8/9 9/10 10/11 1