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

• Introduction
• Complete and Reduced Residue Systems
• Euler's Totient Function
• Calculating the Totient Function by Hand

Introduction

Today we're going to delve into a little bit of number theory.

In number theory, we are usually dealing with modular arithmetic - expressions of the form:

or

The mod indicates we're doing modular arithmetic, which is (formally) an algebraic system called a ring, which consists of the integers 0 through m.

An analogy to modular arithmetic is the way that the sine and cosine function "wrap around," and

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 …

Table of Contents

• Newton's Method for Finding Roots of Equations

• Newton's Method for Finding Square Roots

• Newton's Method for Finding Square Roots: Program

• Accuracy

• Speed

• Next Steps

• References

Newton's Method for Finding Roots of Equations

Suppose we have a function \(f(x)\) and we want to compute values of \(x\) for which \(f(x)=0\). These values of \(x\) are called the roots of \(f(x)\).

We can compute the roots using Newton's Method, which utilizes the derivative of the function to iteratively compute the roots of the function.

Newton's method begins with an initial guess. It evaluates the derivative …