Create Farey Sequence with Python / Tcl Script

This is an interesting subject > Community: Ford circles not touching
Keywords: Farey sequence, Ford circle

I've shared workspace examples related to the subject (FME User Community members only).
FME 2012 SP4+ Edition
FME 2014 Edition

Here I give Python and Tcl script examples which create Farey sequence as a structured list attribute. Probably these are "more than enough is too much", but contain some useful tips which can be applicable generally.

Python

-----
# Python Script Example (PythonCaller)
# Create Farey sequence as a structured list attribute:
# _farey{}.p, _farey{}.q, _farey{}.v (v = p / q)
# Assume input feature has an integer attribute named "_farey_orders".
import fmeobjects
from operator import itemgetter

def createFareySequence(feature):
    s = [(0, 1, 0.0), (1, 1, 1.0)]
    for q in range(2, int(feature.getAttribute('_farey_orders')) + 1):
        for p in range(1, q):
            if not have_common_divisor(p, q):
                s.append((p, q, float(p)/q))
    for i, (p, q, v) in enumerate(sorted(s, key=itemgetter(2))):
        feature.setAttribute('_farey{%d}.p' % i, p)
        feature.setAttribute('_farey{%d}.q' % i, q)
        feature.setAttribute('_farey{%d}.v' % i, v)

# Helper function
# Return True if m and n have a common divisor other than 1.
# Otherwise return False.
def have_common_divisor(m, n):
    nmin, nmax = min(m, n), max(m, n)
    if nmin == 1:
        return False
    elif (m % 2 == 0 and n % 2 == 0) or nmax % nmin == 0:
        return True
    for d in range(3, nmin / 2 + 1, 2):
        if m % d == 0 and n % d == 0:
            return True
    return False
-----

Tcl

-----
# Tcl Script Example (TclCaller)
# Create Farey sequence as a structured list attribute:
# _farey{}.p, _farey{}.q, _farey{}.v (v = p / q)
# Assume input feature has an integer attribute named "_farey_orders".
proc createFareySequence {} {
    set s [list {0 1 0.0} {1 1 1.0}]
    for {set q 2} {$q <= [FME_GetAttribute "_farey_orders"]} {incr q} {
        for {set p 1} {$p < $q} {incr p} {
            if {![have_common_divisor $p $q]} {
                lappend s "$p $q [expr double($p) / $q]"
            }
        }
    }  
    set s [lsort -real -index 2 $s]
    for {set i 0} {$i < [llength $s]} {incr i} {
        FME_SetAttribute "_farey{$i}.p" [lindex $s $i 0]
        FME_SetAttribute "_farey{$i}.q" [lindex $s $i 1]
        FME_SetAttribute "_farey{$i}.v" [lindex $s $i 2]
    }
}

# Helper procedure
# Return 1 if m and n have a common divisor other than 1.
# Otherwise return 0.
proc have_common_divisor {m n} {
    set nmin [expr min($m, $n)]
    set nmax [expr max($m, $n)]
    if {$nmin == 1} {
        return 0
    } elseif {(![expr $n % 2] && ![expr $m % 2]) || ![expr $nmax % $nmin]} {
        return 1
    }
    for {set d 3} {$d <= [expr $nmin / 2]} {incr d 2} {
        if {![expr $n % $d] && ![expr $m % $d]} {
            return 1
        }
    }
    return 0
}
-----