¿Qué sucede cuando nos (mal) hacer fracciones impropias correcto de nuevo?

Question

Muchas personas evitar el "número mixto" notación como $4\frac{2}{3}$ debido a su ambigüedad. El ejemplo podría significar "$4$ y dos tercios", es decir, $4+\frac{2}{3}$, pero también se puede tener la tentación de multiplicar, lo que resulta en $\frac{8}{3}$.

Mi pregunta es con respecto a lo que sucede cuando repetimos este proceso -- alternando entre el cambio de una fracción a un número mixto, a continuación, "incorrectamente" multiplicar el mixto la fracción. La iteración termina cuando se llega a una adecuada fracción (numerador $\leq$ denominador) o un número entero. Voy a "definir" este proceso a través suficientemente complicada ejemplo:

$$\frac{14}{3} \rightarrow 4 \frac{2}{3} \rightarrow \frac{8}{3} \rightarrow 2 \frac{2}{3} \rightarrow \frac{4}{3} \rightarrow 1\frac{1}{3}\rightarrow \frac{1}{3}.$$

1. ¿Este proceso de terminar siempre?

2. Para que $(p,q)\in\mathbb{N}\times(\mathbb{N}\setminus\{0\})$ hace este proceso, con la inicial recorrer $\frac{p}{q}$, terminar en $\frac{p \mod q}{q}$?

Answer 1

Sí, el proceso no siempre terminar.

He aquí por qué:

Considerar el número mixto $a\frac{b}{c}$, donde $0 \le b < c$ e $a > 0$. Entonces, es claro que $ab < ac+b$, y así el proceso continúa para llevar a los más pequeños y pequeñas fracciones con el mismo denominador $c$ hasta el numerador por último se hace menor que $c$.

En caso de una negativa de número mixto $-a\frac{b}{c}$, recuerde que esto significa "$-(a+\frac{b}{c})$", no "$(-a)+\frac{b}{c}$". Pero uno puede fácilmente omitir el signo negativo, por lo que sin pérdida de generalidad, se puede considerar positivo mixto de sólo números.

Answer 2

La fórmula dada por R. Burton, en un comentario es muy útil para el análisis de este problema. Tenemos la siguiente iteración de la función, donde $\lfloor x \rfloor$ es la función del suelo: $$ f(x) = \lfloor x \rfloor(x-\lfloor x \rfloor) $$ Tenemos una secuencia de varias ocasiones la aplicación de esta función hasta que se $a_n$ es un número entero o $0 < a_n < 1$. $$ \begin{array}{rcl} a_0 &=&\frac{p}{q} \\ a_{n+1} &=& f(a_n) \end{array} $$ Tenga en cuenta que nos pueden tomar un valor de $a_0$ que no es un número racional, pero cualquier número real positivo. Creo que esta generalización hace que el problema sea más fácil, porque nos puede olvidarse de los numeradores y denominadores.

Este es el argumento de $f$:

Se puede ver que, por ejemplo, si $4 < x < 5$, a continuación, $0 < f(x) < 4$.

Si decimos que el área entre dos adyacentes enteros en el eje x de una columna, entonces se puede decir que con cada solicitud de $f$, el valor de $a_n$ se desplaza al menos una columna a la izquierda. O, en una fórmula, $\lfloor a_{n+1} \rfloor < \lfloor a_n \rfloor$.

Pero, por supuesto, $a_n$ nunca es negativo, por lo que este proceso debe terminar.

Problema 2

Deje $f^*$ ser la función de $f$ repite hasta que el resultado es un número entero o entre 0 y 1. Donde $f^*$ es continua, su gráfica se parece a esto, las líneas de 0 a 1 directamente uno al lado del otro:

