# Recounting the rationals

> An annotated edition of this paper on Fermat's Library, where scientists and readers explain its ideas, equations and history in the margins. Annotated edition: https://fermatslibrary.com/s/recounting-the-rationals

- **Authors:** Neil Calkin and Herbert S. Wilf
- **Published:** 2008
- **Topic:** Mathematics
- **Original:** https://s3-us-west-1.amazonaws.com/fermatslibrary/uploads%2F1531708143695-g3ztjao6srj-105d5d5362639a98e8391b3bf55c05fc%2Fcalkin_wilf_recounting_rationals.pdf
- **Pages:** 4
- **Annotations:** 13 comments in 6 threads
- **Featured:** Fermat's Library Journal Club
- **Annotated edition:** https://fermatslibrary.com/s/recounting-the-rationals

## Annotations

### Annotation 1 (page 1)

Beside the passage: “1 1 , 1 2 , 2 1 , 1 3 , 3 2 , 2 3 , 3 1 , 1 4 , 4 3 , 3 5 , 5 2 , 2 5 , 5 3 , 3 4 , 4 1 , 1 5 , 5 4 , 4 7 , 7 3 , 3 8 , 8 5 , 5 7 , 7 2 , 2 7 , 7 5 , . . .”

**Annotation** by Luís Batalha (2018-07-16):

> ### Motivation
>
> In this paper the authors present a new way to list all the rational numbers in a more elegant fashion. A rational number can be written in the form $\frac{a}{b}$ where $a$ and $b$ are integers. Rational numbers are countable, which means there is a one-to-one correspondence between the set of rational numbers and $\mathbb{N}$ = {0, 1, 2, 3, ...} - in other words, you can put the elements of the set in order just like natural numbers are in order. Here's an example of how you can create a countable correspondence for the rationals
>
>  ![](https://i.imgur.com/2wX6wa3.png)
>
> The problem with this correspondence is that you have numbers that appear multiple times $1/1,2/2,...$, making it seem a bit inelegant. The solution presented in this paper tries to fix some of these issues.

**Reply** by Steve Powell (2018-07-25):

> Actually, as noted by the authors, the elegant enumeration of the rationals was already known (see Stern-Brocot trees), but this paper makes it even more elegant, and makes explicit a relationship to the _hyperbinary_ partition function, first defined by Reznick.
>
> _Concrete Mathematics_, by Graham, Knuth and Patashnik (see references), contains the most accessible introduction I know to these trees — and to many other discrete mathematics topics.

### Annotation 2 (page 1)

Beside the passage: “1”

**Annotation** by Mathias Gebhart (2018-07-17):

> What does relatively prime mean?

**Reply** by Steven Canning (2018-07-17):

> It means that the numbers share no common factors other than $1$. For instance, $6 = 2\cdot 3$ and $35 = 5 \cdot 7$ are relatively prime.

**Reply** by Jont Allen (2018-07-18):

> this is also called "coprime"

### Annotation 3 (page 2)

Beside the passage: “         1 2 u e”

**Annotation** by Luís Batalha (2018-07-16):

> The list in the beginning of the paper is just the deforestation of the so-called Calkin-Wilf tree, starting from top to bottom and from left to right.

### Annotation 4 (page 2)

Beside the passage: “2”

**Annotation** by Luís Batalha (2018-07-16):

> There's another way to prove this. Two numbers are relatively prime if the greatest common divisor (gcd) between the two is 1 ($gcd(i,j)=1$). We can prove this by induction.
>
> 1) $gcd(1,1) = 1$, at the root vertex this is true
>
> 2) Assuming it's true for a certain vertex i,j ($gcd(i,j) = 1$) we just need to prove that it's true for the child nodes - $gcd(i,i+j) = gcd(i+j,j) = 1$
>
> Now, it's not difficult to see that if $gcd(i,j) = k$, that means $k$ divides both $i$ and $j$, so we can write $i = ka$ and $j = kb$. Consequently, $i+j = ka + kb = k(a+b)$, so $k$ divides $i+j$ as well! $gcd(i,j)=gcd(i,j+i)=gcd(i+j,j)$

**Reply** by Steve Powell (2018-07-25):

> These two ways are essentially the same; the proof by induction uses the same common factor argument as the contradiction in the paper.
>
> Furthermore, the principle of induction and the well-foundedness of the integers (every non-empty collection has a least element) can be deduced from each other (with a contradiction argument like this one).

### Annotation 5 (page 3)

Beside the passage: “3. No reduced positive rational number occurs at more than one vertex. First, the rational”

**Annotation** by Luís Batalha (2018-07-16):

