# Expected Cardinality of the First n Coefficients of a Continued Fraction

Is there anything known about the asymptotic expected growth of $card\{a_0,a_1,...,a_n\}$, where the $a_i$ are the first $n$ coefficient of a continued fraction $[a_0; a_1, ... ]$?

• What does this mean? You are asking about the cardinality of a set of $n+1$ elements??? – Igor Rivin Aug 18 '15 at 14:00
• @IgorRivin no, as the $a_i$ need not be distinct, there may (or better will) be fewer than $n$ distinct elements in the set. I agree that my notation is misleading, but I don't know how to express the set that contains the first $n$ parameters of the continued fraction. Any suggestions are highly welcome. – Manfred Weis Aug 18 '15 at 14:49
• At least for quadratic irrational numbers, the cardinality is bounded above. – Sungjin Kim Aug 18 '15 at 14:56
• yes, it actually is $O(1)$, but the interesting question is, whether some expected growth could be quantified; I guess there should be something in that line in analogy to the Khinchin constant or the Levy constant. – Manfred Weis Aug 18 '15 at 14:59

Since the question asks about an expectation, one needs to specify a probability space of continued fractions. It seems the most natural such space is the interval $[0,1)$ with the density function $1/(1+x)$ that is the natural invariant measure in the study of continued fractions. It is known (Khinchin) that the probability that $a_i=r$ is equal to $\log(1+\frac1{r(r+2)})/\log 2$. Therefore the expected number of distinct $a_i$ among $a_1,\dots,a_k$ is (by linearity of expectation) $$\sum_{r=1}^\infty \bigg( 1 - \bigg(1- \frac{\log(1+\frac1{r(r+2)})}{\log 2} \bigg)^k \bigg).$$ (The $r$th summand is the probability that $r$ occurs at least once among $a_1,\dots,a_k$.) When $\frac1{r(r+2)}$ is small compared with $\frac1k$, then the $r$th summand is approximately $k\log(1+\frac1{r(r+2)})/\log 2 \asymp \frac k{r^2}$; the contribution of such terms where $r>R$ say (with $R$ large compared with $\sqrt k$) is $O(k/R)$. The contribution of the initial $\sqrt k$ or so terms should have order of magnitude $\sqrt k$. So I suspect that the expected number of distinct $a_i$ among the first $k$ partial quotients is asymptotic to some constant times $\sqrt k$. Numerical experimentation is reasonably consistent with this, with the constant quite close to $2.1$.
Results of Diamond and Vaaler (see Flajolet-Vallee-Vardi survey) and others would seem to indicate that the cardinality for a "random" number grows logarithmically with $n.$