# An upper bound for the length of the continued fraction expansion of $\sqrt d$

Let $d\ge 2$ and let $$\sqrt d =[a_0; \overline{a_1,\dots, a_\ell, 2a_0}]$$ be its continued fraction expansion. Clearly, if $d=n^2+1$, then $\ell=0$, which gives the lower bound for $\ell$.

Question. What is the best known upper bound for $\ell=\ell(d)$ as a function of $d$?

For instance, $\ell(d)=O(d)$ is fairly trivial, following from the well-known algorithm (see [Rockett-Szusz], for instance). However, I suspect something like $O(\sqrt d)$ (or $O(\sqrt d\log d$) must be known.

• What can you say about numbers $d$ where $l$ is 1 or 2? Is it conceivable that the upper bound is constant? Gerhard "If You Dream, Dream Big" Paseman, 2015.04.16 Apr 16, 2015 at 18:37
• No, this is not possible. For instance, $\ell(2^{2k+1}\asymp 5^k$, according to E. Golubeva (1990). Apparently, this was already known in the 19th century. Apr 16, 2015 at 19:06

## 1 Answer

It is known that $\ell(d)=O(\sqrt{d}\log d)$ and $\ell(d)=\Omega(\sqrt{d}/\log\log d)$.

See Cohn's paper (free access) for more details.

For numerical results and some further historical comments see Williams's paper.

• That $\Omega$ is not consistent with the cases of $\ell=0$ in the question. I think it actually says $\ell(d)$ is not $o(\sqrt{d}/\log\log d)$. Apr 16, 2015 at 21:53
• @GeraldEdgar: In analytic number theory, $f(x)=\Omega(g(x))$ means that $f(x)=o(g(x))$ is false, and I followed that convention. See en.wikipedia.org/wiki/… Apr 16, 2015 at 22:34
• @GHfromMO Is there a relation between length of periods and factoring?
– VS.
Feb 13, 2020 at 15:12
• @VS.: I don't know. Feb 13, 2020 at 15:40