## Sage – 147

<!-- language: lang-python -->

	p,q=map(int,raw_input().split('/'))
	a=[(0,1),0]
	c=d=1
	while d<q:a[c*q>p*d]=c,d;c=a[0][0]+a[1][0];d=a[0][1]+a[1][1]
	R=Rational
	print R(a[0]),R(a[1])

Sage is only needed in the last two lines, which take care of the output. Everything else also works in Python.

This essentially recursively constructs the respective [Farey sequence](http://en.wikipedia.org/wiki/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.