Admissible qx+1 Sequences, Semiconvergents, and Rational Catalan Numbers

Abstract

Let $q\ge 3$ be odd and put $m_r=\lfloor r{\log }_{2}q\rfloor$. We count parity sequences with exactly $r$ entries equal to $1$ for which the coefficient in the $qx+1$ iteration first drops below $1$ at step $m_r+1$. Their number $a_q(r)$ also counts the corresponding residue classes modulo $2^{m_r+1}$. By classifying increasing integer sequences according to the first index at which they exceed a prescribed bound, we obtain a recurrence which, for $q=3$, establishes the five- or six-term block pattern conjectured in 2015, allowing a shorter final block. We establish the sharp inequalities \[ \frac1r\binom{m_r-1}{r-1}\leq a_q(r)\leq\frac1r\binom{m_r}{r-1} \] Equality in the lower (respectively upper) bound occurs exactly when $\{r{\log }_{2}q\}$ is smaller (respectively larger) than all preceding fractional parts $\{j{\log }_{2}q\}$, $1\le j<r$. These indices are characterized by denominators of convergents and semiconvergents from below and above; at these indices $r\ge 2$, the values $a_q(r)$ are rational Catalan numbers. We also characterize the dependence on $q$ and prove, for each fixed odd $q\ge 3$, that $a_q(r)={\Theta }_q(r^{-3/2}{B}_q^r)$, where $B_q=({\log }_{2}q{)}^{{\log }_{2}q}/({\log }_{2}q-1{)}^{{\log }_{2}q-1}$. For $q=3$, this proves Hikawa's conjectured polynomial factor for the number of finite binary words of given weight for which the length of every nonempty prefix is smaller than ${\log }_{2}3$ times the number of its ones.

arXiv comment19 pages, 2 tables. The author thanks the editors of the Journal of Integer Sequences for comments on an earlier version, particularly for noting that Proposition 6 holds for every nondecreasing bound