Extraña (o estúpida) derivación aritmética

Question

Consideremos la siguiente operación sobre enteros positivos: $$n=\prod_{i=1}^{k}p_i^{\alpha_i} \qquad f(n):= \prod_{i=1}^{k}\alpha_ip_i^{\alpha_i-1}$$ (Is it true that if we apply this operation to any integer multilpe times, it will eventually get into a finite cycle?) Is there a constant $K$ such that any integer will fall into a cycle after $K$ pasos?

Edit4: Hemos logrado resolver afirmativamente a la pregunta de Marca Sapir, si un ciclo de longitud arbitraria existe: http://www.math.bme.hu/~kovacsi/Pub/arithmetic_derivation_v04.pdf

Edit3: he propuesto dos preguntas (en retrospectiva, fue un pequeño error), uno de ellos fue respondida. Para apreciar esto, he de aceptar la Marca de Sapir la respuesta, y alterar el texto original poniendo las cosas sin respuesta en paréntesis. Haciendo que el respondió uno de los principales pregunta.

Edit2: István Kovács señaló que no es una buena fórmula para $f(n)$ utilizando el número de divisores de función: $$ f(n):= d \left( \frac{n}{ \prod_{i=1}^{n}p_i } \right) \frac{n}{ \prod_{i=1}^{n}p_i } $$ from which it fillows that for any $\varepsilon >0 , \quad f(n)=o(n^{1+\varepsilon})$.

Creo que la respuesta a la primera pregunta es sí, pero a la segunda no. Hemos probado la primera $10000$ enteros y cada entero cayó en un ciclo después de que en la mayoría de las $6$ pasos.

Edit: @MarkSapir demostrado que la respuesta a la segunda pregunta es no. Su prueba se plantea la (tercera) pregunta: ¿cuánto tiempo puede un ciclo de ser?

Answer 1

Voy a mostrar que la respuesta a la segunda pregunta es "no". Tenga en cuenta que si la respuesta a la primera pregunta es "no", hemos terminado. Por tanto, asumir que la respuesta es "sí" y para cada número $n$, la cadena se convierte finalmente en un ciclo. Tomar cualquier número $n$ y considerar la posibilidad de una secuencia de números de $n, f(n)(n-1), f(f(n)(n-1))(n-2),...$, que es $a_1=n, a_{m+1}=f(a_m)(n-m)$, para cada $m=1,...,n-1$. Deje $A=a_n$. Deje $p$ ser un primo que es mayor que cualquier número que se produce en la cadena de $A$. Considere la posibilidad de $p^n$. Entonces, la cadena de $p^n$ se parece a $p^n\to a_1p^{n-1}\to ...\to a_n\to...$ y la cadena de $A=a_n$ sigue. Que la cadena nunca llegará a la primera $n$ de los números en la cadena de $p^n$, por lo tanto la cadena de $p^n$ no entra en un ciclo antes de que el paso número $n$. Desde $n$ fue arbitraria, hemos terminado. Esto responde a la segunda pregunta. La primera pregunta parece más difícil.

Edit. Como @DanielSoltész señalado, me contestó una difícil pregunta acerca de la delimitación de la longitud de ciclo en la cadena de $m\to f(m)\to\ldots$. Si queremos demostrar que no es obligado por el número de diferentes elementos en una cadena, entonces asumiendo $p>n^{2^n-1}$ es suficiente. Esto nos lleva a otra pregunta razonable acerca de la delimitación de la longitud de los ciclos de $m\to...\to m$. Esta pregunta es abierta.

Answer 2

Mientras trabajaba en la primera pregunta, logré obtener otra solución para la segunda, diferente de la de Mark. Considere el producto formal:$$P_0=\prod_{p_i \, prime} p_{i}^{p_i}.$$ Note that it is the fixed point of the formal derivation. Then the formal derivative of $ 2P_0$ is $ f (2P_0) = 3P_0$. In general it is true that $ f ^ {(k)} (2P_0) = c_k f ^ {(k- 1)} (2P_0)$ for a $ c_k> 1$. Indeed as every exponent is at least as big as its base. Thus lets formally derive $ 2P_0$, k-times. Then there are only finitely many primes which had their exponents changed during the process. Removing every other prime from $ 2P_0$ we obtain a finite product which has its first $ k $ derivados estrictamente crecientes.

Answer 3

Hice algunos cálculos con los números enteros hasta 400000 y llegué a las siguientes conclusiones:

1) Los siguientes son los ciclos con más de un elemento (es decir, sin puntos fijos)

• [32,80]=[2⁵, 2⁴·5]
• [864,2160]=[2⁵·33, 2⁴·33·5]
• [708588,2598156,787320]=[22·311, 22·31⁰·11, 23·3⁹·5]
• [5832,17496,61236,20412]=[23·3⁶, 23·3⁷, 22·3⁷·7, 22·3⁶·7]

2) Todos los números enteros de hasta 400000 terminan cayendo en un punto fijo o uno de los ciclos anteriores (o, tal vez, otra 2-ciclo que me he perdido), excepto para $2^{16}$, $2^{17}$, $2^{16}\cdot 3$, $2^{16}\cdot 5$, $2^{18}$, $2^{17}\cdot 3$, $2^{12}\cdot 3^4$, $2^4\cdot 3^9$, $2^9\cdot 3^6$.

Estos valores excepcionales acaban de llegar a algún número que mi ordenador no puede manejar. Como un ejemplo de los primeros seis valores excepcionales (todos aquellos con los que el exponente de 2 es más grande o igual a 16) llevar a $2^{18}\cdot 3^5$, que después de más de 10 pasos o así calculada por la mano sigue aumentando y no parece caer en un ciclo de pronto. Esto está de acuerdo con Felipe el comentario.

