Project Euler problem 198 is a number theory problem that turns out to be almost entirely about continued fractions. The problem hides this - the statement talks about "ambiguous" real numbers - but the ambiguity has a clean characterization in terms of continued fraction expansions, and once you see it, the problem gets a lot smaller.

Wiki notes: Project Euler/198.

The Problem

Define a best approximation to a real number x with denominator bound d as a rational r/s in reduced form with s ≤ d, such that any other rational p/q closer to x than r/s has q …

Favorite Pi Approximations

What's your favorite \(\pi\) approximation?

Some of my favorite approximations of \(\pi\) come from Ramanujan-Sato series. These are mathematical series that generalize from a remarkable formula for \(\pi\) given by Srinivasa Ramanujan, an Indian mathematician:

Table of Contents

• Number Systems and Representations
• Continued Fraction Representations
• Convergents of Continued Fractions
• Example: Continued Fraction Coefficients of \(\sqrt{14}\)
• Example: Convergents of \(\sqrt{14}\)
• Approximating Square Roots

Continued Fractions

Let's start part 2 of our discussion of computing square roots by talking about continued fractions. When we first learn mathematics, we learn to count in the base 10 system: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. We can construct representations of all of the integers using these 10 digits, by arranging them in a different order. So, for example, saying 125 is equivalent to saying …