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

Published on 12 May 2024 09:40 PM

How to resolve the algorithm Farey sequence step by step in the Tcl 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 Tcl programming language

Source code in the tcl programming language

package require Tcl 8.6

proc farey {n} {
    set nums [lrepeat [expr {$n+1}] 1]
    set result {{0 1}}
    for {set found 1} {$found} {} {
	set nj [lindex $nums [set j 1]]
	for {set found 0;set i 1} {$i <= $n} {incr i} {
	    if {[lindex $nums $i]*$j < $nj*$i} {
		set nj [lindex $nums [set j $i]]
		set found 1
	    }
	}
	lappend result [list $nj $j]
	for {set i $j} {$i <= $n} {incr i $j} {
	    lset nums $i [expr {[lindex $nums $i] + 1}]
	}
    }
    return $result
}

for {set i 1} {$i <= 11} {incr i} {
    puts F($i):\x20[lmap n [farey $i] {join $n /}]
}
for {set i 100} {$i <= 1000} {incr i 100} {
    puts |F($i)|\x20=\x20[llength [farey $i]]
}


  

You may also check:How to resolve the algorithm Sum and product of an array step by step in the Modula-3 programming language
You may also check:How to resolve the algorithm Sort three variables step by step in the Java programming language
You may also check:How to resolve the algorithm Ackermann function step by step in the RISC-V Assembly programming language
You may also check:How to resolve the algorithm Find common directory path step by step in the PureBasic programming language
You may also check:How to resolve the algorithm URL decoding step by step in the Arturo programming language