2011年7月10日星期日

Farey sequence

Farey sequence是一個order n,

F n = { x = h k | x | 0 h k n }
即是element是形如h/k的rational number,範圍在0和1之間,約簡後沒有重複。

def farey_seq(n):
    '''Return list of farey sequence.

    >>> farey_seq(1)
    [Fraction(0, 1), Fraction(1, 1)]
    >>> farey_seq(2)
    [Fraction(0, 1), Fraction(1, 2), Fraction(1, 1)]
    '''
    if n < 1:
        raise ValueError('n must be >= 1.')
    return sorted(set(fractions.Fraction(h, k) for k in range(1, n+1) for h in
        range(k))) + [fractions.Fraction(1)]

>>> farey_seq(5)
[Fraction(0, 1), Fraction(1, 5), Fraction(1, 4), Fraction(1, 3), Fraction(2, 5),
 Fraction(1, 2), Fraction(3, 5), Fraction(2, 3), Fraction(3, 4), Fraction(4, 5),
 Fraction(1, 1)]

這個sequence很有趣,它不像Fibonacci sequence可以一直延續下去,有無限個element。它每一個order只有有限個數(但當然有無限多個order),每一個分數都是約簡了的,即是分子和分母coprime,所以不計每個order中的第一個element 0/1,element數量是1到n的coprime combination數量,即是1至n的Euler's totient function總和+1。
F n = 1 + k = 1 n φ k
假設其中一個item h/k,因為是約簡分數,所以gcd(h, k) = 1。根據Euclidean algorithm,會有x和y

k x - h y = 1
而gcd(x, y) = 1,x和y有多過一個solution, x 1 = x 0 + r h y 1 = y 0 + r k 。所以,只要y ≦ n,x/y也是order n中的一個約簡份數。 x y - h k = 1 k y

如果,x/y並不是緊貼h/k的分數,假設是a/b,
a b - h k = a k - b h b k
1 k y a k - b h b k
但問題係,

b y · a k - b h > n

b不可能大過n,y*(ak - bh)也不會大過n, 故(ak - bh)只可能等如1,所以b = y。

而除了頭尾外,中間每個elment都可以由前後的分子和分母相加而得。

h n k n = h n - 1 + h n + 1 k n - 1 + k n + 1

沒有留言:

發佈留言