How to resolve the algorithm Farey sequence step by step in the Common Lisp programming language

Published on 12 May 2024 09:40 PM
#Common lisp

How to resolve the algorithm Farey sequence step by step in the Common Lisp programming language

Table of Contents

Problem Statement

The   Farey sequence   Fn   of order   n   is the sequence of completely reduced fractions between   0   and   1   which, when in lowest terms, have denominators less than or equal to   n,   arranged in order of increasing size. The   Farey sequence   is sometimes incorrectly called a   Farey series.

Each Farey sequence:

The Farey sequences of orders   1   to   5   are:

The length   (the number of fractions)   of a Farey sequence asymptotically approaches:

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Farey sequence step by step in the Common Lisp programming language

Source code in the common programming language

(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))))


;; Force printing of integers in X/1 format
(defun print-ratio (stream object &optional colonp at-sign-p)
  (format stream "~d/~d" (numerator object) (denominator object)))
 
(loop for i from 1 to 11 do
     (format t "~a: ~{~/print-ratio/ ~}~%" i (farey i)))

(loop for i from 100 to 1001 by 100 do
     (format t "Farey sequence of order ~a has ~a terms.~%" i (length (farey i))))

You may also check:How to resolve the algorithm Abelian sandpile model step by step in the Nim programming language
You may also check:How to resolve the algorithm Barnsley fern step by step in the Go programming language
You may also check:How to resolve the algorithm Command-line arguments step by step in the Visual Basic programming language
You may also check:How to resolve the algorithm Ackermann function step by step in the DWScript programming language
You may also check:How to resolve the algorithm String prepend step by step in the LFE programming language