What is the effect of adding 1/2 to a continued fraction?

Question

Is there a simple answer to the question "what happens to the continued fraction expansion of an irrational number when you add 1/2?" A closely related question is "what happens to such an expansion when you multiply by 2?"

Remarks: I'm not sure what qualifies for an answer. The motivation comes from wanting to better understand the equivalence relation on integer sequences generated by tail equivalence (which is generated by adding integers and taking reciprocals) and closure under doubling/halving. It is known that this Borel equivalence relation is not hyperfinite, so the answer cannot be too simple.

Edit: The answers are not really what I am asking for. It is clear there is some recursive procedure for doing this, just like there is a recursive procedure for taking a square root of a decimal expansion. I'm looking for something which one might call a "closed form". For instance, if you start with a periodic expansion, adding 1/2 produces a new periodic expansion. Is there a simple transformation on the initial and periodic parts which corresponds to adding 1/2? For instance, can this be done with a finite state automaton? An authoritative "there is no such nice answer" would actually be an acceptable answer.

Answer 1

Gosper showed how to produce the continued fraction for

$$\frac{axy+bx+cy+d}{exy+fx+gy+h}$$

and even more complicated expressions given the continued fractions for $x$ and $y$. As a special case, he covers fractional linear transformations of $x$, which of course includes adding $1/2$ or multiplying by $2$. I haven't digested this yet.

Here is a special case: $2[a_0; 2a_1, a_2, 2a_3, a_4,...] = [2a_0; a_1, 2a_2, a_3, 2a_4, ...]$.

Another way of thinking about these is by way of the following two elementary results on simple continued fractions. First, if $p_n/q_n$ and $p_{n+1}/q_{n+1}$ are adjacent convergents of the simple continued fraction for $x$, then $|p_n/q_n - x| \le 1/(q_n q_{n+1}) = 1/(a_{n+1} q_n^2 + q_{n-1}) \lt 1/(a_{n+1} q_n^2)$, where $a_{n+1}$ is a coefficient of the simple continued fraction for $x$. Second, if $|p/q - \alpha | \lt 1/(2q^2)$ then $p/q$ must be a convergent of the simple continued fraction for $\alpha$. Every time you have a large coefficient in the simple continued fraction expansion for $x$ (say, at least $8$, though I think you can do better), the previous convergent $p/q$ is a particularly efficient approximation to $x$. Then $p/q + 1/2$ is just as close to $x+1/2$, and the denominator of $p/q + 1/2$ is at most $2q$, so $p/q + 1/2$ must be a convergent of the simple continued fraction for $x+1/2$. Similarly, if $p/q$ is a sufficiently close approximation to $x$, then $2p/q$ must be a convergent for $2x$. Even the convergents to $x$ which are not so close still constrain the convergents of $x+1/2$ and $2x$.

---

Let $\begin{eqnarray}x &=& [a_0; a_1, a_2, a_3, ...] \newline x' &=& [a_1; a_2, a_3, ...] \newline x'' &=& [a_2; a_3, a_4, ...]\end{eqnarray}$.

Then $\frac{1}{2} x = \begin{cases} [a_0/2 ; 2x']& a_0 ~\text{even} \newline [(a_0-1)/2;1,1,(x'-1)/2]& a_0 ~\text{odd}\end{cases}$

