Return to Revisions

Sage – 119

x,X=map(int,raw_input().split('/'))
a=0
A=c=C=1
while C<X:
    if c*X>C*x:b=c;B=C
    else:a=c;A=C
    c=a+b;C=A+B
print a/A,b/B

Sage is only needed in the last line, which takes care of the output. Everything else also works in Python.

This essentially recursively constructs the respective Farey sequence using mediants of the existing elements, but restricts itself to those elements closest to the input. From another point of view, it runs a nested-interval search on the respective Farey sequences.

It correctly processes all of the examples in less than a second.