ファレイ数列
n に対応するファレイ数列の長さ |Fn| は、オイラーの (トーティエント) 関数 φ を用いて、
| F n | = 1 + ∑ m = 1 n φ ( m ) {\displaystyle |F_{n}|=1+\sum _{m=1}^{n}\varphi (m)}
と書ける。 この |Fn| の漸近的振舞いは、オイラーの関数の性質から、
| F n | ∼ 3 n 2 π 2 {\displaystyle |F_{n}|\sim {\frac {3n^{2}}{\pi ^{2}}}}
となることが知られている。
数列の長さがオイラーの関数で書けることは次のようにして確かめられる。 n に対応するファレイ数列は、定義から明らかなように n 未満の正の整数に対応するファレイ数列の数を全て含んでいなければならない。 特に、n に対応するファレイ数列 Fn (n > 1) は、Fn−1 に、分母が n で分子が n と互いに素な n 未満の各数であるような分数を付け加えたものになる。 例えば、F8 は F7 に {1/8, 3/8, 5/8, 7/8} を加えて並べ替えたものである。
オイラーの関数はまさにその引数以下でその数と互いに素な数の個数を表すものであるから、 |Fn| と |Fn−1| (n > 1) の関係は、
|Fn| = |Fn−1| + φ(n)
となることになり、初項 |F1| = 2 から最初の式が従う。