UMASS Lowell CyberEd
92.419 Computer Algebra with Mathematica
Kenneth M. Levasseur
Department of Mathematical Sciences    
University of Massachusetts Lowell
Lowell, MA 01852

Mathematica Project Home Page

Really Counting the Rational Numbers

Subject

Mathematics

Topic

It is well known among mathematics students that the set of positive rational numbers is countable.  This means that in principle one can make an exhaustive list of the set.  It isn't too hard to describe how you can proceed.  Create an infinite table as below and then proceed down the diagonals starting with the one number in the top right.

As you pass through all of these numbers, you ignore the ones that are not reduced to lowest terms such as .  Theoretically this is fine, but if we ask were, for example, will appear on our list it is unclear.  Or what will be the number on the list.  

A Note in the April 2000 issue of the American Mathematical Monthly describes an ordering of the positive rational numbers where these questions can more easily answered.  The ordering is based on an infinite tree that starts as follows.

Can you see the patterns in this tree?   A complete listing of the positive rational numbers is accomplished by writing the successive levels of this tree, moving from left to right along the levels:

        

The numbers that appear in the tree are the ratios of successive terms in a sequence , where is the number of ways that you can write n as the sum of powers of two using any power of two no more than twice.  For example,   because .  This called Stern's diatomic sequence.

Reference(s)

  1. Neil Calkin and Herbert Wilf, "Recounting the Rationals,"  American Mathematical Monthly, 107(2000) 360-363.
  2. Ronald L. Graham, Donald E. Knuth and Boren Patashnik, Concrete Mathematics, Addison Wesley, Reading, 1989.
  3.  N. J. A. Sloane, The On-Line Encylopedia of Integer Sequence, http://www.research.att.com/~njas/sequences/

Project Idea(s)

1.   Develop as many functions as you can to
    a.  Compute the values of
    b.  Compute the entries in the tree above.
    c.  Determine the position of any rational number in the tree and in the corresponding list of rationals
2.   Using the functions above, explore patterns in the tree above and within similar trees, called Stern-Brocot trees (see [2])

3.  An advanced project:  Consider the question posed at the end of [1]: Besides the sequence , is there any other sequence of numbers whose successive ratios lists all rationals?

Prerequisite Mathematics

Recursion, infinite cardinality, elementary number theory.

Required Programming Level

Elementary - Moderate

Key Words

Rational numbers, fractions, countable, trees

Reviewer

K. M. Levasseur (Kenneth_Levasseur@uml.edu)

Archive

None

Questions?

If you have a question about this project or you would like to propose to try it (or a variation) click here