Algoritmo para averiguar si un número "n" dado se convertiría en "1" a lo largo de una serie de acciones.

Question

Me he encontrado con este problema y no sé cómo empezar.

Si me dan un número n , puedo hacer dos tipos de operaciones con él:

1- Si es impar , n = 3n + 3

2- Si es par, n = n/2

¿Cómo puedo saber si a través de una serie de estas acciones, podré o no conseguir n=1?

Lo único que he podido averiguar es que para que n se convierta en 1, primero tiene que ser una potencia de dos.

Answer 1

Sólo se puede llegar a 1 empezando por ahí o dividiendo por 2. Podemos ver que cualquier potencia de 2 acabará llegando a 1. No hay ninguna opción de impar, asumiendo que siempre empezamos con enteros positivos, que llegue a 1. Como ese es el caso, debemos preguntar si hay una opción impar que llegue a una potencia de 2.

Nuestra ecuación para un número impar es n=3n+3. Podemos demostrar que 3n+3 será divisible por 3 para cualquier valor de n:

3n+3=3(n+1)

Dado que ninguna potencia de 2 es también múltiplo de 3, ningún paso de impar puede llegar a una potencia de 2. Por tanto, los únicos valores de n que llegan a 1 son las potencias de 2.