¿Cuál es el efecto de agregar 1/2 a una fracción continua?

Question

Hay una respuesta sencilla a la pregunta "¿qué sucede con la continuación de la fracción de expansión de un número irracional cuando se agrega 1/2?" Vinculado estrechamente a la pregunta es "¿qué le pasa a esa ampliación, cuando se multiplica por 2?"

Observaciones: no estoy seguro de lo que lo califica para una respuesta. La motivación viene de querer comprender mejor la relación de equivalencia en secuencias de enteros generados por la cola de equivalencia (la cual es generada por la adición de números enteros y de tomar recíprocos) y cierre bajo duplicar/reducir a la mitad. Es sabido que este Borel relación de equivalencia no es hyperfinite, por lo que la respuesta no puede ser demasiado simple.

Edit: Las respuestas no son realmente lo que estoy pidiendo. Es claro que hay algunas procedimiento recursivo para hacer esto, al igual que no hay un procedimiento recursivo para la toma de una raíz cuadrada de un número decimal de expansión. Estoy buscando algo que uno podría llamar una "forma cerrada". Por ejemplo, si usted comienza con un periódico expansión, añadiendo 1/2 produce un nuevo periódico expansión. Hay una transformación simple de la inicial y periódica de las piezas que corresponde a la adición de 1/2? Por ejemplo, se puede hacer esto con un autómata de estado finito? Una autoridad "no es tan bonita respuesta" realmente sería una respuesta aceptable.

Answer 1

Gosper mostró cómo producir la continuación de la fracción de

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

y aún más complicadas expresiones dadas las fracciones continuas para $x$ e $y$. Como un caso especial, que cubre fracciones de transformaciones lineales de $x$, lo que incluye, por supuesto, la adición de $1/2$ o multiplicar por $2$. No he digerido todavía.

Aquí es un caso especial: $2[a_0; 2a_1, a_2, 2a_3, a_4,...] = [2a_0; a_1, 2a_2, a_3, 2a_4, ...]$.

Otra manera de pensar acerca de estas es a través de las siguientes dos elementales resultados en simples fracciones continuas. En primer lugar, si $p_n/q_n$ e $p_{n+1}/q_{n+1}$ son adyacentes convergents de la simple continuación de la fracción de $x$,, a continuación, $|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)$ donde $a_{n+1}$ es un coeficiente de la simple continuación de la fracción de $x$. En segundo lugar, si $|p/q - \alpha | \lt 1/(2q^2)$ entonces $p/q$ debe ser convergente de la simple continuación de la fracción de $\alpha$. Cada vez que usted tiene un gran coeficiente en la simple continuación de la fracción de expansión para $x$ (es decir, al menos $8$, aunque creo que se puede hacer mejor), la anterior convergente $p/q$ es particularmente eficaz en la aproximación a $x$. A continuación, $p/q + 1/2$ es tan cerca de $x+1/2$, y el denominador de $p/q + 1/2$ es en la mayoría de las $2q$, lo $p/q + 1/2$ debe ser convergente de la simple continuación de la fracción de $x+1/2$. Del mismo modo, si $p/q$ es suficiente la aproximación a $x$,, a continuación, $2p/q$ debe ser convergente para $2x$. Incluso el convergents a $x$ que no están tan cerca todavía impiden la convergents de $x+1/2$ e $2x$.

---

Deje $\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}$.

A continuación, $\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}$

Multiplicando por $2$ es 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}$

Tenga en cuenta que $(x'-1)/2$ no está garantizado a ser mayor que $1$. Si no, entonces esto nos da un $0$ coeficiente en el medio de la simple continuación de la fracción de $\frac{1}{2}x$. El $0$ puede ser eliminado mediante la suma de los coeficientes en ambos lados. $[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}, ...]$

Por ejemplo, si $x = [a_0; a_1, a_2, a_3, ...]$ con $a_0$ impar y el resto de coeficientes incluso, a continuación,$\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}$.

