Задача 192
Наилучшие аппроксимации

Пусть x - действительное число.
Наилучшая аппроксимация x для ограниченного знаменателя d - рациональная дробь r/s в сокращенной форме, у которой sd, такая, что любое рациональное число, которое ближе к x, чем к r/s, имеет знаменатель больше d:

|p/q-x| < |r/s-x| ⇒ q > d

К примеру, наилучшая аппроксимация √13 для знаменателя, ограниченного значением 20, составляет 18/5. В свою очередь, для знаменателя, ограниченного значением 30, наилучшая аппроксимация √13 равна 101/28.

Найдите сумму всех знаменателей наилучших аппроксимаций √n, при ограничении на знаменатель равном 10^(12), где n не является идеальным квадратом и 1 < n ≤ 100000.

Оригинал
 
© Проект Эйлера | Translated problems from ProjectEuler.net