yaworsw/euler-manager

---
:id: 198
:name: Ambiguous Numbers
:url: https://projecteuler.net/problem=198
:content: |+
  A best approximation to a real number <var>x</var> for the denominator bound <var>d</var> is a rational number <var>r</var>/<var>s</var> (in reduced form) with <var>s</var> ≤ <var>d</var>, so that any rational number <var>p</var>/<var>q</var> which is closer to <var>x</var> than <var>r</var>/<var>s</var> has <var>q</var> \> <var>d</var>.

  Usually the best approximation to a real number is uniquely determined for all denominator bounds. However, there are some exceptions, e.g. 9/40 has the two best approximations 1/4 and 1/5 for the denominator bound 6. We shall call a real number <var>x</var> _ambiguous_, if there is at least one denominator bound for which <var>x</var> possesses two best approximations. Clearly, an ambiguous number is necessarily rational.

  How many ambiguous numbers <var>x</var> = <var>p</var>/<var>q</var>, 0 \< <var>x</var> \< 1/100, are there whose denominator <var>q</var> does not exceed 10<sup>8</sup>?