Cómo detectar cuando termina el período de fracciones continuadas

Question

Estoy haciendo fracciones continuas aritmética. Hay un método para detectar cuándo la continuación de las fracciones período termina?
Déjeme darle un ejemplo: $\sqrt{2} = [1; \overline{2}]$, $\sqrt{7} = [2; \overline{1, 1, 1, 4}]$ y $\sqrt{14} = [3; \overline{1, 2, 1, 6}]$.
Ahora claramente $\sqrt{2} \times \sqrt{7} = \sqrt{14}$, pero si hacemos las fracciones continuas aritmética se obtiene: $[1; \overline{2}] \times [2; \overline{1, 1, 1, 4}] = 3, 1, 2, 1, 6, 1, 2, 1, 6, 1, 2, 1, 6, \dots$. Obviamente, esta secuencia no termina nunca, ya que la continuación de la fracción puede siempre la entrada de un término de cualquiera de las $\sqrt{2}$ o $\sqrt{7}$ (que son infinitos).

Así que mi pregunta es: ¿existe un método matemático para detectar cuando finalice el período (durante la adición, sustracción, multiplicación y división), en lugar de adivinar y comprobar?
Tal vez el uso de la $z$ (objeto deesta "cosa")? Por ejemplo, después de que se emite la primera $1$ es: $\left \langle \begin{matrix}13 & 31 & 28 & 67\\ 11 & 27 2& 8 & 20 \end{de la matriz}\right \rangle$

y cuando el tiempo comienza de nuevo: $\left \langle \begin{matrix} 549 & 1317 & 2226 & 5335\\ 95 & 239 & 814 & 2010 \end{matrix} \right \rangle$
y de nuevo: $\left \langle \begin{matrix} 92029 & 222405 & 122610 & 296283\\ 41317 & 99487 & 37841 & 91039 \end{matrix} \right \rangle$.

¿Hay algún tipo de patrón? He notado ninguno.

Gracias,
rubik

Answer 1

Esto es más para J. M... no es necesario el uso de ciclo de algoritmos de detección si usted se pega con la reducción de la formas cuadráticas, http://www.numbertheory.org/php/reduce.html para una descripción.

Como escribí en http://mathoverflow.net/questions/22811/upper-bound-of-period-length-of-continued-fraction-representation-of-very-composi/23014#23014 si usted está buscando sólo la reducción de las formas $$ \langle a,b,c \rangle \approx a x^2 + b x y + c y^2, $$ with discriminant $\Delta = b^2 - 4 a c$ positiva, pero no un cuadrado, con $$ 0 < b < \sqrt \Delta $$ y $$ \sqrt \Delta - b < 2 |a| < \sqrt \Delta + b. $$

Edit, April 2015: THEOREM: a form $ \langle a,b,c \rangle$ with discriminant $\Delta = b^2 - 4 a c$ positiva, pero no un cuadrado se REDUCE si y sólo si $$ ac < 0 \; \; \mbox{AND} \; \; \; b > |a+c|. $$

Then, at any given step, find $\delta$ que $$ \delta c > 0 $$ y $$ |\delta| = \left\lfloor \left| \frac{b +\sqrt \Delta}{2 c} \right|\right\rfloor $$ Ahora, el derecho adyacentes formulario de la derecha o vecino, está dada por $$ \langle a,b,c \rangle \rightarrow \langle c, -b + 2 c \delta, a - b \delta + c \delta^2 \rangle. $$ Espuma, enjuague, repita.

Si usted comienza con un reducido formulario de $\langle a_0,b_0,c_0 \rangle$ a continuación, después de un número finito de pasos, llame a $n$ pasos, se obtiene una coincidencia exacta de los tres coeficientes, $$\langle a_n,b_n,c_n \rangle = \langle a_0,b_0,c_0 \rangle$$

