Back to search

Clemson University

The Calkin-Wilf Tree and Its Various Properties

Abstract

dc:description.abstract

The Tree of All Fractions, otherwise known as the Calkin-Wilf tree, gets its name from the fact that every reduced positive rational appears once in this binary search tree. We look at the various properties this tree is known to hold and will explore a plethora of related, yet new, characteristics within the patterns of the tree. One of the most interesting properties of the tree we will state is the numerators are the hyperbinary representation of that index in the sequence, as already observed by Calkin and Wilf. We will take look at this as well as the ordering of the numerators. We notice that some numbers in the sequence of numerators appeared "out of order," i.e. if N +1 appears before N in the sequence of numerators. We found these oddities and looked at the distance between these occurrences. We also look closely at the "paths'' of the rationals in the tree. The "path'' of an element is the right and left steps it takes to reach said element. We let 0 represent a left step and 1 represent a right step. We explore various ways to change or look at the paths, as well as with matrices that represent the left and right steps. We also question the claim, ∀∊ > 0 and x ∈ ℝ+, there exists an n such that $\left \vert x - \frac{a_n}{a_{n+1}} \right \vert < ∊. In other words, for any positive real number, there is a rational number that is incredibly close to the real number given. We use ideas from continued fraction approximations and computation to bring this claim to life. From this claim, we attempt to define a distrubtion over the real numbers.

Degree

thesis:*
Name thesis:degree_name
Master of Science (MS)
Level thesis:degree_level
Thesis
Discipline thesis:degree_discipline
Mathematical Sciences

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Kenyon, Catherine Mary
Contributors dc:contributor
  • Neil J Calkin, Committee Chair
  • Christopher S McMahan
  • William C Bridges

Subjects

dc:subject × 6

Identifiers

dc:identifier.*
Repository record dc:identifier
https://open.clemson.edu/all_theses/3075

Chain of custody

source
Harvested from
Clemson University
Base URL
open.clemson.edu/do/oai/
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Kenyon, Catherine Mary. The Calkin-Wilf Tree and Its Various Properties. Thesis thesis, https://open.clemson.edu/all_theses/3075