La vertical de líneas grises indican donde $f^*$ es discontinuo y tiene un valor entero positivo. (el valor no es visible en la gráfica.) Las posiciones de las líneas verticales que se puede calcular con la siguiente relación de recurrencia. El conjunto $L_i$ contiene todas las discontinuidades de $f^*$ a $i$ e ha $2^{i-1}$elementos. $$ \begin{array}{rcl} L_1 &=& \{1\} \\ L_{i+1} &=& L_i\ \cup\ \{i + \frac{k}{i}\ |\ k \in L_i\} \end{array} $$ Para dibujar el diagrama que se utiliza $L_7$, que es igual a $$ \left\{1,2,\frac{5}{2},3,\frac{10}{3},\frac{11}{3},\frac{23}{6},4,\frac{17}{4},\frac{9}{2},\frac{37}{8},\frac{19}{4},\frac{29}{6},\frac{59}{12},\frac{119}{24},5,\frac{26}{5},\frac{27}{5},\frac{11}{2},\frac{28}{5},\frac{17}{3},\frac{86}{15},\frac{173}{30},\frac{29}{5},\frac{117}{20},\frac{59}{10},\frac{237}{40},\frac{119}{20},\frac{179}{30},\frac{359}{60},\frac{719}{120},6,\frac{37}{6},\frac{19}{3},\frac{77}{12},\frac{13}{2},\frac{59}{9},\frac{119}{18},\frac{239}{36},\frac{20}{3},\frac{161}{24},\frac{27}{4},\frac{325}{48},\frac{163}{24},\frac{245}{36},\frac{491}{72},\frac{983}{144},\frac{41}{6},\frac{103}{15},\frac{69}{10},\frac{83}{12},\frac{104}{15},\frac{125}{18},\frac{313}{45},\frac{1253}{180},\frac{209}{30},\frac{279}{40},\frac{419}{60},\frac{559}{80},\frac{839}{120},\frac{1259}{180},\frac{2519}{360},\frac{5039}{720},7\right\}. $$

The corresponding Mathematica code is: (Wolfram Alpha)

