4 votos

Mejor solución a un problema de la teoría elemental de números.

He encontrado el siguiente problema acerca de primaria número de thery

Alice diseñado un programa que toma un entero $n>1$, y a continuación, factores como $a_0^{e_0}a_1^{e_1}a_2^{e_2}\cdots a_1^{e_n}$. A continuación, se calcula $r=a_0e_0+a_1e_1\cdots+a_ne_n+1$, y se repite el proceso con $r$. Demostrar que siempre terminan en un periódico de la secuencia, y encontrar cada tiempo posible.

Mi solución:

Definir $f(x)$ $\rightarrow$ como una iteración del programa.

Lema 1.1:Para cada natural $x\ge3$, $x^2>2x+2$

Prueba: $$x-1\ge2\implies x^2\ge2x+3>2x+2$$ Lema 1.2:Por cada naturals $s\ge2$$x\ge3$, $x^s>sx+2$

Prueba: Hipótesis inductiva:$x^k\ge xk+2$ $\forall x\ge2\in\mathbb{N}$.Por lo tanto $$x^{s+1}\ge sx^2+2x > sx+x+1=x(s+1)+2$$ Usando el lema 1.1 como basecase, terminamos la prueba.

Lema 1.3:Para cada uno de los diferentes números primos $p,q$, $f(pq)\le pq$

Prueba: Vamos a wlog $p<q$

Entonces, $p\ge2$,$p\ge3$,$p\neq q$ $$p-1\ge1$$ $$q-1\ge2$$ $$pq-q-p+1\ge2$$ $$pq\ge q+p+1$$ $$pq\ge f(pq)$$ Y la igualdad se alcanza el fib $p=2,q=3$

Lema 1.4:Para cada $x\in\mathbb{N}$ más de $2$ factores primos y al menos dos diferentes, tenemos $f(x)<x$

Prueba: Desde Lema 1.3 sabemos que si $p$ $q$ son diferentes de los números primos $$pq\ge q+p+1$$ Multiplicar por un prime $x$ ambos lados $$xpq\ge x(q+p)+x>p+q+1+x$$ Por lo $xpq>f(xpq)$ por cada prime $x$

Ya queremos mostrar que $f(ypq)<ypq$ $\forall y\ge2$, podemos multiplicar por sus factores primos $x$ un número finito de veces y de la misma manera de obtener el resultado.

Luego, a partir de Lema 1.2 sabemos que $p^k>f(p^k)+1$ para todos los $k\ge2$,$p\ge3$. Pero no sabemos lo que sucede cuando $k=1$ o $p=2$.

Si $p=2$ $$f(2^k)=2k+1$$ Ya sabemos $2^3\ge 2*3+2$ utilizamos la prueba del Lema 1.2 verificar $2^s>2s+2$ $s>3$ Entonces, nos quedamos con $$f(2)=3\rightarrow 4\rightarrow 5\rightarrow 6\rightarrow 6$$ $$f(4)=5\rightarrow 6\rightarrow 6$$ $$f(8)=7\rightarrow 8$$ Y $2^s>f(2^s)+1$$s>3$. Así que si $p+1$ es un número de la forma $2^s$ donde $s>3$ $p\rightarrow p+1=2^s\rightarrow 2s+1<2^s-1=p$, y nos cuenta que después de dos iteraciones que el número ha disminuido.

Si $k=1$, luego tenemos $$f(p)=p+1$$

Si $p\neq2$(lo hemos visto con el caso del que antes), entonces $f(p)=2k$ para algún entero k\ge2$

A continuación, $2k$ es una potencia de $2$ o no lo es.

Si es así, entonces hemos tratado con el caso del que antes y hemos terminado.

Si no lo es, entonces $2k$ tiene dos o más factores primos.

Si ha $2$, sabemos por el lema 1.3 que podemos lograr la igualdad iff $p=6$ y que las iteraciones son la disminución en otros lugares.

Si tiene más de $2$, ya que hemos tratado con perfecta poderes antes de que sabemos que tiene al menos dos factores diferentes, y el Lema 1.4 dice que no hay más soluciones y la iteración está disminuyendo.

Respuesta: $7\rightarrow8\rightarrow7$ $6\rightarrow6$

Pregunta: Se que hay una forma más rápida y sencilla de solucionar esto?

4voto

Calvin Lin Puntos 33086

Lema 1: Si $ x $ es un número primo, entonces $f(x) = x+1$.

Lema 2: Si $x = mn$ (no necesariamente coprime), a continuación,$f(mn) - 1 = [f(m) - 1] + [f(n) - 1 ]$.

Considero que esto es el quid de la función. Esto es fácil de demostrar (una vez que lo saben).

Ahora compruebe que $f(4) = 5$, $f(6) = 6$ y $f(8) = 7$.

Lema 3: $f(x) \leq x+1$.

Lema 4: Si $ x\geq 9$ es compuesto, entonces $f(x) \leq x-2 $.

Deje $x=mn$, entonces, queremos mostrar que $f(mn) \leq f(m) + f(n) -1 \leq m+n+1 \leq mn-2.$

La última desigualdad se cumple debido a que $(m-1)(n-1) \geq 4$.

Lema 5: Si $x \geq 9$,$f(f(x)) \leq x-1 < x$.

Corolario: Cada secuencia de $f^{(i)}(x)$ es el tiempo de periódico.

Corolario: Si $x \geq 9$, $x$ no aparece en un periódico de la secuencia. Sólo tenemos que comprobar $f(x)$ $x=1$ a 8 a encontrar los diversos periódicos de secuencias.

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