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 $ p \geq 1 $ and $ 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.

Then, introduce optimizations to scale further, and use intermediate solutions to verify optimizations aren't changing answers.

Develop insights about ambiguous numbers in the process.

q < 10,000 is very fast to compute, but q < 1,000,000 can take way, way longer.