[Edu-sig] A math + python example (cc: math-learn)

[Kirby Urner]

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=20
between 0 and 1 inclusive, in ascending order, having denominators=20
up to and including N.[2]

For example, if N=3D3, then Farey(N) =3D

  >>> 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=20
for 0 and 1.  The default list (no 2nd argument) returns a list of=20
tuples:

  >>> farey(3)
  [(0, 1), (1, 3), (1, 2), (2, 3), (1, 1)]

and the 'd' option returns floating point numbers, which are a=20
little different from the decimals one would compute by hand, owing=20
to the decimal->binary->decimal conversions that go on in floating=20
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=20
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. =20

  >>> farey(7,'f')
  ['0/1', '1/7', '1/6', '1/5', '1/4', '2/7', '1/3', '2/5',=20
   '3/7', '1/2', '4/7', '3/5', '2/3', '5/7', '3/4', '4/5',=20
   '5/6', '6/7', '1/1']

This algorithm is guarenteed to reach all lowest terms fractions,=20
and keeps them in ascending order to boot.  The tree algorithm=20
will pick of fractions of denominator > N in the process of=20
getting all those with denominators <=3D N, so some filtering is
required in the final step. =20

The tree algorithm is defined as a separate function, to facilitate=20
explorations independent of the Farey series connection, e.g.=20
classroom discussion might focus on the fact that initial values=20
of 0/1 and 1/0 will plant a tree that grows towards encompassing=20
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): =20

     http://www.inetarena.com/~pdx4d/ocn/python/farey.py

Color-coded in HTML for readability (uses Win32 IDLE colors=20
-- pre-written conversion modules do this work [4]):

     http://www.inetarena.com/~pdx4d/ocn/python/farey.html

Kirby

=3D=3D=3D=3D=3D=3D=3D

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=F3mez Mor=EDn generalizes the notion of mediant
     in his definition of rational mean, which he uses to specify
     various root-finding algorithms etc.  Mor=EDn'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,=20
     Tim Peters and Just van Rossum (I modified the color key
     to match Win32 IDLE 0.8).