3 ms·
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 Tr
by user2994cb 9y ago
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)