Project Euler/198

Problem Statement

A best approximation to a real number x for the denominator bound d is a rational number $ \frac r s $ (in reduced form) with $ s \le d $, so that any rational number $ \frac p q $ which is closer to x than $ \frac r s $ has $ q > d $

Usually the best approximation to a real number is uniquely determined for all denominator bounds. However, there are some exceptions, e.g. $ \frac 9 {40} $ has the two best approximations $ \frac 1 4 $ and $ \frac 1 5 $ for the denominator bound 6. We shall call a real number x ambiguous if there is at least one denominator bound for which x possesses two best approximations. Clearly, an ambiguous number is necessarily rational. How many ambiguous numbers $ x=\frac p q, 0 < x < \frac 1 {100} $, are there whose denominator q does not exceed $ 10^8 $?

examples

9/40 is an ambiguous number, with two best approximations 1/4 and 1/5, for a denominator bound of 6 (q < 6)

conditions

$ 0 < \frac p q < \frac 1 {100} $

The smallest possible value of p is 1, implying q > 100. We also know q < 1e8, from the problem statement. This provides an absolute range for q.

For a given denom q, poss num p must satisfy some constraints:

• p and q are coprime, so $ \mbox{gcd}(p,q) = 1 $
• $ p \geq 1 $
• $ p \leq \frac q {100} $

Technique

Start with a program that won't scale, and generate intermediate solutions (smaller values of q limit) that we can trust.

Introduce optimizations to scale better, use intermediate solutions to verify answers don't change

Develop insights about ambiguous numbers in the process

Counting ambiguous fractions

Want to count the number of ambiguous fractions

(Note: can also try counting total number of fractions, then subtracting total number of non-ambiguous fractions)

We know a fraction p/q is not ambiguous if the continued fraction is $ [0; a_1] $ or $ [0; a_1, 1, 1, \dots, 1] $