Una curiosa secuencia de racionales: finito o infinito?

Question

Considere la siguiente función se aplica repetidamente a un racional $r = a/b$ en términos mínimos: $f(a/b) = (a b) / (a + b - 1)$. Así, $f(2/3) = 6/4 = 3/2$. $f(3/2) = 6/4 = 3/2$.

Me pregunto si es posible predecir cuando la secuencia es finito, y cuando infinita. Por ejemplo, $f(k/11)$ parece infinita para $k=2,\ldots,10$, pero, por ejemplo, $f(4/13)=f(13/4)$ es finito. Varios ejemplos se muestran a continuación.

---

$$\frac{1}{k} \to \frac{k}{k} {=} 1$$

$$\frac{3}{7} \to \frac{21}{9} {=} \frac{7}{3} \to \frac{21}{9} {=} \frac{7}{3}$$

$$\frac{5}{12} \a \frac{60}{16} {=} \frac{15}{4} \a \frac{60}{18} {=} \frac{10}{3} \a \frac{30}{12} {=} \frac{5}{2} \a \frac{10}{6} {=} \frac{5}{3} \a \frac{15}{7} \a \frac{105}{21} {=} \frac{5}{1} \a \frac{5}{5} = 1$$

$$\frac{5}{23} \a \frac{115}{27} \a \frac{3105}{141} {=} \frac{1035}{47} \a \frac{48645}{1081} = \frac{45}{1} \to 1$$

$$\frac{4}{11} \a \frac{44}{14} {=} \frac{22}{7} \a \frac{154}{28} {=} \frac{11}{2} \a \frac{22}{12} {=} \frac{11}{6} \a \frac{66}{16} {=} \frac{33}{8} \a \frac{264}{40} {=} \frac{33}{5} \a \frac{165}{37} \a \cdots \to \infty ?$$

---

Yo estoy esperando que este no se ejecuta en Collatz-como dificultades, pero lo hace parecer sencillo para analizar... Si alguien la reconoce, o ve una manera de domesticar ni siquiera parcialmente, yo estaría interesado en aprender. Gracias!

Answer 1