También, tenga en cuenta que este patrón se parece mucho a la simple continuación de la fracción de $e = [2;1,2,1,1,4,1,1,6,1,1,8,...]$. Esto indica que algo relacionado con la $e$ tiene una simple continuación de la fracción, y, de hecho, esto es cierto. $\frac{e-1}{2} = [0; 1,6,10,14,18,...], \frac{e+1}{e-1} = [2;6,10,14,18,...]$.

Usted puede ver esto como que hay dos estados (aunque podría subdividir estos). En la primera, alternativamente dividir y multiplicar los coeficientes por $2$. En el segundo, el espacio de los coeficientes por $1$s, restar uno y dividirlos por $2$. Si usted encuentra un número impar cuando usted tiene que dividir por dos, luego pasa a la segunda unidos o quedarse allí. Si usted tiene que dividir un número por $2$, se mueve o permanece en el primer estado, y multiplicar el siguiente coeficiente por $2$.

De David Speyer observación, si se puede multiplicar por $2$ y dividir por $2$, entonces usted puede también agregar $1/2$. Sin embargo, es un poco más complicado. Grandes coeficientes de obtener aproximadamente multiplicado por $2$ o dividido por $2$ cuando se multiplica o divide $x$ por $2$. Cuando se agrega $1/2$, gran coeficientes a veces se dividen por $4$, a veces aproximadamente la misma estancia, y a veces ellos son más o menos multiplicado por $4$, y las operaciones que dependen del estado y el resto de los coeficientes $\mod 4$.

Por ejemplo, si $x = [0; 1, 1000, 2000, 3000, 4000, 5000]$ entonces $x+1/2 = [1; 2, 249, 1, 3, 499, 1, 3, 749, 1,3, 999, 1, 3, 1249, 1, 3]$. Si $y=[0;1,1001,2000,3000,4000,5000]$ entonces $y+1/2 = [1; 2, 250,8000,750,16000,1250]$.

Answer 2

Tipo de respuesta tardía, pero ya nadie lo mencionó creo que vale la pena señalar que el procedimiento para el cómputo de los homographies/lineal fraccional transformaciones en fracciones continuas (mencionado en Douglas Zare la respuesta) también fue descrito explícitamente en términos de autómatas de estado finito por George N. Raney, en "Sobre la continuación de las fracciones y los autómatas finitos", Mathematische Annalen 206:4, 1973. (Esto fue un poco después de Gosper memo, pero ni una cita a la otra, así que supongo que Gosper y Raney se acercó con estas ideas en forma independiente?)

Formalmente, Raney mostró cómo interpretar homographies $\phi(x) = \frac{ax + b}{cx + d}$ (por ejemplo, el mapa de $x \mapsto x + 1/2$, teniendo en $a=2,b=1,c=0,d=2$) como de los estados de estados finitos transductores. Las transiciones ejecutado por estos transductores son de la forma $$\phi_1 \underset{I:O}{\longrightarrow} \phi_2$$ donde $\phi_1$ e $\phi_2$ son de estados correspondiente a un par de homographies, y $I,O \in \{L,R\}^*$ son binarios palabras que describen una pieza de las fracciones continuas de la entrada y la salida, respectivamente. Tenga en cuenta que esta se basa en una codificación de fracciones continuas $x = [a_0;a_1,a_2,\dots]$ como secuencias binarias $R^{a_0}L^{a_1}R^{a_2}\cdots$ (que, por cierto, está estrechamente relacionado con el de Stern-Brocot/Calkin-Wilf representaciones de los racionales).

Estoy en su mayoría ignorante en cuanto a lo lejos Raney del enfoque que se ha tomado (y curioso a mí mismo). Sin embargo, una importante labor de seguimiento fue por Pierre Liardet y Pierre Stambul en "Cálculos Algebraicos con Fracciones continuas" (1998), donde se mostró cómo unificar Gosper y Raney de los enfoques de la construcción de transductores para interpretar general "bihomographies"/"biquadratic fracciones de transformaciones" $\phi(x,y) = \frac{axy + bx + cy + d}{exy + fx + gy + h}$.

