# A Sequence for Counting the Rationals

David R. Tribble
david@tribble.com

Revision 1.2, 2007-12-15

## Introduction

Georg Cantor [1] proved that the rational numbers are countable. In layman's terms, this means that there are just as many fractions as there are counting numbers. While this strikes most people as rather counter-intuitive upon first hearing it, it is nonetheless grounded in solid logic.

Cantor used a diagonal counting method for counting all of the fractions, as illustrated in the following diagram. His scheme was slighltly less than perfect, though, because while it does indeed denumerate every possible rational number, it counts many of them more than once. This does not affect his proof, of course, because it simply shows that there are more than enough counting numbers (natural numbers) to number the rationals. It would be useful to construct a counting function or sequence that counts all of the rationals exactly once.

## The Sequence

... define the following sequence:

Sequence function.

S(0) = 0
S(1) = 1
S(2n) = S(n) + 1 for all n > 0
S(2n+1) = 1/S(2n) for all n > 0

Function S maps all of the natural numbers to all of the positive rational numbers. So for every natural number (i.e., every counting number) n = 0, 1, 2, etc., S(n) produces a unique rational number p/q in reduced form. (Reduced form means that p and q are integers with no common divisors, such as 2/3 and 8/5, but not 4/6 or 24/15.)

The first few values of sequence S are:

n S(n) Derivation
0 0 by the definition, S(20)
1 1 by the definition, S(21)
2 2 S(2•1) = S(1)+1, S(21)
3 1/2 S(2+1) = 1/S(2)
4 3 S(2•2) = S(2)+1, S(22)
5 1/3 S(4+1) = 1/S(4)
6 3/2 S(2•3) = S(3)+1
7 2/3 S(6+1) = 1/S(6)
8 4 S(2•4) = S(4)+1, S(23)
9 1/4 S(8+1) = 1/S(8)
10 4/3 S(2•5) = S(5)+1
11 3/4 S(10+1) = 1/S(10)
12 5/2 S(2•6) = S(6)+1
13 2/5 S(12+1) = 1/S(12)
14 5/3 S(2•7) = S(7)+1
15 3/5 S(14+1) = 1/S(14)
16 5 S(2•8) = S(8)+1, S(24)
etc. ... ...

The first 150 values of sequence S:

Table 1 — First 150 values of S(n)

n S(n)
n  S(n)
n  S(n)
n  S(n)
n   S(n)
 0 0 1 1 2 2 3 1/2 4 3 5 1/3 6 3/2 7 2/3 8 4 9 1/4 10 4/3 11 3/4 12 5/2 13 2/5 14 5/3 15 3/5 16 5 17 1/5 18 5/4 19 4/5 20 7/3 21 3/7 22 7/4 23 4/7 24 7/2 25 2/7 26 7/5 27 5/7 28 8/3 29 3/8
 30 8/5 31 5/8 32 6 33 1/6 34 6/5 35 5/6 36 9/4 37 4/9 38 9/5 39 5/9 40 10/3 41 3/10 42 10/7 43 7/10 44 11/4 45 4/11 46 11/7 47 7/11 48 9/2 49 2/9 50 9/7 51 7/9 52 12/5 53 5/12 54 12/7 55 7/12 56 11/3 57 3/11 58 11/8 59 8/11
 60 13/5 61 5/13 62 13/8 63 8/13 64 7 65 1/7 66 7/6 67 6/7 68 11/5 69 5/11 70 11/6 71 6/11 72 13/4 73 4/13 74 13/9 75 9/13 76 14/5 77 5/14 78 14/9 79 9/14 80 13/3 81 3/13 82 13/10 83 10/13 84 17/7 85 7/17 86 17/10 87 10/17 88 15/4 89 4/15
 90 15/11 91 11/15 92 18/7 93 7/18 94 18/11 95 11/18 96 11/2 97 2/11 98 11/9 99 9/11 100 16/7 101 7/16 102 16/9 103 9/16 104 17/5 105 5/17 106 17/12 107 12/17 108 19/7 109 7/19 110 19/12 111 12/19 112 14/3 113 3/14 114 14/11 115 11/14 116 19/8 117 8/19 118 19/11 119 11/19
 120 18/5 121 5/18 122 18/13 123 13/18 124 21/8 125 8/21 126 21/13 127 13/21 128 8 129 1/8 130 8/7 131 7/8 132 13/6 133 6/13 134 13/7 135 7/13 136 16/5 137 5/16 138 16/11 139 11/16 140 17/6 141 6/17 142 17/11 143 11/17 144 17/4 145 4/17 146 17/13 147 13/17 148 22/9 149 9/22