Nota: he anexado algún material adicional que se extiende el análisis de, en efecto, la pre-imágenes de la pre-imágenes del punto fijo $n/m=1$ de la función de $f$, para mirar general pre-imágenes y pre-imágenes de otros puntos fijos (es decir, $n/m = (m^2-m+1)/m$ para $m>1$. El nuevo material sigue una negrita ", Agregó más tarde." Final de la nota

Las familias Karl Fabian encontrado puede ser subsumido bajo una sola regla:

$f^{(2)}(a/b)=1$ si y sólo si $${a\over b}={n+d\over n+d'}$$ donde $n>0$, $dd'=n(n-1)$, e $(n+d,n+d')=1$.

No es difícil mostrar que si $a/b$ tiene la forma dada, a continuación,$f(a/b)=n$, y es fácil demostrar que los $f(n)=f(n/1)=1$. (La suposición de que $n+d$ e $n+d'$ son relativamente primos es crucial.) La parte difícil es muestra de que nada más llega a $1$ en dos pasos.

Es claro que $f(a/b)=1$ si y sólo si $a+b-1=ab$, que puede ser reescrita como $(a-1)(b-1)=0$, por lo que los únicos números que llegan a $1$ en un solo paso son enteros $n$ y sus recíprocos $1/n$. También es claro que $f(a/b)\ge1$ para todos los $a/b$. Por lo tanto, los números que llegan a $1$ en dos pasos son aquellos que llegan a un número entero $n$ en un solo paso. Vamos a ver cómo eso puede suceder.

Si $ab/(a+b-1)=n$, entonces tenemos que tener en $ab=nk$ e $a+b-1=k$ para algunos entero $k$. Escrito $b=nk/a$, acabamos con $a^2-(k+1)a+nk=0$, por lo que

$$a={k+1\pm\sqrt{(k+1)^2-4nk}\over2}.$$

Para $a$ a ser un número entero, debemos tener una plaza dentro de la raíz cuadrada:

$$(k+1)^2-4nk = m^2,$$

la cual puede escribirse como

$$(k+1-2n)^2-m^2 = 4n(n-1),$$

o

$$(k+1-2n+m)(k+1-2n-m)=4n(n-1).$$

Los dos términos en el lado izquierdo tiene la misma paridad (se diferencian por $2m$), por lo tanto ambas deben ser parejos, es decir, $k+1-2n+m=2d$ e $k+1-2n-m=2d'$ donde $dd'=n(n-1)$. De esto podemos obtener $k+1-2n=d+d'$ e $m=d-d'$, por lo que

$$a={2c+d+d'\pm(d-d')\over2}.$$

Elegir el signo positivo da $a=n+d$. (Eligiendo el signo negativo da $b=n+d'$. Si te gusta, puede suponer $a\ge b$ e $d\ge d'$.)

Para hacer sólo un ejemplo, vamos a $n=16$. Las opciones para $dd'$ son $240\cdot1$, $80\cdot3$, $48\cdot5$, y $16\cdot15$, lo que en los cuatro posibilidades para que las $a/b$ (con $a>b$) para que $f(a/b)=16$:

$${a\over b} = {256\over 17}, {96\over19}, {64\over21}, {32\over31}.$$

Nota cómo la factorización como $dd'=6\cdot40$ falla:

$$f((16+6)/(16+40)) = f(22/56)=f(11/28)= {11\cdot28\over38}={154\over19}.$$

Añadido posterior: Si lo he hecho todo correctamente, un análisis similar se da la siguiente buen resultado sobre pre-imágenes:

Deje $n/m$ ser una fracción con $n\ge m$ y $(n,m)=1$. A continuación, $f(a/b)=n/m$ si y sólo si

$${a\over b} = {n+d\over n+d'}$$

donde $dd'=n(n-m)$ e $(n+d,n+d')=m$.

Vamos a ver cómo esto se aplica a los otros puntos fijos para $f$, es decir, cuando se $n=m^2-m+1$, para los primeros valores de $m$.

Saltarse el caso de $m=1$ (que se puede consultar da el resultado se señaló anteriormente), vamos a $n/m = 3/2$, por lo que necesitamos $dd'=3$ e $(3+d,3+d')=2$. Los únicos factores son $3$ e $1$, lo que, de hecho, satisfacer $(6,4)=2$, pero esto sólo da $a/b = 6/4=3/2$. En otras palabras, el punto fijo, $3/2$ no tiene pre-imagen distinto de sí mismo.

Para $n/m=7/3$, tenemos $n(n-m)=28$, por lo que la posible factorizations son $28\cdot1$, $14\cdot2$, y $7\cdot4$. Pero sólo uno de estos para que $(7+d,7+d')=3$ es $14\cdot2$, lo que da $a/b = 21/9 = 7/3$, lo $7/3$ también no tiene pre-imagen distinto de sí mismo.

Se puede comprobar que lo mismo sucede con $n/m = 13/4$: La única factorización $dd'$ de % de $13(13-4)$ para que $(13+d,13+d')=4$ es $39\cdot3$, dando $a/b=52/16 = 13/4$.

Pero $n/m = 21/5$, por último, es interesante: Hay dos factorizations que el trabajo, es decir, $84\cdot4$ e $24\cdot14$. La primera, como antes, le da el punto fijo de nuevo, $$a/b = (21+84)/(21+4) = 105/25 = 21/5.$$ But the other one gives $$a/b = (21+24)/(21+14) = 45/35 = 9/7.$$ Note, however, that $9/7$ has no pre-image: The factorizations of $9(9-7)=18$ are $18\cdot1$, $9\cdot2$, and $6\cdot3$, none of which produce anything divisible by $7$, much less a pair $(9+d,9+d')$ with $7$ como un divisor común.

En resumen (por ahora), la única fracción con un número infinito de pre-imágenes es $n/m=1$ (desde $n(n-m)=0$ tiene infinitamente muchos divisor pares!); el tamaño de la pre-imagen de conjunto para todas las otras fracciones que está limitada por el número de divisor pares de $n(n-m)$. Para algunos de los puntos fijos de $f$, la pre-imagen de conjunto es sólo el punto fijo de sí mismo, mientras que para otros (por ejemplo,$n/m = 21/5$), la pre-conjunto de imágenes contiene los puntos adicionales. Puede haber algo de criterio simple que identifica los puntos fijos que no tengan adicionales de pre-imágenes, pero yo no improviso ver uno, posiblemente porque no he pensado nunca dura lo suficiente (pero tal vez porque estoy ciego a lo obvio).

Answer 2

Todas las fracciones $a/b$ con $a = b(b-1)+1$ son puntos fijos porque, a continuación,$(a,b)=1$. Por otra parte, todas las soluciones a $f^{(2)}(r)=1$ me encontrado hasta el momento proceden de una de estas familias: $$f\left(f\left(\frac{1}{n}\right)\right)=f\left(1\right)=1$$

$$f\left(f\left(\frac{(n-1)^2}{n^2}\right)\right)=f\left(\frac{n(n-1)}{2}\right)=1$$

$$f\left(f\left(\frac{2n-1}{2n}\right)\right)=f\left(n\right)=1$$

$$f\left(f\left(\frac{n+1}{n^2}\right)\right)=f\left(n\right)=1$$

$$f\left(f\left(\frac{3(2n+1)}{4(3n+1)}\right)\right)=f\left(4n+2\right)=1$$

Si en un principio no se mucho de cancelación ocurre durante la iteración y $a\approx b$,, a continuación,$f^{(n)}(a/b)$ crece superexponential, probablemente cerca de $a^{\phi^{n-1}}$ que hace sustancial de la cancelación de más y más raro, sobre todo que el numerador finalmente golpea por casualidad un perfecto múltiplo del denominador.

Answer 3

[actualización] Upp, después de la publicación de este veo, que Barry ha hecho algo similar con el término "preimagen". Creo que en la lista de/árbol debajo de la pena de todos modos... [endupdate]

Me acerqué a el problema desde el lado de la inversión del mapa; comenzando a las $1/1$ entonces debe ocurrir un árbol infinito. El grado de libertad es tomado por la cancelación de los factores comunes en el numerador y el denominador, lo que significa que la elección (aunque de alguna manera restringido) de un factor común $g$ en el invertida mapa. No es fácil para optimizar el procedimiento; primero uno tiene que encontrar un mínimo factor de $g$, lo que permite a todos para calcular uno válido paso por la inversa (por la construcción de una solución mínima entero squareroot) y, a continuación, para encontrar posteriores soluciones. He utilizado hasta ahora la fuerza bruta para el primer par de intentos.
Por la descripción me ha resuelto la fracción racional en un 2-vector componente, en lugar de $\frac ab$, uso $[a,b]$ como parámetro y como resultado.

Aquí está un breve handplanted árbol, comenzando a las $[1,1]$. De $[1,1]$ que puede llegar en cualquier$[k,1]$ por algún factor común $g$ esto es indicado por $[k,1]$ en el árbol de abajo.

Entonces comienzo a $[2,1]$ hay un subárbol, donde los hermanos de un mismo nivel son siempre en la misma columna. Por ejemplo, $[2,1]$ tiene sólo un niño $[4,3]$, esto tiene un hijo a $[2,2]$ y este tiene un número infinito de childs $[2k,1]$.

Después de eso, comencé con $[3,1]$, y así sucesivamente, con la obvia esquema.

Nos encontramos con algunas común "nodos", por ejemplo,$[4,3]$, que se producen en las diferentes generaciones de niños, y también "inmediata ciclos", por ejemplo) $[3,2]$

Sorprendentemente hay un montón de callejones sin salida, $[6,5]$,$[8,7]$ y así sucesivamente.
Si te gusta jugar con él, un crudo ejemplo de código para Pari/GP es el final.

 [1,1] 
    --> [k,1]

 [2,1]
   [4,3]
     [2,2]
        --> [2k,1]

 [3,1]
   [6,5]
   [9,4]
     [6,3]
       [4,3]  (... common node)


 [4,1]
   [8,7]
   [10,6]
     [5,2]
       [5,4]
       [10,3]
         [8,5]
           [4,2]
             [4,3]   (... common node)
         [15,4]
           [12,5]
              [8,3]
                [6,4]
                  [3,2]  (!!cycle)
                [16,3]
                  [14,8]
                     [7,2]
                       (???)
                  [40,6]
           [45,4]
   [16,5]

---

\\ The original map
T(v,h=1)=local(a,b);for(k=1,h,a=v[1]*v[2];b=v[1]+v[2]-1;v=[a,b]/gcd(a,b));v

\\The inverse map
{TI(v,maxg=2000,maxj=20)=local(a,b,j=0,x,y);
 list=vectorv(maxj);    \\ list to establish the branch of siblings
 for(g=1,maxg,          \\ test all successive assumed common factors g up to maxg
   a = v[1]*g;b=v[2]*g;
   t1 =  (b+1)^2 - 4*a;
   if(t1<0,next());
   t1=sqrt(t1);
   if(t1<>floor(t1),next());   \\ t1 must be an integer squareroot
   x = bestappr(((b+1)+ t1)/2,1e12) ;
   y = bestappr(((b+1)- t1)/2,1e12) ;
   j++; if(j>maxj,break());   \\ length of sibling-list at most 20
   list[j]=[x,y,g];
  );
  if(j==0,return(Mat([0,0,0])));   \\ we have a dead-end in our argument v
  list=VE(list,j);    \\ shorten the list to the length of actually found siblings
 return(Mat(list))   }


{TIrek(v,level=0)=local(tmp);
 tmp = TI(v); 
 for(r=1,rows(tmp),
    print(level,"   ", tmp[r,]);
     if(level<5 & tmp[r,1]<>0, TIrek([tmp[r,1],tmp[r,2]],level+1));
    );
 return(0);}