Coast to Coast Seminar Series: Live from Clemson, South Carolina "Recounting the rationals"

Abstract

It is well known that the rationals are countable, that is, that there is a bijection from the non-negative integers to the rational numbers: as simple as the standard proof of this fact is, computationally it is remarkably mysterious. Indeed, at the moment, it is difficult to list, say, the 10^100th rational, and with current technology andalgorithms, impossible to give the 10^{300}th rational. In joint work with Herbert S. Wilf, we give an alternate enumeration of the positive rationals: after a detour via generating functions, restricted partitions and continuous nowhere differentiable functions, we will discuss computational advantages of our enumeration. In particular, we will give the last few digits of the numerator and denominator of the 10^{1000}th rational.