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.



What is the effect of adding 1/2 to a continued fraction?
[Gosper](http://www.inwap.com/pdp10/hbaker/hakmem/cf.html#item101b) 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]$.