An indefinite binary quadratic form, with integer coefficients, corresponds to one of two quadratic irrationals given by the quadratic formula, where we are solving for either $x/y$ or $s/x$ according to taste. As the discriminant is positive and not a square, the roots are real numbers. It turns out that the number defined by the continued fraction (take the absolute values of the $\delta$'s) is not just positive but is larger than 1. Just one of those things.

I noticed in your code for $\sqrt N$ you had it terminate when the first coefficient returned to $\pm 1.$ Thts is not going to work if the reduced form you start with is $\langle 7,3,-7 \rangle$, donde el método exacto que yo describo es dar a la continuación de la fracción de $$ \frac{3 + \sqrt{205}}{14} $$

jagy@phobeusjunior:~/old drive/home/jagy/Cplusplus$ ./indefCycle
Input three coefficients a b c for indef f(x,y)= a x^2 + b x y + c y^2 
7  3  -7

0  form   7 3 -7   delta  -1
1  form   -7 11 3   delta  4
2  form   3 13 -3   delta  -4
3  form   -3 11 7   delta  1
4  form   7 3 -7
minimum was   3rep -1 -1 disc   205 dSqrt 14.317821063  M_Ratio  4.183673
Automorph, written on right of Gram matrix:  
17  21
21  26
 Trace:  43   gcd(a21, a22 - a11, a12) : 3
=========================================
jagy@phobeusjunior:~/old drive/home/jagy/Cplusplus$

To repeat, reduced indefinite integral quadratic form correspond to quadratic irrationals with purely periodic continued fractions. The cycle is complete if and only if the initial reduced form has been repeated. No other cycle detection is required.

The one caution is that, because we are taking the absolute values of the $\delta$'s, es posible para la continuación de la fracción del período a ser exactamente la mitad del período de la forma cuadrática. Por ejemplo,

=========================================
jagy@phobeusjunior:~/old drive/home/jagy/Cplusplus$ ./Pell
Input n for Pell 
61

0  form   1 14 -12   delta  -1
1  form   -12 10 3   delta  4
2  form   3 14 -4   delta  -3
3  form   -4 10 9   delta  1
4  form   9 8 -5   delta  -2
5  form   -5 12 5   delta  2
6  form   5 8 -9   delta  -1
7  form   -9 10 4   delta  3
8  form   4 14 -3   delta  -4
9  form   -3 10 12   delta  1
10  form   12 14 -1   delta  -14
11  form   -1 14 12   delta  1
12  form   12 10 -3   delta  -4
13  form   -3 14 4   delta  3
14  form   4 10 -9   delta  -1
15  form   -9 8 5   delta  2
16  form   5 12 -5   delta  -2
17  form   -5 8 9   delta  1
18  form   9 10 -4   delta  -3
19  form   -4 14 3   delta  4
20  form   3 10 -12   delta  -1
21  form   -12 14 1   delta  14
22  form   1 14 -12

 disc   244
Automorph, written on right of Gram matrix:  
-183241189  1581119536
-226153980  945570387


 Pell automorph 
-1766319049  -910490892
-226153980  -1766319049

Pell unit 
1766319049^2 - 61 * 226153980^2 = 1 

=========================================
jagy@phobeusjunior:~/old drive/home/jagy/Cplusplus$

La de arriba está dando la continuación de la fracción de $$ \frac{7 + \sqrt{61}}{12},$$ Así que creo que estamos consiguiendo siempre el mayor valor de $x/y$ en lugar de $y/x.$ Para su propósito, esta es la correcta, usted está poniendo un 7 en la parte delantera, que utiliza la recíproca de la anterior, para obtener $$ 7 + \; \; \frac{12}{ \sqrt{61} + 7} $$ que funciona a $\sqrt 61$ al racionalizar el denominador.

Por favor, lea el capítulo 3, páginas 21-48, en la Formas Cuadráticas Binarias por Duncan A. Buell, AMAZON

Answer 2

En el caso de $\sqrt n$, es muy fácil de decir cuando has alcanzado el final del periodo; es cuando usted consigue un parcial cociente de dos veces la parte entera. Mira tus ejemplos para $n=2,7,14$; las partes enteras son $1,2,3$, respectivamente, y el final del periodo de $2,4,6$, respectivamente.

Pero si usted no sabe que usted está trabajando con $\sqrt n$; si, por ejemplo, tiene las fracciones continuas para$\sqrt2/\pi$$\pi$, pero tú no lo sabes, no veo cómo vas a saber nunca para asegurarse de que el producto es periódica. Pero seguramente la misma pregunta que surge es si usted tiene el decimal expansiones de $\pi$ $1/\pi$ y usted no lo sabe, ¿cómo puede usted saber nunca para asegurarse de que el producto es $1$?

Answer 3

Una fracción continua termina su período cuando $a_i = 2 * a_0$ ejemplo: $\sqrt{23} = [4;1,3,1,8]$ => $8 = 2* 4$

¿O estoy yo mal entendido la pregunta?

Answer 4

Puede sonar un poco trivial, pero en realidad, lo importante qustion sería: Cuando se tiene una fracción de un período, es decir, cuando hay repetitivo bahvior en los dígitos. Se sabe que los números irracionales no son de terminación, no periódicos las fracciones decimales. Mediante una sencilla configuración de la teoría, es decir, tomando el complemento del conjunto de los números irracionales en el conjunto de los números reales, nos encontramos con que, cualquiera de los números racionales son la terminación de las fracciones decimales periódicas o fracciones. En cualquier caso, por la construcción de los números racionales, es posible encontrar una expresión como esta: $q=\dfrac{n}{m}, n\in\mathbb{Z}, m\in\mathbb{N}$. Tenga en cuenta que esta expresión no tiene por qué ser única!. Por lo tanto, después de haber añadido $m$ multiplicado por el número de $q$ estamos hecho. Hasta el momento acerca de la teoría. Mi experiencia me ha dicho que estas preguntas son las prácticas, es decir, aquellos de poca matemáticos de interés (b.t.w.: Yo soy un puro matemático de trabajo en el análisis global, longitudinal entre la topología y la geometría diferencial < \begin{matrix}13 & 31 & 28 & 67\\ 11 & 27 2& 8 & 20 \endmás Pura de las matemáticas, aparte de la lógica). Creo que numéricamente uno podría encontrar la respuesta a su problema, pero en general, usted tendrá que atenerse a adivinar y comprobar. Pero tal vez cuando usted aprende resumen de álgebra y teoría de números combinados con la lógica, se ha encontrado alguna solución (he escuchado álgebra abstracta en la versión abreviada de los geómetras :D)