---

ACTUALIZACIÓN: Me fui por delante y derivados de la Raney transductor para el cómputo de los $x \mapsto x + 1/2$.

• Hay cuatro estados de la $q_1,\dots,q_4$, que corresponde a la 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}
• Un total de 16 de las transiciones, las cuales se agrupan en ocho transiciones \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} junto con un juego doble de ocho transiciones: \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}

En caso de que usted está interesado, aquí está un poco de Haskell aplicación, que muestra cómo utilizar esta máquina para agregar 1/2 para la continuación de las fracciones que representan la proporción áurea y $e$.

Answer 3

Aquí están algunos de los resultados que sugieren que tal vez lo que sucede es ni muy simple ni muy al azar. Pero ver el final para un mejor resultado.

Estas son algunas de las más simples fracciones continuas a lo que conducen. Esto también le dice lo que los resultados en fracciones continuas simples debido a que $r-\frac12$ e $r+\frac12$ tienen el mismo continuó fracción después de la parte entera.

La décima fila dice que $$r=\frac{1+\sqrt3}{2}=1+\cfrac{1}{2+\cfrac{1}{1+\cfrac{1}{2+\cfrac{1}{1+\cfrac{1}{2+\cdots}}}}}$$ y $$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}}}}}$$

Cada línea es un número $r$, entonces la continuación de la fracción de $r$, entonces la continuación de la fracción de $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} $$

También miré los primeros resultados de la forma $[[3,j]]$ que parecían similares. Los números racionales también podría ser digno de una mirada.

más tarde como Douglas señala. Hay patrones que las tablas anteriores son sólo un poco demasiado breve para mostrar.

La continuación de la fracción $[[k]]$ corresponde a $\frac{k+\sqrt{k^2+4}}{2}$ y tenemos para $k \ge 2$ (y en algunos casos para $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 ]]$

Cosas similares suceden para $[[i,k]]$ $i=1,2$ dependiendo de la clase de congruencia $k \mod 4$ para $k$ no es demasiado pequeño.

Answer 4

Este es un comentario sobre los datos de Aarón Meyerowitz. Mi respuesta se muestra cómo agregar $1/2$ a un periódico simple continuación de la fracción, y que el comportamiento depende de los coeficientes de $\mod 4$. Para los pequeños coeficientes, el resultado puede tener algunos $0$s no está presente cuando se empieza con los coeficientes que son más grandes por $4$ o $8$. Estos degenerados $0$s causa adyacentes coeficientes de combinación: $[a_0;0,a_2] = [a_0+a_2]$. Esta es la razón por la que es difícil ver los patrones en su mesa, sino que aparecería si la mesa era un poco más grande.

Considere la posibilidad de $x=[4k; 4k, 4k, ...] = [\overline{4k}]$. $x+\frac{1}{2} = \frac{2x+1}{2}$. Así que, vamos a calcular $2x$, añada $1$, y luego se divide por $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}$

Se puede comprobar que para $k=2$, $[\overline{8}]+\frac{1}{2} = [8;\overline{1,1,1,1,1,7}]$ en Aaron Meyerowitz de la tabla. Desafortunadamente, termina antes de ver a $k=3$, por lo que es difícil ver el patrón. ¿Qué acerca de la $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}$

Aquí está otro ejemplo:

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

Esto encaja $[\overline{5}] + \frac{1}{2}$, degenerando en dos lugares donde $k-1=0$, e $[\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

Deje$x = [a_0; a_1, a_2, \ldots]$ y$y = \dfrac{bx+c}{dx+e}$ donde$b,c,d,e$ son enteros. $y = n$ para $x = \dfrac{-en+c}{dn-b}$. Al comparar las fracciones continuas para estos con los primeros$a_i$, puede determinar$\lfloor y \rfloor$. Si eso es$n$, entonces$y = n + 1/y_1$ donde$y_1 = \dfrac{dx+e}{(b-dn)x + (c-en)}$. Recurse ...