In this question it is shown that if a continued fraction of some rational $\frac{p}{q}=[a_0; a_1, \dots, a_n]$ is symmetrical (i.e. $a_k = a_{n-k}$) then $q^2 \equiv(-1)^n \pmod{p} $. A converse is also true, that is:
1) Given a rational $\frac{p}{q} \ge 1$ in reduced form with continued fraction of length $n+1$, if $q^2 \equiv (-1)^n \pmod{p}$ then the continued fraction is symmetrical.
Note that the condition $q^2 \equiv (-1)^n \pmod{p}$ for some $n$ isn't enough, it must exactly coincide with the length of the continued fraction to work. For example, $\frac{25}{18}$ is such that $18^2 \equiv -1 \pmod{25}$, but since $\frac{25}{18} = [1;2,1,1,3]$ has length $5$ (and $(-1)^{5-1} = +1\neq -1$) then the continued fraction isn't symmetric.
Because of this converse, we can classify symmetric continued fractions in $2$ groups: The odd-length group ($q^2 \overset{p}{\equiv} 1$) and the even-length group ($q^2 \overset{p}{\equiv} -1$).
Since $p$ must be greater than $q$, we can do an exhaustive search for all symmetric continued fractions (SCFs) by: Solving $x^2 \equiv \pm 1 \pmod{p}$ for each $p$ and $x\le p$, and then checking that the parity of the length of the continued fraction $\frac{p}{x}$ correctly matched the sign of $x^2 \equiv \pm 1 \pmod{p}$ according to 1).
Doing this search you can also track how many continued fractions with numerators less than or equal to $p$ are of odd-length vs even-length. As an example, for $p < 15$ we have that $$ \text{Even group }(p) = \begin{cases} \frac{5}{2} &= [2; 2]\\ \frac{10}{3} &= [3; 3]\\ \frac{13}{5} &= [2; 1, 1, 2] \end{cases} \qquad \text{Odd group }(p)\begin{cases} \frac{8}{3} &= [2; 1, 2]\\ \frac{12}{5} &= [2; 2, 2] \end{cases} $$ as the only SCFs with numerators less than $15$.
It turns out that the number of odd-length SCFs with numerators less than some $p$ appears to be more than the number of even-length SCFs with numerators less than $p$, with the ratio increasing as $p$ increases. Here are some graphs of the quotient of the number of odd SCFs over the number of even SCFs with numerators less than $p$:
So again recalling the example, at $p=15$ this graphs $\frac{2}{3}$ since there are $2$ odd SCFs and $3$ even SCFs with numerators less than $15$. After re-scaling the $x$-axis to be a logarithmic scale I got the following (on the right):
This appears to suggest that the increase in the ratio is (somewhat) logarithmic.
My questions are:
- Is there a simple way to see why we get "more" (in the sense described by the ratio above) symmetric continued fractions of odd length than even length? Is this just a consequence of how easy $x^2 \equiv \pm 1 \pmod{p}$ is to solve?
- Is there an easy heuristic/intuition as to why the growth rate is the way it is? Can we get a more specific growth rate?
Thanks for reading!