Deriving the rational number for large naturals can take several steps, since the sequence function is a recurrence relation:

S(1000)
= S(2•500) + 1
= (S(2•250) + 1) + 1
= ((S(2•125) + 1) + 1) + 1
= (((S(2•62+1) + 1) + 1) + 1)
+INCOMPLETE

## Inverse Function

Out next goal is to derive the inverse function of S. That is, we'd like to define inverse function S −1, so that for a given S(n) = p/q, we can plug in p/q to get the original argument, n = S −1(p/q).

We already know that S(0) = 0 andS(1) = 1, so the inverse mappings of these are simply S −1(0) = 0 and S −1(1) = 1.

Closer examination of the sequence (Table 1 above) reveals some observations about the values of the sequence and its arguments:

a. S(2k) = k + 1
b. For even n > 1, S(n) = S(n/2) + 1
c. For odd  n > 1, S(n) = 1/S(n−1)
d. For all even n > 0, S(n) = p/q where p > q
e. For all odd n, S(n) = p/q where p < q

The observations shown above allow us to derive the inverse sequence S −1, i.e., the function for mapping a rational number p/q to its corresponding natural number n.

In particular, note that S(2k) = k+1, in other words, that every power of 2 maps to an integer. This makes sense, because the sequence essentially produces a branching binary tree as we proceed along increasing arguments. It maps a certain number of fractions between each pair of integers k and k+1, and then twice as many fractions between the next pair of integers k+1 and k+2. As Table 1 above shows, there are two numbers mapped between S(2) = 2 and S(4) = 3 (if we include the first integer S(2) = 2), there are four numbers mapped between S(4) = 3 and S(8) = 4, there are eight numbers mapped between S(8) = 4 and S(16) = 5, and so on, doubling the number of fractions between each successive pair of integers mapped.

Thus observation (a) provides the next step in deriving the inverse function. Since S(2k) = k+1, therefore S −1(p) = 2p−1 for all positive integers p.

INCOMPLETE
Next we note that observation (b) tells us that the value of S(2n) where argument 2n is even can be derived from the previous value of S(n), effectively working our way backwards through the recurrence function. In addition, observation (d) tells us that given an even argument 2n, that S(2n) = p/q with p >q. So combining (b) and (d), we get that for fractions p/q when p >q, that S −1(p/q) = S(XXX)+1, +REDO
Observation (d) tells us that S(n) where argument n is even produces a fraction p/q with p > q.

Putting all of this together, we get the following definition for the inverse mapping function:

Inverse function.

S −1(0) = 0
S −1(1) = 1
S −1( p ) = 2p−1 for p > 0
S −1( p/q ) = 2 S −1( p/q − 1) for p > q
S −1( p/q ) = S −1( q/p ) + 1 for p < q

It is the fact that function S and its inverse S −1 map each natural n to exactly one rational p/q and vice versa that allows us to denumerate all of the rationals efficiently with no duplications or redundancies.

+INCOMPLETE

## Acknowledgments

I wish to express my gratitude to the following people who provided helpful criticisms of earliers drafts of this document:

• Virgil LastName?

## References

[1] Georg Cantor
Wikipedia: http://en.wikipedia.org/wiki/Georg_Cantor

[2] Cantor's Theorem (Diagonal Method)
Wikipedia: http://en.wikipedia.org/wiki/Cantor%27s_theorem
http://en.wikipedia.org/wiki/Cantor%27s_diagonal_argument
MathWorld: http://mathworld.wolfram.com/CantorDiagonalMethod.html

[3] Farey Sequence
Wikipedia: http://en.wikipedia.org/wiki/Farey_sequence
MathWorld: http://mathworld.wolfram.com/FareySequence.html
Cut the Knot: http://www.cut-the-knot.org/blue/Stern.shtml

[4] Stern-Brocot Tree
Wikipedia: http://en.wikipedia.org/wiki/Stern-Brocot_tree
MathWorld: http://mathworld.wolfram.com/Stern-BrocotTree.html
Cut the Knot: http://www.cut-the-knot.org/blue/Stern.shtml

This document: http://david.tribble.com/text/sequence1.html.

Copyright ©2007 by David R. Tribble, all rights reserved.
Permission is granted to reference, quote, and link to this document provided that appropriate credit is given to the orginal author.