> Here's how can we prove that every positive number occurs in the tree. Let's start with a rational number, say $\frac{3}{5}$. To figure out if the number is a right or left node we just need to compare the denominator  with the numerator - in this case since 5>3, this is a right node. Then to determine the parent node we just need to calculate $\frac{3}{5-3}=\frac{3}{2}$ and we can keep doing this until we get to the root node $\frac{1}{1}$.
>
> ![](https://i.imgur.com/I4HdglS.png)
>
> This means that we can find a path up to the root node from any reduced positive rational. Since there was no choice at each step, there is exactly one path from any rational up to the root of the tree and each reduced rational occurs is only one place in the tree (there are no duplicates).

**Reply** by Marc Talbot (2018-07-17):

> For 3/5 and 5 > 3, shouldn't this be a left node, rahter than right node?

**Reply** by Rishabh Bhargava (2018-08-17):

> It's not clear to me how to determine whether a rational number in this tree will be a left child or a right child? From Figure 1, there are enough examples to show that just the relative magnitude of numerator and denominator isn't enough.

**Reply** by Luís Batalha (2018-08-27):

> @Rishabh Can you give me an example? In a left child the denominator is always bigger than the numerator and in a right child the numerator is always bigger than the denominator.

### Annotation 6 (page 4)

Beside the passage: “There is a large literature on the closely related subject of Stern-Brocot trees [Ste, Bro]. In particular, an excellent introduction is in [GKP], and the relationship between these trees and hyperbinary partitions is explored in [Rez]. In Stern’s original paper [Ste] of 1858 there is a structure that is essentially …”

**Annotation** by Luís Batalha (2018-07-16):

> It is possible to create a similar list via a deforestation of the Stern-Brocot tree of rationals.
>
> ![](https://upload.wikimedia.org/wikipedia/commons/thumb/3/37/SternBrocotTree.svg/500px-SternBrocotTree.svg.png)
>
> For more information on that go [here](https://pdfs.semanticscholar.org/6527/441cea8228a86d61ab4bf054e2f6c1008ef5.pdf).

## Full text

Extracted from the PDF. [Annotation N] marks where each annotation above sits.

#### Page 1

Recounting the rationals

Neil Calkin Department of Mathematics, Clemson University

Clemson, SC Herbert S. Wilf Department of Mathematics, University of Pennsylvania

Philadelphia, PA 19104-6395

September 4, 2008

We’re going to arrange the positive rational numbers in a list that begins like this:

1 1 [Annotation 1] , 1 2 , 2 1 , 1 3 , 3 2 , 2 3 , 3 1 , 1 4 , 4 3 , 3 5 , 5 2 , 2 5 , 5 3 , 3 4 , 4 1 , 1 5 , 5 4 , 4 7 , 7 3 , 3 8 , 8 5 , 5 7 , 7 2 , 2 7 , 7 5 , . . .

Some of the interesting features of this list are

1. The denominator of each fraction is the numerator of the next one. That means that the

nth rational number in the list looks like f(n)/f(n + 1) (n = 0, 1, 2, . . .), where f is a certain function of the nonnegative integers whose values are

{f(n)} n≥0 = {1, 1, 2, 1, 3, 2, 3, 1, 4, 3, 5, 2, 5, 3, 4, 1, 5, 4, 7, . . .}.

2. The function values f(n) actually count something nice. In fact, f (n) is the number of

ways of writing the integer n as a sum of powers of 2, each power being used at most twice (i.e., once more than the legal limit for binary expansions). For instance, we can write 5 = 4 + 1 = 2 + 2 + 1, so there are two such ways to write 5, and therefore f(5) = 2. Let’s say that f(n) is the number of hyperbinary representations of the integer n.

3. Consecutive values of this function f are always relatively prime, so that each rational occurs

in reduced form when it occurs.

4. Every positive rational occurs once and only once in this list.

1 [Annotation 2]

#### Page 2

1 1 u Q

Q

Q

Q

Q

Q

Q

Q Qs

        +

Q

Q

Q

Q

Q

Q

Q

Q

Q

         1 2 [Annotation 3] u e

e

e

e

e

e

% % % % % %

u 2 1 u e

e

e

e

e

e

% % % % % % 1 3

u A

A

A

A

A A

     

3 2

u A

A

A

A

A A

     

2 3

u A

A

A

A

A

A

     

3 1

u A

A

A

A

A A

      1 4

u A A  

4 3

u A A  

3 5

u A A  

5 2

u A A  

2 5

u A A  

5 3

u A A  

3 4

u A A  

4 1

u A A  

Figure 1: The tree of fractions

1 The tree of fractions

For the moment, let’s forget about enumeration, and just imagine that fractions grow on the tree

that is completely described, inductively, by the following two rules:

• 1 1 (the root ) is at the top of the tree, and

• Each vertex i j has two children: its left child is i i+j and its right child is i+j

j .

We show the following properties of this tree.

1. The numerator and denominator at each vertex are relatively prime. This is certainly true at

the top vertex. Otherwise, suppose r/s be a vertex on the highest possible level of the tree

for which this is false. If r/s is a left child, then its parent is r/(s − r), which would clearly

also not be a reduced fraction, and would be on a higher level, a contradiction. If r/s is a

right child, then its parent is (r − s)/s, which leads to the same contradiction.

2. Every reduced positive rational number occurs at some vertex. The rational number 1 ce r-

tainly occurs. Otherwise, let r/s be, among all fractions that do not occur, one of smallest

denominator, and among those the one of smallest numerator. If r > s then (r − s)/s doesn’t

2 [Annotation 4]

#### Page 3

occur either, else one of its children would be r/s, and its numerator is smaller, the denominator being the same , a contradiction. If r < s, then r/(s − r) doesn’t occur either, else one of its children would be r/s, and it has a smaller denominator, a contradiction.

3. No reduced positive rational number occurs at more than one vertex. First, the rational [Annotation 5]

number 1 occurs only at the top vertex of the tree, for if not, it would be a child of some vertex r/s. But the children of r/s are r/(r + s) and (r + s)/s, neither of which can be 1. Otherwise, among all reduced rationals that occur more than once, let r/s have the smallest denominator, and among these, the smallest numerator. If r < s then r/s is a left child of two distinct vertices, at both of which r/(s − r) lives, contradicting the minimality of the denominator. Similarly if r > s. 2

It follows that a list of all positive rational numbers, each appearing once and only once, can be made by writing down 1/1, then the fractions on the level just below the top of the tree, reading from left to right, then the fractions on the next level down, reading from left to right, etc.

We claim that if that be done, then the denominator of each fraction is the numerator of its successor. This is cle ar if the fraction is a left child and its successor is the right child, of the same parent. If the fraction is a right child then its denominator is the same as the denominator of its parent and the numerator of its succe ss or is the same as the numerator of the parent of its successor, hence the result follows by downward induction on the levels of the tree. Finally, the rightmost vertex of each row has denominator 1, as does the leftmost vertex of the next row, proving the claim.

Thus, after we make a single sequence of the rationals by reading the successive rows of the tree as described above, the list will be in the form {f(n)/f(n + 1)} n≥0 , for some f. Now, as the fractions sit in the tree, the two children of f (n)/f(n + 1) are f (2n + 1)/f(2n + 2) and f(2n + 2)/f(2n + 3). Hence from the rule of construction of the children of a parent, it must be that

f(2n + 1) = f(n) and f(2n + 2) = f(n) + f(n + 1) (n = 0, 1, 2, . . .).

These recurrences evidently determine our function f on all nonnegative integers.

We claim that f (n) = b(n), the number of hyperbinary re presentations of n, for all n ≥ 0. This is true for n = 0, and suppose true for all integers ≤ 2n. Now b(2n + 1) = b(n), because if we are given a hyperbinary expansion of 2n + 1, the “1” must appear, hence by subtracting 1 from both sides and dividing by 2, we’ll get a hyperbinary representation of n. Conversely, if we have such an expansion of n, then double each part and add a 1, to obtain a representation of 2n + 1.

Furthermore, b(2n + 2) = b(n) + b(n + 1), for a hyperbinary expansion of 2n + 2 might have either two 1’s or no 1’s in it. If it has two 1’s, then by deleting them and dividing by 2 we’ll get an expansion of n. If it has no 1’s, then we just divide by 2 to get an expansion of n + 1. These maps are reversible, proving the claim.

It follows that b(n) and f(n) satisfy the same recurrence formulas and take the same initial values, hence they agree for all nonnegative integers. We state the ﬁnal result as follows.

3

#### Page 4

Theorem 1 The nth rational number, in reduced form, can be taken to be b(n)/b(n + 1), where b(n) is the number of hyperbinary representations of the integer n, for n = 0, 1, 2, . . .. That is, b(n) and b(n + 1) are relatively prime, and each positive reduced rational number occurs once and only once in the list b(0)/b(1), b(1)/b(2), . . ..

2 Remarks

There is a large literature on the closely related subject of Stern-Brocot trees [Ste, Bro]. In particular, an excellent introduction is in [GKP], and the relationship between these trees and hyperbinary partitions is explored in [Rez]. In Stern’s original paper [Ste] of 1858 there is a structure that is essentially our tree of fractions, though in a diﬀerent garb, and he proved that every rational number [Annotation 6] occurs once and only once, in reduced form. However Stern did not deal with the partition function b(n). R eznick [Rez] studied restricted binary partition functions and observed their relationship to Stern’s sequence. Nonetheless it seemed to us worthwhile to draw these two aspects together and explicitly note that the ratios of successive values of the partition function b(n) run through all of the rationals.

References

[Bro] Achille Bro cot, Calcul des rouages par approximation, nouvelle m´ethode, Revue Chrono-

m´etrique 6 (1860), 186-194.

[GKP] Ronald L. Graham, Donald E. Knuth and Oren Patashnik, Concrete Mathematics, Addison-

Wesley, Reading, 1989.

[Leh] D. H. Lehmer, On Stern’s diatomic series, this monthly 36 (1929), 59-67.

[Rez] Bruce Reznick, Some binary partition functions, in Analytic Number Theory, Proceedings

of a conference in honor of Paul T. Bateman, Birkh¨auser, Boston (1990), 451-477.

[Ste] M. A. Stern, ¨ Uber eine zahlentheoretische Funktion, Journal f¨ur die reine und angewandte Mathematik 55 (1858), 193-220.

4

---

Source: [Fermat's Library](https://fermatslibrary.com/) — https://fermatslibrary.com/s/recounting-the-rationals. More annotated papers: https://fermatslibrary.com/llms.txt