3) he encontrado todo lo anterior, usando la mala programación: he calculado los números reales en lugar de seguir la pista de los números primos y exponentes como se hace con la mano. La reprogramación de todo el uso de esta idea debe dar resultados mucho mejores.

Anexo 1: Estudio de caso de $2^{16}$ me podría encontrar algo más de 2 ciclos, tales como

• $[2^{63}\cdot 3^{13}\cdot 7\cdot 31,2^{62}\cdot 3^{14}\cdot 7\cdot 13]$ ($2^{16}$ llega este 2-ciclo después de 33 pasos).
• $[2^{279}\cdot 3^{61}\cdot 31\cdot 139,2^{278}\cdot 3^{62}\cdot 31\cdot 61]$
• $[2^{15}\cdot 3^{33}\cdot 7\cdot 17,2^{14}\cdot 3^{34}\cdot 5\cdot 11]$

El término izquierda de todos ellos es de la forma $2^{2p+1}\cdot 3^{2q-1}\cdot p\cdot q$ con $(2p+1)(2q-1)=9\cdot c$ donde $p,q$ son primos diferentes de $2,3$ e $c$ es una plaza libre entero coprime con $2,3$. Más en general, tenemos los siguientes.

Deje $p,q,r,s$ ser pares distintos de los números primos tales que $(pr+1)(ps-1)=q^2\cdot c$ donde $c$ es una plaza libre entero coprime con $p,q$. A continuación, $[p^{pr}\cdot q^{ps}\cdot c,p^{pr+1}\cdot q^{ps-1}\cdot r\cdot s]$ es $2$-ciclo de $f$.

N. B.: Si $r,s\neq 2$, la hipótesis de la fuerza, ya sea $p=2$ o $q=2$. Por lo que un resultado mucho más fácil es:

Deje $p>2,3$ ser un primo tal que $2p=3c+1$ donde $c$ es una plaza libre entero coprime con $3$. A continuación, $[2^3\cdot 3^{2p-1}\cdot p,2^2\cdot 3^{2p}\cdot c]$ es $2$-ciclo de $f$.

E. g. $p=11,17,29,47,53$ hacer el truco.

Anexo 2: ya he codificado todo correctamente (por favor, dígame si usted está interesado en el código). En este momento estoy buscando ciclos tan largos como sea posible. Si se encuentra fuera de 5 ciclos y 6 ciclos: por ejemplo 22·3⁴⁷·5⁶ es el comienzo de un 5-ciclo y 2⁶⁷·31⁰⁵·5⁵·53·67 es el comienzo de un 6-ciclo. Naturalmente uno se pregunta si hay ciclos de longitud arbitraria y cómo encontrarlos. Sería bueno encontrar una propuesta de ampliación de la uno me dio en la Adición 1 $f^k$ arbitrarias $k$.

Anexo 3: obtuve resultados similares para $k=4$:

Deje $p>2,3$ ser un primo tal que $6p+1$ es una plaza libre entero. A continuación, $[2^3\cdot 3^{6p}\cdot p, 2^3\cdot 3^{6p+1}\cdot p, 2^2\cdot 3^{6p+1}\cdot (6p+1),2^2\cdot 3^{6p}\cdot(6p+1)]$ es $4$-ciclo de $f$.

Todos los números primos entre 5 y 97 satisfacen las condiciones de esta proposición, excepto para los días 29 y 79.

Deje $p>2,3$ ser un primo tal que $p-1=6c$ para una plaza libre entero $c$. A continuación, $[2^2\cdot 3^p\cdot p, 2^2\cdot 3^{p-1}\cdot p, 2^3\cdot 3^{p-1}\cdot c, 2^3\cdot 3^p\cdot c]$ es $4$-ciclo de $f$.

Algunos de los números primos que cumplen las condiciones son 31, 43, 67 y 79.

Answer 4

He aquí una observación elemental inspirado por Felipe perspicaz comentario.

Vamos a atacar a una versión más simple de este problema y tratar de ingeniero de ciclos largos, cuando el punto de partida es $n = p^{k_0}$ para algunos $k_0 > 1$. Comenzando con un $n$, podemos ver inmediatamente que $f(n) = k_0p^{k_0-1}$, por lo que tratamos de establecer algún tipo de control sobre los factores primos de $k_0$. En el fin de mantener las cosas tan simples como sea posible, puede que se desee $k_0$ para volver a ser una potencia de $p$, decir $k_0 = p^{k_1}$ lo que nos deja con $f(n) = p^{k_1 + k_0 -1}$. Tan largo como $k_1 > 1$, se nos garantiza $f(n) \neq n$.

Procediendo de esta manera, parece como si estamos después de una secuencia $k_j$ de los enteros que satisfacen la siguiente propiedad: denota las sumas parciales como $K_j = \sum_{0 \leq i < j}k_j$, queremos $$k_j = p^{K_j - j}.$$

Con el fin de asegurar un ciclo de longitud $L+1$, queremos un contiguos subsequence $k_j, \ldots , k_{j+L}$, de modo que el conjunto de cambios en las sumas parciales $$\{K_{j+i} - (j+i) \mid 0 \leq i \leq L\}$$ tiene cardinalidad $L+1$. No estoy seguro de cómo uno va sobre la búsqueda de una secuencia $k_j$, pero esperemos que no son la teoría del número de asistentes que no saben esas cosas...