Задача 243
Упругость

Положительная дробь, чей числитель меньше знаменателя, называется правильной дробью.
Для любого знаменателя d существует d−1 правильных дробей; к примеру, для d = 12:
^(1)/_(12) , ^(2)/_(12) , ^(3)/_(12) , ^(4)/_(12) , ^(5)/_(12) , ^(6)/_(12) , ^(7)/_(12) , ^(8)/_(12) , ^(9)/_(12) , ^(10)/_(12) , ^(11)/_(12) .

Назовем дробь, которую невозможно сократить, упругой дробью.
Далее, определим упругость знаменателя R(d) как отношение количества упругих правильных дробей к общему количеству правильных дробей с этим знаменателем; к примеру, R(12) = ^(4)/_(11) .
Вообще, d = 12 является наименьшим знаменателем, чья упругость R(d) < ^(4)/_(10) .

Найдите наименьший знаменатель d с упругостью R(d) < ^(15499)/_(94744) .

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