Fold[Join[#1, #2 + #1/#2] &, {1}, Range[6]]

Let $x = \frac{p}{q}$ ser un número positivo, entonces tenemos $$ f^* \left( \frac{p}{q} \right) = \frac{p \mod p}{q}\quad \ffi \quad f^*(x) = x - \lfloor x \rfloor. $$ Si nos basamos $x - \lfloor x \rfloor$ en la parte superior de $f^*(x)$, obtenemos esta imagen:

La ecuación de $f^*(x) = x - \lfloor x \rfloor$ es verdad que el azul y el naranja líneas se superponen o cruz, a excepción de los números enteros positivos, donde es falso debido a que el lado derecho es $0$.

Podemos ver que la ecuación tiene por $0 \le x < 1$ e $1 < x < 2$. Es cierto, también, en un punto en cada línea azul que no se inicia o termina en un número entero. Así que para cada entero $n \ge 2$hay $|L_{n+1}| - |L_n| - 2 = 2^{n-1}-2$ puntos entre $n$ e $n+1$ para que la ecuación es verdadera.

Para obtener las coordenadas de los puntos, tenemos que equiparar una línea azul con una línea naranja. Deje $a$ e $b$ ser los valores de los dos adyacentes no entero puntos de discontinuidad, por ejemplo, $a = \frac{10}{3}$ e $b = \frac{11}{3}$ para obtener el primer punto. Entonces las ecuaciones para el azul y el naranja de las líneas son: $$ \begin{array}{rcl} l_b(x) &=& \frac{x - a}{b - a} \\ l_o(x) &=& x - \lfloor a \rfloor \end{array} $$ La solución de $l_b(x) = l_o(x)$ nos da: $$ x = \frac{a + \lfloor un \rfloor(a - b)}{1 + a - b} $$ En Mathematica podemos utilizar este código para la salida de todos los números entre 2 y 7 para que la ecuación se tiene:

x[a_, b_] := (a + Floor[a](a - b)) / (1 + a - b);
list = Fold[Join[#1, #2 + #1/#2] &, {1}, Range[6]];
intervals = Select[Partition[list, 2, 1], NoneTrue[#, IntegerQ] &];
points = x @@ # & /@ intervals

Esto nos da $$ \left\{\frac{7}{2},\frac{19}{5},\frac{13}{3},\frac{32}{7},\frac{33}{7},\frac{53}{11},\frac{54}{11},\frac{114}{23},\frac{21}{4},\frac{49}{9},\frac{50}{9},\frac{79}{14},\frac{40}{7},\frac{167}{29},\frac{168}{29},\frac{111}{19},\frac{112}{19},\frac{77}{13},\frac{232}{39},\frac{352}{59},\frac{353}{59},\frac{713}{119},\frac{31}{5},\frac{70}{11},\frac{71}{11},\frac{111}{17},\frac{112}{17},\frac{232}{35},\frac{233}{35},\frac{154}{23},\frac{155}{23},\frac{318}{47},\frac{319}{47},\frac{483}{71},\frac{484}{71},\frac{976}{143},\frac{977}{143},\frac{199}{29},\frac{200}{29},\frac{408}{59},\frac{409}{59},\frac{618}{89},\frac{619}{89},\frac{1246}{179},\frac{1247}{179},\frac{830}{119},\frac{831}{119},\frac{1670}{239},\frac{1671}{239},\frac{2511}{359},\frac{2512}{359},\frac{5032}{719}\right\}. $$

Answer 3

Respuesta parcial por 2: si $q = 2$, el proceso terminará en $\frac12$ fib $p = 2^k - 1 \, (k \in \mathbb{N})$ y en un número entero de otra manera. Esto es porque la única manera de terminar con una $1$ en el numerador es por tener una parte entera de $1$ y un numerador de $1$, lo $1\frac12 = \frac32$. La única manera de poner fin a $\frac32$ es de $3\frac12$, etc. No importa que $15 = 3 \cdot 5$, usted no puede tener otra cosa que $1$ en el numerador.

Así que si $q = 2$, el final numerador es, modulo p, igual a la original, $p$ fib $p$ es par o $p = 2^k - 1$.

---

Para otros $q$, es mucho más difícil encontrar una 'fórmula', pero como @isaacg notas, el caso anterior puede ser generalizado a los números de la forma $p_k=\frac{q^k-1}{q-1}$:

$$\frac{q^k-1}{q-1}=\frac{qq^{k-1}-q+q-1}{q-1}=q\frac{q^{k-1}-1}{q-1}+1=qp_{k-1}+1$$

por lo $p_k \equiv 1 \pmod q$, y la fracción impropia $\frac{p_k}{q}$ es igual a $p_{k-1}\frac1q$ que se convierte en $\frac{p_{k-1}}{q}$ en el siguiente paso, y terminamos con $\frac1q$.

Esos no son los únicos casos, por ejemplo, $\frac53 \to 1\frac23 \to \frac23$ es otro de los 'adecuada' (no-entero-final) ejemplo.

Answer 4

1. ¿Este proceso de terminar siempre?

Sí. El proceso descrito es, simplemente, la evaluación de la recurrencia de la relación...

$$a_{n+1}=\lfloor a_n\rfloor(a_n-\lfloor a_n\rfloor);\quad a_0=\frac{p}{q}$$

...donde $\lfloor\cdot\rfloor$ es la función del suelo, mientras que $a_n>0$.

Para demostrar que el proceso termina, es suficiente para mostrar que hay algo de $n$ tal que $a_n=0$.

Una prueba de croquis de la siguiente manera:

Supongo que hay algo de $n$ tal que $a_n$ es un número entero. A continuación, $a_{n+1}=0$ y hemos terminado.

Supongamos que no es $n$ tal que $a_n$ es un número entero. Deje $c=\max\{a_n-\lfloor a_n\rfloor:n\in\Bbb{N}\}$ (tenga en cuenta que $c<1$). De ello se sigue que...

$$a_{n+1}\le\lfloor a_n\rfloor c\le a_nc$$

Debido a $a_{n+1}=a_nc$ ha cerrado el formulario de $a_n=a_0c^n$, sabemos que $a_n\le a_0c^n$. Desde $\lim_{n\to\infty}a_0c^n=0$ e $0\le a_n$ para todos los $n$, se deduce que el $\lim_{n\to\infty}a_n=0$. Por la definición del límite de una secuencia, debe existir $n$ tal que $a_n-0<1$. Deje $k$ ser el menos $n$, a continuación, $a_{k+1}=0$ y hemos terminado.

La convención de empleados @GeoffreyTrang puede ser utilizado para tratar negativo racionales.

2. Para que $(p,q)\in\mathbb{N}\times(\mathbb{N}\setminus\{0\})$ hace este proceso, con la inicial recorrer $\frac{p}{q}$, terminar en $\frac{p \mod q}{q}$?

Es más fácil pensar en los pares para que el proceso no terminará en $\frac{p\mod q}{q}$.

Para empezar, tenga en cuenta deje $h(p,q)$ será el último valor antes de la terminación, como se describió anteriormente. Vale la pena señalar que $h(p,q)=h(np,nq)$ cualquier $n\in\Bbb{Z}^+$ - por lo que sólo es necesario tener en cuenta la proporción entre el $p$ e $q$. Podemos identificar cada uno de esos proporción con una línea a través de $\Bbb{N}\times\Bbb{Z}^+$.

(más)

(ver @Paul 's respuesta para la solución)