Return to Revisions

Sage – 119 117

x,X=map(int,sys.argv[1].split('/'))
a=0
A=c=C=1
while C<X:exec("ab,,AB"[c*X>C*x::2]+"=c,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.

Replace raw_input() with sys.argv[1] to have the input read from a command-line argument instead of a prompt. This does not change the character count. (Does not work in Python without importing sys first.)

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 on my machine.

Here is an ungolfed version:

x,X = map(Integer,sys.argv[1].split('/'))
x = x/X
a = 0
c = 1
while c.denominator() < X:
    if c > x:
        b = c
    else:
        a = c
    c = ( a.numerator() + b.numerator() ) / ( a.denominator() + b.denominator() )
print a,b