Recounting the rationals: twice [pdf]

Code to print both the Stern-Brocot tree and the Calkin-Wilf tree, using the algorithm in that paper:

  def fractions():
      a,b,c,d = 1,0,0,1
      while True:
        yield a,b,c,d
        if a == 1 and b == 0 and d == 1:
          a,b,c,d = 1,c+1,0,1
        else:
          j = (c+d-1)//(a+b)
          k = 2*j+1
          a,b,c,d = k*a-c,k*b-d,a,b

  g = fractions()
  for i in range(100):
      a,b,c,d = g.next()
      print "%d/%d %d/%d"%(c+d,a+b,a+c,b+d)