6 votos

Prueba o contraejemplo de la conjetura de la convergencia de secuencia

Recientemente me encontré con un número de secuencia se define como:

$$ a_{i} = \begin{cases} N & \text{if } i = 0 \\ S(a_{i-1}) & \text{if } i > 0 \end{casos} $$

Donde:

$$ S(N) = \begin{cases} \sum \text{Prime Factors of N} & \text{if N is composite} \\ N + P_{next} &\text{if N is prime} \end{casos} $$

Y $P_{next}$ se define como el próximo primer después de N. (es decir, Si N es 7, $P_{next}$ es de 11)

Se puede demostrar la secuencia de bucle en:
(N=5): {5, 12, 7, 18, 8, 6, 5, ...}
(N=4): {4, 4, ...}
(N=3): {3, 8, 6, 5, 12, 7, 18, 8, 6, 5, ...}
(N=2): {2, 5, 12, 7, 18, 8, 6, 5, ...}

En aras de la claridad, $\sum \text{Prime Factors of N}$, se refieren a la suma de TODOS los factores primos con respecto a sus multiplicidades. Por ejemplo: S(18) = 8 18 porque es compuesto, y sus factores primos son {2,3,3}. Desde 2 + 3 + 3 = 8, S(18) = 8.

Para$N\geq2$$N\leq10,000,000$, con la excepción de N = 4, todas las secuencias convergen en 5, como se muestra arriba es un bucle de secuencia.

Mi conjetura es que para todos los $N\geq2$, con el excepton de N = 4, la secuencia converge a 5.

Es posible demostrar esta conjetura? O, por el contrario, refutar a través de un contraejemplo?
Como se indicó anteriormente, he probado la conjetura de $2\leq N\leq 10,000,000$.

Gracias de antemano.

2voto

Mike Puntos 1113

Su conjetura es verdadera, y puede ser probada con un poco de teoría de números y algunos de la computación que ya has hecho.

La función que se utiliza en el compuesto-$N$ de los casos, la suma de todos los primos divisores (con multiplicidad) de $N$, es conocido a veces como el número entero de registro o la potencia de $N$; usted puede encontrar más información en https://oeis.org/A001414 . Por comodidad, voy a escribir esto como $\log_{\mathbb N}(n)$ en adelante.

Vamos a tener que demostrar algunas propiedades básicas de $\log_{\mathbb N}$:

  • Para todos $n$, $\log_{\mathbb N}(n)\leq n$. Esto puede ser demostrado por (fuerte) de la inducción: si $n$ es primo, entonces obviamente $\log_{\mathbb N}(n)=n\leq n$. De lo contrario, deje $p$ ser el menor factor primo de $n$; a continuación,$\frac np\geq p$, y así $\log_{\mathbb N}(n)=p+\log_{\mathbb N}(\frac np)$ $\leq p+\frac np$ (por la inducción de paso) $\leq \frac np+\frac np$ (desde $p\leq\frac np$) $=\frac2pn$ $\leq n$ (desde $p\geq 2$).
  • Para todos los compuestos $n\gt 4$, $\log_{\mathbb N}(n)\lt n$ (es decir, la desigualdad es estricta). El argumento es similar: vamos a $p$ ser el menor divisor primo de $n$ y tenga en cuenta que $\log_{\mathbb N}(n)\leq p+\frac np$. Pero ahora, si $p=2$, entonces el lado derecho es $2+\frac n2$, e $2+\frac n2\lt n$$n\gt 4$, lo $\log_{\mathbb N}(n)\lt n$; en caso contrario (es decir, si $p\gt 2$) tenemos a $\log_{\mathbb N}(n) \leq p+\frac np \leq \frac np+\frac np$ (como en el anterior) $=\frac 2pn$ $\lt n$ (desde $p\gt 2$).
  • Por último, un refinamiento adicional: para todos los compuestos de $n\gt 45$, no de la forma $n=2p$ primer $p$,$\log_{\mathbb N}(n)\lt \frac25n$. Sostenemos como antes: en primer lugar, podemos encontrar un divisor $d$$n$$3\leq d\leq\frac nd$. (Si $4|n$, a continuación, tome $d=4$; de lo contrario, deje $d$ ser el menor divisor primo impar de $n$.) Pero ahora, si $d=3$ $\log_{\mathbb N}(n)\leq 3+\frac n3$ $\lt \frac n{15}+\frac n3$ (desde $n\gt 45$) $=\frac25n$. Si $d=4$ $\log_{\mathbb N}(n)\leq 4+\frac n4$ $\lt \frac3{20}n+\frac n4$ (desde $n\gt 27$) $=\frac25n$. Si $d=5$ $\log_{\mathbb N}(n)\leq 5+\frac n5$ $\lt \frac n5+\frac n5$ (desde $n\gt 25$) $=\frac25n$. Y por último, si $d\gt 5$$\log_{\mathbb N}(n)\leq d+\frac nd\leq \frac nd+\frac nd =\frac 2dn\lt \frac25n$.

