2014年12月3日星期三

Infinite Fractions

這段片介紹一個sequences,包含所有rational number,沒有重複而且全是約化。

因為這是sequences,和integer bijection,所以亦証明了rational number是和integer有著相同的cardinality。

片中引用的paper Recounting the rationals [PDF]。


這個sequences的Python implementation如下:

def stern_brocot_seq():
    l = [1, 1]
    while True:
        l.extend([l[0] + l[1], l[1]])
        l.extend([l[1] + l[2], l[2]])
        yield l.pop(0)
        yield l.pop(0)

沒有留言:

發佈留言