Rational Counting Function Create a function that takes a natural number (starting from 0 inclusive), and returns a pair of positive integers, which are the numerator and denominator respectively.
Use the diagonal traversal. Previous-counted numbers must be skipped. (you can memorize the set of skipped values)

Diagram:



Red are skipped values

Values:


f(0) = 1, 1
f(1) = 2, 1
f(2) = 1, 2
f(3) = 1, 3
f(4) = 3, 1 (notice the skip)
f(5) = 4, 1
f(6) = 3, 2
f(7) = 2, 3
f(8) = 1, 4
f(9) = 1, 5
f(10) = 5, 1 (notice the skip)


You may use the Rational data structure and their operations if they exist.
Shortest code wins.
Haskell, 78 characters

q(r,f)=[(r-b,b)|b&lt;-f[1..r-1],r`gcd`b==1]
d=reverse:id:d
f=((zip[2..]d&gt;&gt;=q)!!)


Sample run:

&gt; map f [0..10]
[(1,1),(2,1),(1,2),(1,3),(3,1),(4,1),(3,2),(2,3),(1,4),(1,5),(5,1)]
&gt; f 100
(17,1)
&gt; f 1000
(3,55)





Edit: (100 → 87) silly me, just testing the gcd is enough!
Edit: (87 → 85) clever trick with cycle and functions to alternate row order
Edit: (85 → 82) replace cycle with the hand-built infinite list d
Edit: (82 → 78) applied gcd identity as suggested by Matías