Processing math: 100%

19 votos

Una curiosa secuencia de racionales: finito o infinito?

Considere la siguiente función se aplica repetidamente a un racional r=a/b en términos mínimos: f(a/b)=(ab)/(a+b1). 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,,10, pero, por ejemplo, f(4/13)=f(13/4) es finito. Varios ejemplos se muestran a continuación.


1kkk=1

37219=73219=73

512\a6016=154\a6018=103\a3012=52\a106=53\a157\a10521=51\a55=1

523\a11527\a3105141=103547\a486451081=4511

411\a4414=227\a15428=112\a2212=116\a6616=338\a26440=335\a16537\a?


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!

6voto

spambas Puntos 29

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=(m2m+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 ab=n+dn+d donde n>0, dd=n(n1), 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+b1=ab, que puede ser reescrita como (a1)(b1)=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)1 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+b1)=n, entonces tenemos que tener en ab=nk e a+b1=k para algunos entero k. Escrito b=nk/a, acabamos con a2(k+1)a+nk=0, por lo que

a=k+1±(k+1)24nk2.

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

(k+1)24nk=m2,

la cual puede escribirse como

(k+12n)2m2=4n(n1),

o

(k+12n+m)(k+12nm)=4n(n1).

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+12n+m=2d e k+12nm=2d donde dd=n(n1). De esto podemos obtener k+12n=d+d e m=dd, por lo que

a=2c+d+d±(dd)2.

Elegir el signo positivo da a=n+d. (Eligiendo el signo negativo da b=n+d. Si te gusta, puede suponer ab e dd.)

Para hacer sólo un ejemplo, vamos a n=16. Las opciones para dd son 2401, 803, 485, y 1615, lo que en los cuatro posibilidades para que las a/b (con a>b) para que f(a/b)=16:

ab=25617,9619,6421,3231.

Nota cómo la factorización como dd=640 falla:

f((16+6)/(16+40))=f(22/56)=f(11/28)=112838=15419.

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 nm y (n,m)=1. A continuación, f(a/b)=n/m si y sólo si

ab=n+dn+d

donde dd=n(nm) 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=m2m+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(nm)=28, por lo que la posible factorizations son 281, 142, y 74. Pero sólo uno de estos para que (7+d,7+d)=3 es 142, 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(134) para que (13+d,13+d)=4 es 393, dando a/b=52/16=13/4.

Pero n/m=21/5, por último, es interesante: Hay dos factorizations que el trabajo, es decir, 844 e 2414. 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(97)=18 are 181, 92, and 63, 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(nm)=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(nm). 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).

3voto

dpDesignz Puntos 121

Todas las fracciones a/b con a=b(b1)+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(f(1n))=f(1)=1

f(f((n1)2n2))=f(n(n1)2)=1

f(f(2n12n))=f(n)=1

f(f(n+1n2))=f(n)=1

f(f(3(2n+1)4(3n+1)))=f(4n+2)=1

Si en un principio no se mucho de cancelación ocurre durante la iteración y ab,, a continuación,f(n)(a/b) crece superexponential, probablemente cerca de aϕn1 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.

3voto

Robert Claypool Puntos 136

[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 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);}

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X