Ahora, podemos demostrar que para todos los $N\gt 45$, vamos a tener cualquiera de las $S(N)\lt N$ o $S(S(N))\lt N$. Dado que este proceso puede ser repetido hasta que llegamos a $N\leq 45$ y ya sabemos que todos los $N\leq 45$ (a excepción de $4$) ir a la $5$-ciclo, entonces esto implica que todos los $N$ va a caer en este ciclo. Este se divide en dos casos: si $N$ es compuesto, entonces sabemos que $S(N)=\log_{\mathbb N}(N)\lt N$ por la segunda propiedad básica de $\log_{\mathbb N}$. Finalmente, nos quedamos con el caso de que $N=p$, una de las principales.

Para manejar el primer caso, tenga en cuenta que por simples extensiones de Bertrand Postulado tenemos que para cualquier constante $\epsilon$ hay un $n_0$ tal que para todos los $p\gt n_0$ el primer después de $p$ siempre va a ser $\lt (1+\epsilon)p$; esto significa que para todos lo suficientemente grande $p$, $S(p)\lt (2+\epsilon)p$. En particular, se sabe que para todos los $p\gt 25$, $p_{\mathrm{next}}(p)\lt (1+\frac15)p$, por lo $S(p)=p+p_{\mathrm{next}}(p)\lt \frac{11}{5}p$.

Pero $S(p)$ siempre estará compuesto (es divisible por $2$, después de todo!) y nunca se puede de la forma $2q$ primer $q$ (se puede ver por qué?) así que para todos los $p\gt 25$ tenemos $S(S(p)) \lt \frac25S(p)$ (por la tercera propiedad básica de $\log_{\mathbb N}$, ya que el $S(p)$ es lo suficientemente grande como para que tener) $\lt \frac25\cdot\frac{11}{5}p$ (gracias a la ampliación del postulado de Bertrand) $=\frac{22}{25}p\lt p$.

Ahora, sabiendo que para $N\gt 45$ siempre tenemos bien $S(N)\lt N$ (si $N$ es compuesto) o $S(S(N))\lt N$ (si $N$ es primo), podemos 'rayuela' nuestro camino hacia el rango que su simulaciones por ordenador han cubierto, por tomar uno o dos pasos a lo largo de la ruta de acceso según corresponda. Por ejemplo, supongamos $N=199$. Desde $N$ es primo, nos tomamos un 'salto' de dos pasos: $S(S(199))=S(199+211)=S(410) = 2+5+41 = 48$. Ahora 48 es compuesto, por lo que tener un solo paso: $S(48) = 2+2+2+2+3=11$. Y ahora este es el interior de nuestro "rango", por lo que sabemos que cae en el lazo. Este mismo procedimiento de trabajo para cualquier $N\gt 45$, finalmente llevando a estados unidos a un número menor que $45$ donde estamos seguros de caer en la $5$-ciclo.

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