# Representation of rationals as finite continued fractions with restricted coefficients

This question and its answer incidentally show that every non-zero rational number $$q$$ can be written as a finite generalised continued fraction of the form:

$$\dfrac{2^{n_0}}{1- \dfrac{2^{n_1}}{1 - \dfrac{2^{n_2}}{1- \dfrac{2^{n_3}}{\ddots\dfrac{\ddots}{1-2^{n_{r(q)}}}}}}}$$

with $$n_i \in \Bbb N$$ and $$r(q) \ge 1$$ depending on $$q$$. For example: $$\frac{14}{9} = \dfrac2{1- \dfrac2{1 - 8}}$$ and

$$\frac{9}{5} = \dfrac1{1- \dfrac4{1 - \dfrac8{1- 2}}}$$ and $$-17 = \dfrac1{1- \dfrac2{1 - \dfrac8{1- \dfrac2{1-\dfrac4{1-\dfrac4{1-2}}}}}}$$

(How to get the powers of $$2$$: Let $$v_2$$ be the $$2$$-adic valuation, then if $$v_2(q) \ge 0$$, set $$n_i = v_2(f^i(q))$$; if $$v_2(q) <0$$, set $$n_0=0, n_{i+1}= v_2(f^i\circ g(q))$$ where $$f(x)= 1-\frac{1}{x|x|_2}$$ and $$g(x) = 1-\frac{1}{x}$$ are the functions in that question resp. answer.)

Now, if we generalise from $$2$$ to an arbitrary natural $$k > 1$$ (in particular prime $$k$$, but why restrict to that), I wondered if it is also true that:

For every $$q \in \Bbb Q^*$$ there is a finite tuple $$(n_0, ..., n_{r(q)})$$ such that $$q = \dfrac{k^{n_0}}{1- \dfrac{k^{n_1}}{1 - \dfrac{k^{n_2}}{1- \dfrac{k^{n_3}}{\ddots\dfrac{\ddots}{1-k^{n_{r(q)}}}}}}}$$

or something similar/more general (what if the "$$1$$"'s are replaced by another natural number etc).

If not, which rationals can be written that way?

Also, as I basically know nothing about continued fractions and made up an ad hoc approach for the other question, so:

Are there standard tools for handling this kind of question from the theory of continued fractions?

Edit: After playing around a bit, it seems more natural to me (albeit I've neither proven sufficiency nor necessity) that for general $$k$$, one would allow a set of representatives modulo $$k$$ instead of the leading "$$1$$"'s, i.e.

$$q = \dfrac{k^{n_0}}{b_1- \dfrac{k^{n_1}}{b_2 - \dfrac{k^{n_2}}{b_3- \dfrac{k^{n_3}}{\ddots\dfrac{\ddots}{b_{n_q}-k^{n_{r(q)}}}}}}}$$

with the $$b_i \in \{1,2, ..., k-1\}$$. This would make a characterisation of the ones where all $$b_i=1$$ more subtle.

• The continued fraction with "+"s isn't going to get you any negative rational numbers. Additionally, it appears that you are allowing for the possibility of infinite continued fractions. My gut says each fraction will terminate, although I have nothing resembling a proof of that yet. Edited to add: Never mind, despite the ellipses, you say the tuples are finite. Jul 18, 2018 at 2:48
• @SteveB: Tried to correct both issues now (the "+" was wrong anyway, I thought it corresponded to $f(x) = 1+\frac{1}{x|x|_2}$, but it doesn't, sign error). Robert: $-17$ has the expansion it says, and $85/47= \dfrac1{1- \dfrac{2}{1 - \dfrac2{1- \dfrac4{1- \dfrac4{1- \dfrac2{1 - \dfrac4{1- \dfrac8{1-2}}}}}}}}$. As stated, every non-zero rational. I honestly do not understand anything else you write. Jul 18, 2018 at 17:02
• I have a proof by induction, but the formatting is taking more time than the math and it won't fit into the time between now and HEB closing. Jul 19, 2018 at 2:38
• My induction proof fell through. Jul 19, 2018 at 7:24
• @samerivertwice: I have not tried anything empirical, whatever that would mean precisely (I'd be happy to see something). As to that other form, good question; I do not know. Feb 17, 2021 at 3:19