Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
add comment

4 Answers

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]$.

share|improve this answer
4  
See also Knuth, "The Art of Computer Programming", vol. 2, sec. 4.5.3 ex. 14. –  Robert Israel Apr 25 '13 at 5:36
3  
Note $z+1/2 = (1/2) (2z+1)$. And $[a_0, a_1, a_2, \ldots]+1 = [1+a_0, a_1, a_2, \ldots]$. So adding $1/2$ and multiplying/dividing by $2$ are equivalent. –  David Speyer Apr 25 '13 at 12:04
    
@David:Actually I think this is not quite true. Unless I am missing something, this is not reversible. You can, however, multiply by 4 by adding 1/2 and reciprocating though. The point is that multiplication by 1/2 corresponds to operations in PSL_2(Z[1/sqrt(2)]), while adding 1/2 comes from PSL_2(Z[1/2]). –  Justin Moore Apr 26 '13 at 10:46
1  
@Douglas: thanks, but this is not really what I'm asking. The 2[a0;2a1,a2,2a3,a4,...]=[2a0;a1,2a2,a3,2a4,...] part is in the spirit of what I want, but I want something analogous which works for any sequence. I was aware of this observation --- the hard part is of course in dealing with the remainders. –  Justin Moore Apr 26 '13 at 12:07
    
There is some redundancy in the rules I mentioned for multiplying and dividing by $2$. If you are willing to clean up $0$ coefficients later, you can use the first rule for multiplying by $2$ every time. For example, $2[10;1,2,3] = [20; [1;2,3]/2] = [20; 0,1,1,([2;3]-1)/2 = [21;1,([2;3]-1)/2]$. –  Douglas Zare Apr 29 '13 at 1:36
show 6 more comments

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.

share|improve this answer
    
If you control the coefficients of the original $\mod 4$ then you get relatively simple patterns which often degenerate due to $0$ coefficients in the first cases. The above tables aren't quite large enough to show the patterns, but they show up if you extend the table slightly. –  Douglas Zare Apr 28 '13 at 23:40
    
Yes, I now realize that. –  Aaron Meyerowitz Apr 29 '13 at 2:24
add comment

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}]$

share|improve this answer
add comment

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...

share|improve this answer
    
Thanks, but this is not really what I'm asking. See the comments in the edit portion of the question. –  Justin Moore Apr 26 '13 at 12:05
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.