■ファレイ数列とディオファントス近似(その1)

 n≧1とする.分母が正でかつnを越えないようなすべての既約分数を増大する順に並べたものを,位数nのファレイ数列と呼ぶ.

===================================

【1】ファレイ数列の生成

 n位のファレイ数列とは分子と分母がnを超えない既約な正の有理数全体を大きさの順に並べたものであるが,まず[0/1,1/1]からはじめ,(0+1)/(1+1)=1/2をはじめの2つの分数の間に挿入する.→[0/1,1/1]

漸次,隣接する2項p/qとr/sの間に中間分数

  (p+r)/(q+s)

を挿入する操作を可能な限り続けることによって得られる.「ただし,第n列の分母はすべてnを超えないものとする.」

[0/1,1/1]

→[0/1,1/2,1/1](2位のファレイ数列)

→[0/1,1/3,1/2,2/3,1/1](3位のファレイ数列)

→[0/1,1/4,1/3,1/2,2/3,3/4,1/1](4位のファレイ数列)

→[0/1,1/4,1/3,2/5,1/2,3/5,2/3,3/4,1/1](5位のファレイ数列)

→[0/1,1/6,1/5,1/4,1/3,2/5,1/2,3/5,2/3,3/4,4/5,5/6,1/1](6位のファレイ数列)

→[・・・,0/1,1/7,1/6,1/5,1/4,2/7,1/3,2/5,3/7,1/2,4/7,3/5,2/3,5/7,3/4,4/5,5/6,6/7,1/1,・・・](7位のファレイ数列)

→[0/1,1/5,1/4,2/7,1/3,3/8,2/5,3/7,1/2,4/7,3/5,5/8,2/3,5/7,3/4,4/5,1/1](8位のファレイ数列)

が得られる.

 n位のファレイ数列はa/b (0<a<b≦n)なる既約分数のすべてを大きさの順に並べたものになっている.

 位数nのファレイ数列の長さをA(n),分数の総和をS(n)とすると,オイラー関数φ(n)を用いて,

  A(n)=2S(n)

 =1+φ(1)+φ(2)+・・・+φ(n−1)+φ(n)

 〜3(n/π)^2〜0.30396n^2

になる.この近似はnが大きくなるにつれてよくなっていく.

===================================