¿Cómo resolver este algorítmicos en matemáticas olimpiada problema?

Question

Así, hoy hemos tenido un concurso local en mi estado para encontrar a las personas elegibles para la internacional de la olimpiada de matemáticas "IMO" ...

Me quedé con este muy interesante algorítmica problema:

Deje $n$ ser un número natural ≥ 2, tomamos el mayor divisor de $n$ pero debe ser diferente de $n$ sí, restar de $n$. Repetimos esta operación hasta que llegamos $1$.

Ejemplo: Vamos A $n = 30$. Entonces tenemos que restar de sus más grandes de diferentes divisor, es decir, 15. Así que 30 - 15 = 15, ahora hacemos lo mismo:

• 5 es el mayor divisor de 15, por lo que el 15 - 5 = 10
• 5 es el mayor divisor por 10, entonces 10 - 5 = 5
• 1 es el mayor divisor por 5, entonces 5 - 1 = 4
• 2 es el mayor divisor de 4 y 4 - 2 = 2
• 1 es el mayor divisor por 2, por lo que el 2 - 1 = 1 .

Y ya está ! se tomaron 6 pasos para conseguir 1.

Si $n = 2016^{155}$ el número de pasos que tenemos que poner a 1 en la final ?

Yo soy un programador, y yo solía rock con acertijos lógicos, pero esta vez estoy completamente perdido. Así que por favor me ayude.

Answer 1

En primer lugar, tenga en cuenta que: $$n=2^{775}3^{310}7^{155}$$

Deje que el número de pasos para obtener de$x$$1$$f(x)$.

---

A continuación, tenga en cuenta que el mayor divisor de $2x$ siempre $x$.

Por lo tanto: $$f(2x)=f(x)+1$$

Por ejemplo: $$f(30)=f(15)+1$$

La aplicación aquí: $$f(n)=f(3^{310}7^{155})+775$$

---

Ahora, cuando $x$ no es divisible por $2$, el mayor divisor de $3x$ siempre $x$.

Por lo tanto: $$f(3x)=f(3x-x)+1=f(2x)+1=f(x)+2$$

Por ejemplo: $$f(15)=f(5)+2$$

La aplicación aquí: $$f(n)=f(7^{155})+2\times310+775=f(7^{155})+1395$$

---

Ahora, donde $x$ no es divisible por $2$, $3$, o $5$, el mayor divisor de $7x$ siempre $x$.

Por lo tanto: $$f(7x)=f(6x)+1=f(3x)+2=f(x)+4$$

Por ejemplo: $$f(77)=f(11)+4$$

La aplicación aquí: $$f(n)=f(1)+4\times155+1395=2015$$

---

Es sólo una coincidencia?

---

Extra:

Me escribió un programa en Pyth para confirmar esto (toma un tiempo para calcular).

Esto es para números más pequeños.

He utilizado esto para generar $f(x)$$x$$1$$100$.

Una rápida búsqueda devuelve OEIS A064097.

Answer 2

2016 = 2 * 2 * 2 * 2 * 2 * 3 * 3 * 7. Por lo tanto

$2016^{155} = 2^{775} · 3^{310} ·7^{155}$

Ahora pregúntese: ¿Cuál es el mayor factor de $2^{775}· 3^{310} ·7^{155}$? Obviamente es $2^{774} ·3^{310} ·7^{155}$. Restar el número original, y $2^{774}· 3^{310} ·7^{155}$ permanece. Lo mismo va a pasar exactamente 775 veces, y luego se le dejó con $3^{310} ·7^{155}$ después de 775 sustracciones.

¿Cuál es el mayor factor de $3^{310}· 7^{155}$? El factor más grande es $3^{309} ·7^{155}$. Restar este y el resto es $2 · 3^{309} ·7^{155}$. Que de nuevo tiene el mayor factor de $3^{309} ·7^{155}$. Reste esta nuevo y el resto es $3^{309} ·7^{155}$. Con dos sustracciones hemos dividido por 3. Repetimos 310 tiempo para un total de 620 sustracciones y el resto es $7^{155}$.

Ahora el mayor divisor es $7^{154}$; restando esto deja a $6 · 7^{154}$. Ahora el factor más grande es $3 · 7^{154}$ dejando $3 · 7^{154}$. A continuación, el factor más grande es de nuevo $7^{154}$, dejando primera $2 · 7^{154}$$7^{154}$. 4 sustracciones de dividir por 7. Repetimos un total de 155 veces, para 620 sustracciones, llegando a 1. Toteal 775 + 620 + 620 = 2015 sustracciones.

Answer 3

Tenga en cuenta que $(2016)^{155} = 2^{775} \cdot 3^{310} \cdot 7^{155}$.

Para el primer paso, nos resta por $2^{774} \cdot 3^{310} \cdot 7^{155}$ ya que este es el más grande de la no-trivial divisor.

Esto le da a $2016^{155} - \frac{1}{2} 2016^{155} = \frac{1}{2} 2016^{155}$. Repetimos esta operación para el primer $775$ pasos hasta que acabamos $3^{310} \cdot 7^{155}$.

Ahora, el mayor divisor es $3^{309} \cdot 7^{155}$. Nos resta ahora para obtener el $2 \cdot 3^{309} \cdot 7^{155}$. El mayor divisor de esto es que ahora se $3^{309} \cdot 7^{155}$, y restando de nuestro resultado da $3^{309} \cdot 7^{155}$. Es claro que para deshacerse de todos los tres, tomamos $2 \cdot 310$ pasos.

Finalmente, ahora solo tenemos $7^{155}$. Se tarda $4$ pasos para convertir esto en $7^{154}$ (es decir, $7$ se convierte en $6$, $6$ se convierte en $3$, $3$ vuelve $2$, e $2$ hace $1$) por lo que tarda $4 \cdot 155$ más pasos para convertirse $1$.

Con todo, este es $2015$ pasos.

---

Observación. La generalización de aquí es claro.

Si $n = p_1^{e_1} p_2^{e_2} \dots p_n^{e_n}$$f(n) = e_1 f(p_1) + e_2 f(p_2) + \ldots + e_n f(p_n)$.