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\leq 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

Introducing continued fractions

Best approximations relate to continued fractions in that the continued fraction expansion is a best approximation in some sense

For a rational number, the continued fraction expansion is finite. We also know the fractions we're considering are rational. So we don't have to worry about a continued fraction expansion getting into an infinite loop.

(However, from past experience with continued fraction expansions, they CAN get reeeeeally long)

Crux of the problem

For a rational number, continued fraction expansion terminates, and best approximations are convergents

But problem mentions case of two best approximations for a given denominator bound

That happens when continue fraction expansion has coeff greater than 1,

then there are intermediate fractions that can also be best approximations fro certain bounds

For continued fraction, $[a_{0};a_{1},a_{2},\dots ,a_{n}]$, convergents are fractions obtained by truncating expansion at each step

There exists a denominator bound d such that there are two different fractions with denominators <= d equally close to x

Continued fraction of 9/40 is $[0;4,2,4]$

First convergent: $[0;4]={\frac {1}{4}}$

Second convergent: $[0;4,2]={\frac {1}{4+{\frac {1}{2}}}}={\frac {2}{9}}$

Third (final) convergent: $[0;4,2,4]={\frac {9}{40}}$

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]$