Multiplying by $2$ is similar: $2x = \begin{cases} [2a_0; x'/2] & a_1 \gt 1 \newline [2a_0+1; 1, (x''-1)/2] & a_1=1 \end{cases}$

Note that $(x'-1)/2$ is not guaranteed to be greater than $1$. If not, then this gives us a $0$ coefficient in the middle of the simple continued fraction for $\frac{1}{2}x$. The $0$ can be removed by adding together the coefficients on either side. $[a_0; a_1, a_2, ..., a_n, 0, a_{n+2}, a_{n+3},...] = [a_0; a_1, a_2, ..., a_n+a_{n+2}, a_{n+3}, ...]$

For example, if $x = [a_0; a_1, a_2, a_3, ...]$ with $a_0$ odd and the other coefficients even, then $\begin{eqnarray} \frac{1}{2}x &=& [(a_0-1)/2; 1, 1, (a_1-2)/2, 1, 1, (a_2 - 2)/2, 1, 1, (a_3-2)/2, ...] \end{eqnarray}$.

Also, note that this pattern looks a lot like the simple continued fraction for $e = [2;1,2,1,1,4,1,1,6,1,1,8,...]$. This indicates that something related to $e$ has a simpler continued fraction, and indeed this is true. $\frac{e-1}{2} = [0; 1,6,10,14,18,...], \frac{e+1}{e-1} = [2;6,10,14,18,...]$.

You can view this as that there are two states (though you could subdivide these). In the first, you alternately divide and multiply coefficients by $2$. In the second, you space the coefficients out by $1$s, subtract one and divide them by $2$. If you encounter an odd number when you have to divide by two, then you move to the second states or stay there. If you have to divide an even number by $2$, you move to or stay in the first state, and multiply the next coefficient by $2$.

From David Speyer's observation, if you can multiply by $2$ and divide by $2$ then you can also add $1/2$. However, it is a little more complicated. Large coefficients either get approximately multiplied by $2$ or divided by $2$ when you multiply or divide $x$ by $2$. When you add $1/2$, large coefficients sometimes get roughly divided by $4$, sometimes they roughly stay the same, and sometimes they are roughly multiplied by $4$, and the operations depend on the state you are in and the remainder of the coefficients $\mod 4$.

For example, if $x = [0; 1, 1000, 2000, 3000, 4000, 5000]$ then $x+1/2 = [1; 2, 249, 1, 3, 499, 1, 3, 749, 1,3, 999, 1, 3, 1249, 1, 3]$. If $y=[0;1,1001,2000,3000,4000,5000]$ then $y+1/2 = [1; 2, 250,8000,750,16000,1250]$.

Answer 2

Kind of a late response, but since no one else mentioned it I think it is worth pointing out that the procedure for computing homographies/linear fractional transformations on continued fractions (mentioned in Douglas Zare's answer) was also described explicitly in terms of finite state automata by George N. Raney, in "On continued fractions and finite automata", Mathematische Annalen 206:4, 1973. (This was a little after Gosper's memo, but neither one cites the other, so I suppose Gosper and Raney came up with these ideas independently?)

Formally, Raney showed how to interpret homographies $\phi(x) = \frac{ax + b}{cx + d}$ (e.g., the map $x \mapsto x + 1/2$, taking $a=2,b=1,c=0,d=2$) as states of finite state transducers. The transitions executed by these transducers are of the form $$\phi_1 \underset{I:O}{\longrightarrow} \phi_2$$ where $\phi_1$ and $\phi_2$ are states corresponding to a pair of homographies, and $I,O \in \{L,R\}^*$ are binary words describing a piece of the continued fractions of the input and output, respectively. Note that this is based on an encoding of continued fractions $x = [a_0;a_1,a_2,\dots]$ as binary sequences $R^{a_0}L^{a_1}R^{a_2}\cdots$ (which, incidentally, is closely related to the Stern-Brocot/Calkin-Wilf representations of the rationals).

I'm mostly ignorant as to how far Raney's approach has been taken (and curious myself). However, one significant follow-up work was by Pierre Liardet and Pierre Stambul in "Algebraic Computations with Continued Fractions" (1998), where they showed how to unify Gosper's and Raney's approaches by building transducers to interpret general "bihomographies"/"biquadratic fractional transformations" $\phi(x,y) = \frac{axy + bx + cy + d}{exy + fx + gy + h}$.

---

UPDATE: I went ahead and derived the Raney transducer for computing $x \mapsto x + 1/2$.

• There are four states $q_1,\dots,q_4$, corresponding to the homographies \begin{aligned} q_1(x) &= (2x + 1)/2 = x + 1/2 \\ q_2(x) &= 4x \\ q_3(x) &= x/4 \\ q_4(x) &= 2x/(x+2) \end{aligned}
• A total of 16 transitions, which can be grouped into eight transitions \begin{aligned} q_1 &\overset{R:R}{\longrightarrow} q_1 \\ q_1 &\overset{LL:LR}{\longrightarrow} q_2 \\ q_1 &\overset{LR:RLL}{\longrightarrow} q_3 \\ q_2 &\overset{R:RRRR}{\longrightarrow} q_2 \\ q_2 &\overset{LR:RR}{\longrightarrow} q_4 \\ q_2 &\overset{LLR:RL}{\longrightarrow} q_1 \\ q_2 &\overset{LLLR:RLLL}{\longrightarrow} q_3 \\ q_2 &\overset{LLLL:L}{\longrightarrow} q_2 \end{aligned} together with a dual set of eight transitions: \begin{aligned} q_3 &\overset{L:LLLL}{\longrightarrow} q_3 \\ q_3 &\overset{RL:LL}{\longrightarrow} q_1 \\ q_3 &\overset{RRL:LR}{\longrightarrow} q_4 \\ q_3 &\overset{RRRL:LRRR}{\longrightarrow} q_2 \\ q_3 &\overset{RRRR:R}{\longrightarrow} q_3 \\ q_4 &\overset{L:L}{\longrightarrow} q_4 \\ q_4 &\overset{RR:RL}{\longrightarrow} q_3 \\ q_4 &\overset{RL:LRR}{\longrightarrow} q_2 \\ \end{aligned}

In case you are interested, here is a little Haskell implementation, which shows how to use this machine to add 1/2 to the continued fractions representing the golden ratio and $e$.

Answer 3

Here are some results which suggest that perhaps what happens is neither very simple nor very random. But see the end for a better result.

These are some of the simplest continued fractions and what they lead to. This also tells you what results in simple continued fractions because $r-\frac12$ and $r+\frac12$ have the same continued fraction after the integer part.

The tenth row says that $$r=\frac{1+\sqrt3}{2}=1+\cfrac{1}{2+\cfrac{1}{1+\cfrac{1}{2+\cfrac{1}{1+\cfrac{1}{2+\cdots}}}}}$$ and $$r+\frac{1}{2}=1+\frac{\sqrt3}{2}=1+\cfrac{1}{1+\cfrac{1}{6+\cfrac{1}{2+\cfrac{1}{6+\cfrac{1}{2+\cdots}}}}}$$

Each line is a number $r$ then the continued fraction of $r$ then the continued fraction of $r+\frac12$$$ \begin {array}{ccc} \frac{1+\sqrt5}{2}&[[1]]&[[2,8]] \\1+\sqrt {2}&[[2]]&[[2],[1,10,1,1]] \\ \frac{3+\sqrt{13}}{2}&[[3]]&[[3],[1,4,14,4,1,2]] \\2+\sqrt {5}&[[4]]&[[4],[1,2,1,3]] \\ \frac{5+\sqrt{29}}{2}&[[5]]&[[5],[1,2,3,1,20,1,3 ,2,1,4]] \\3+\sqrt {10}&[[6]]&[[6],[1,1,1,24,1,1, 1,5]] \\ \frac{7+\sqrt{53}}{2}&[[7]]&[[7],[1,1,1,3,1 ,1,28,1,1,3,1,1,1,6]] \\4+\sqrt {17}&[[8]]&[[8],[ 1,1,1,1,1,7]] \\ \frac{9+\sqrt{85}}{2}&[[9]]&[[9],[1 ,1,1,1,3,2,36,2,3,1,1,1,1,8]] \\ \frac{1+\sqrt{3}}{2}&[[1,2]] &[[1,1],[6,2]] \\ \frac{3+\sqrt{21}}{6}&[ [1,3]]&[[1, 1],[3,4,3,2]] \\ \frac{1+\sqrt{2}}{2}&[ [1,4]]&[[1,1] ,[2]] \\ \frac{5+3\sqrt{5}}{10}&[ [1,5]]&[[1,1],[2,26, 2,2]] \\ \frac{3+\sqrt{15}}{6}&[ [1,6]]&[[1,1],[1,1,4 ,1,1,2]] \\ \frac{7+\sqrt{77}}{14}&[ [1,7]]&[[1,1],[1 ,1,2,8,2,1,1,2]] \\ \frac{2+\sqrt{6}}{4}&[ [1,8]]&[[1 ,1],[1,1,1,2]] \\ \frac{3+\sqrt{13}}{6}&[ [1,9]]&[[1, 1],[1,1,1,42,1,1,1,2]] \\1+\sqrt {3}&[ [2,1]]&[ [3,4]] \\ 1+ \frac{\sqrt{15}}{3}&[ [2,3]]&[[2],[1,3,1,3,1,1]] \\ 1+ \frac{\sqrt{6}}{2}&[ [2,4]]&[[2],[1,2,1,1]] \\ 1+ \frac{\sqrt{35}}{5}&[ [2,5]]&[[2],[1,2,6,2,1,1]] \\ 1+ \frac{2\sqrt{3}}{3}&[ [2,6]]&[[2],[1,1,1,8,1,1,1,1 ]] \\ 1+ \frac{3\sqrt{7}}{7}&[ [2,7]]&[[2],[1,1,1,2,1,2,1 ,1,1,1]] \\ 1+ \frac{\sqrt{5}}{2}&[ [2,8]]&[[2],[1]] \\ 1+ \frac{\sqrt{11}}{3}&[ [2,9]]&[[2],[1,1,1,1,6,1,1, 1,1,1]]\end {array} $$

I also looked at the first few results of the form $[[3,j]]$ which seemed similar. Rational numbers might also be worth a look.

later as Douglas points out. There are patterns which the tables above are just slightly too brief to show.

The continued fraction $[[k]]$ corresponds to $\frac{k+\sqrt{k^2+4}}{2}$ and we have for $k \ge 2$ (and in some cases for $k \ge 1$)

$2k+\sqrt{(2k)^2+1} \hspace{0.5in} [[4k]] \hspace{0.5in} [[4k],[1,1,k-1,1,1,4k-1]]$

$\frac{4k+1+\sqrt{(4k+1)^2+4}}{2} \hspace{0.5in} [[4k+1]] \hspace{0.5in} [[4k+1],[1,1,k-1,1,3,k,16k+4,k,3,1,k-1,1,1,4k]]$

$2k+1+\sqrt{(2k+1)^2+1} \hspace{0.5in} [[4k+2]] \hspace{0.5in} [[4k+2],[1,1,k,16k+8,k,1,1,4k+1]]$

$\frac{4k+3+\sqrt{(4k+3)^2+4}}{2} \hspace{0.5in} [[4k+3]] \hspace{0.5in} [[4k+3],[1,1,k,3,1,k,16k+12,k,1,3,1,1,4k+2 ]]$

Similar things happen for $[[i,k]]$ $i=1,2$ depending on the congruence class $k \mod 4$ for $k$ not too small.

Answer 4

This is a comment on the data from Aaron Meyerowitz. My answer shows how to add $1/2$ to a periodic simple continued fraction, and that the behavior depends on the coefficients $\mod 4$. For small coefficients, the result may have some $0$s not present when you start with coefficients which are larger by $4$ or $8$. These degenerate $0$s cause adjacent coefficients to merge: $[a_0;0,a_2] = [a_0+a_2]$. This is why it's hard to see the patterns in his table, but they would appear if the table were just slightly larger.

Consider $x=[4k; 4k, 4k, ...] = [\overline{4k}]$. $x+\frac{1}{2} = \frac{2x+1}{2}$. So, let's compute $2x$, add $1$, and then divide by $2$.

$2x = [8k; 2k, 8k, 2k, 8k,...] = [\overline{8k,2k}]$.

$2x+1 = [8k+1; 2k, 8k, 2k, 8k, ...] = [8k+1; \overline{2k, 8k}]$.

$\begin{eqnarray} x+\frac{1}{2} &=& [4k; 1, 1, ([\overline{2k,8k}]-1)/2] \newline &=&[4k;1,1,[2k-1; \overline{8k,2k}]/2] \newline &=&[4k;1,1,[k-1,1,1,([\overline{8k,2k}]-1)/2] \newline &=& [4k; 1,1,k-1,1,1,4k-1,1,1,([\overline{2k,8k}]-1)/2] \newline &=& [4k; \overline{1,1,k-1,1,1,4k-1}]\end{eqnarray}$

You can check that for $k=2$, $[\overline{8}]+\frac{1}{2} = [8;\overline{1,1,1,1,1,7}]$ in Aaron Meyerowitz's table. Unfortunately, it ends before you see $k=3$, so it's hard to see the pattern. What about $k=1$?

$\begin{eqnarray}[\overline{4}] +\frac{1}{2} &=& [4; \overline{1,1,0,1,1,3}] \newline &=&[4;\overline{1,1+1,1,3}] \newline &=& [4; \overline{1,2,1,3}] \end{eqnarray}$

Here is another example:

$[\overline{4k+1}] + \frac{1}{2}= [4k+1; \overline{1,1,k-1,1,3,k,16k+4,k,3,1,k-1,1,1,4k}]$

This fits $[\overline{5}] + \frac{1}{2}$, degenerating in two places where $k-1=0$, and $[\overline{9}]+\frac{1}{2}$.

$[\overline{4k+2}] + \frac{1}{2} = [4k+2; \overline{1,1,k,16k+8,k,1,1,4k+1}]$ $[\overline{4k+3}] + \frac{1}{2} = [4k+3; \overline{1,1,k,3,1,k,16k+12,k,1,3,k,1,1,4k+2}]$

Answer 5

Let $x = [a_0; a_1, a_2, \ldots]$ and $y = \dfrac{bx+c}{dx+e}$ where $b,c,d,e$ are integers. $y = n$ for $x = \dfrac{-en+c}{dn-b}$. By comparing the continued fractions for these to the first few $a_i$, you can determine $\lfloor y \rfloor$. If that is $n$, then $y = n + 1/y_1$ where $y_1 = \dfrac{dx+e}{(b-dn)x + (c-en)}$. Recurse...