Thanks to Dave Marain posting to math-learn@yahoogroups.com [1], the subject of Farey series arose, an ideal topic for those engaged in a "math + programming" curriculum using Python or other language (e.g. Scheme). Farey(N) is the complete list of reduced (lowest-terms) fractions between 0 and 1 inclusive, in ascending order, having denominators up to and including N.[2] For example, if N=3, then Farey(N) =
farey(3,'f') ['0/1', '1/3', '1/2', '2/3', '1/1']
The 'f' argument returns the list in 'fraction format p/q' -- including for 0 and 1. The default list (no 2nd argument) returns a list of tuples:
farey(3) [(0, 1), (1, 3), (1, 2), (2, 3), (1, 1)]
and the 'd' option returns floating point numbers, which are a little different from the decimals one would compute by hand, owing to the decimal->binary->decimal conversions that go on in floating point world:
farey(3,'d') [0.0, 0.33333333333333331, 0.5, 0.66666666666666663, 1.0]
One way to generate a Farey series is given in 'Concrete Mathematics' (Graham, Knuth, Patashnik): generate a Stern- Brocot subtree to the depth necessary in order to get all fractions of denominator N. The Stern-Brocot tree is formed by interpolating what are called mediants between every pair of terms in an expanding list. The mediant of p1/q1 and p2/q2 is simply (p1+p2)/(q1+q2).[3] So, starting with [(0,1),(1,1)], and interpolating a single mediant, you get: [(0,1),(1,2),(1,1)]. The next iteration gives you [(0,1),(1,3),(1,2),(2,3),(1,1)], and so on.
farey(7,'f') ['0/1', '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/1']
This algorithm is guarenteed to reach all lowest terms fractions, and keeps them in ascending order to boot. The tree algorithm will pick of fractions of denominator > N in the process of getting all those with denominators <= N, so some filtering is required in the final step. The tree algorithm is defined as a separate function, to facilitate explorations independent of the Farey series connection, e.g. classroom discussion might focus on the fact that initial values of 0/1 and 1/0 will plant a tree that grows towards encompassing all positive lowest terms fractions, none missing, no duplicates. Here's some code, although students might not want or need it: Python source (public domain): http://www.inetarena.com/~pdx4d/ocn/python/farey.py Color-coded in HTML for readability (uses Win32 IDLE colors -- pre-written conversion modules do this work [4]): http://www.inetarena.com/~pdx4d/ocn/python/farey.html Kirby ======= Notes: [1] http://groups.yahoo.com/group/math-learn/message/521 [2] The Farey series links to what are called Ford circles, as discussed in 'The Book of Numbers' by Conway and Guy. My thanks to Pat Ballew for pointing this out: http://groups.yahoo.com/group/math-learn/message/523 [3] Domingo Gómez Morín generalizes the notion of mediant in his definition of rational mean, which he uses to specify various root-finding algorithms etc. Morín's site suggests some more fun programming challenges. See: http://www.etheron.net/usuarios/dgomez/RmDef.htm [4] (c) 1996-2000 by Mitchell S. Chapman, Zachary Roadhouse, Tim Peters and Just van Rossum (I modified the color key to match Win32 IDLE 0.8).