法里數列

數學上,n階的法里數列是0和1之間最簡分數數列,由小至大排列,每個分數的分母不大於n。每個法里數列從0開始,至1結束,寫作0111,但有些人不把這兩項包括進去。有時法里數列也稱為法里級數,嚴格來說這名字不正確,因為法里數列的項不會加起來。

例子

1至8階的法里數列如下:

F1 = {01, 11}
F2 = {01, 12, 11}
F3 = {01, 13, 12, 23, 11}
F4 = {01, 14, 13, 12, 23, 34, 11}
F5 = {01, 15, 14, 13, 25, 12, 35, 23, 34, 45, 11}
F6 = {01, 16, 15, 14, 13, 25, 12, 35, 23, 34, 45, 56, 11}
F7 = {01, 17, 16, 15, 14, 27, 13, 25, 37, 12, 47, 35, 23, 57, 34, 45, 56, 67, 11}
F8 = {01, 18, 17, 16, 15, 14, 27, 13, 38, 25, 37, 12, 47, 35, 58, 23, 57, 34, 45, 56, 67, 78, 11}

歷史

「法里數列」歷史頗為稀奇。 — Hardy & Wright (1979) 第三章
……又一次,數學關係的名字取自一個人,但記錄所載這人不是其發現者。 — Beiler (1964) 第十六章

法里數列是以英國地質學老約翰·法里得名,他關於這數列的信刊登在1816年的《哲學雜誌》。法里猜測這數列的每一項都是相鄰兩項的中間分數;不過,以所知道的資料,他沒有證明這個性質。法里的信給柯西讀了,就給了一個證明在他的《數學習題》,把這結果歸到法里上。其實,另一位數學家 C. Haros 曾在1802年發表了相類似的結果,幾乎可以肯定法里和柯西都沒看過。所以,法里的名字給了這個數列,是歷史的一次意外。

性質

數列長度

n階的法里數列 包含了較低階的法里數列的全部項,特別是它包含 的全部項,和與n互質的每個數的相應分數。所以 包含了 和分數1656。對大於1的n,其法里數列的中間項必定是12

從上,  的長度的關係,可以用歐拉函數 描述:

 

 這項資料,可以推導出 的長度公式:

 

 的漸近行為是:

 

數列鄰項

法里數列的相鄰分數項有下述性質:

abcd是法里數列的鄰項,而有ab < cd,則它們之差cd − ab1bd。由於

 

上文就等於是說

bc − ad = 1。

例如1325 中是鄰項,它們之差為115

這結果的逆命題也成立。若

bc − ad = 1,

其中a,b,cd為正整數,及有a < bc < d,則abcd在階為 的法里數列中是鄰項。

pq在某法里數列的鄰項是abcd,及

ab < pq < cd

pqabcd中間分數。換句話說,

 

又若abcd在某法里數列是鄰項,則當法里數列的階增加,它們間出現的第一項是

 

而這項第一次出現在b+d階的法里數列中。

例如在1325間出現的第一項是38,在 出現。

Stern-Brocot樹是一個資料結構,顯出如何從0 (= 01)和1 (= 11)開始,以取中間分數來構成法里數列。

法里數列中的鄰項分數,它們的連分數表示形式也密切相關。每個分數都有兩個連分數表示,一個的尾項為1,另一個則大於1。考慮pq,它第一次於 出現。以連分數表示為

 ,或
 

pq 中最接近的鄰項(這是兩鄰項中分母較大的)表示為連分數是

 

而另一鄰項則會表示為

 

例如38有兩個連分數表示:[0;2,1,1,1]和[0;2,1,2],而它在 中的鄰項為25,可寫成[0;2,1,1];和13,可寫成[0;2,1]。

福特圓

法里數列和福特圓英语Ford circle之間有個有趣關連。

對每個最簡分數pq,有福特圓C[pq],以 為半徑,以 為圓心。兩個不同分數的福特圓一是分開,一是相切,但不會相交。若0 < pq < 1,則與相切的福特圓正好是在某一法里數列中與pq為鄰項的分數。

例如C[25]與C[12],C[13],C[37],C[38]等相切。

F1--F8的福特圓圖像如下:

 

外部連結