Dado un número$n$, ¿cuál es el número mínimo de operaciones de $+1, -1, /2, /3$ necesario para alcanzar la $0$?

Question

Dado un número$n > 0$, ¿cuál es el número mínimo de operaciones para reducir este número a $0$ ?

Podemos utilizar estas operaciones:

• $+1$
• $-1$
• $/2$ (cuando el número es divisible por $2$)
• $/3$ (cuando el número es divisible por $3$)

Sería impresionante si usted también podría proporcionar una prueba.

Answer 1

Si la respuesta es $f(n)$,$f(n)=1+\min(f(n-1),f(n+1),f(n/2),f(n/3))$.

Trate de usar la inducción y ver si usted puede encontrar un patrón. Por ejemplo, el primer par de se $f(0)=0,f(1)=1,f(2)=2,f(3)=2$.

Puede ser difícil encontrar una buena solución general, porque aunque creo que este problema tiene conexiones al catalán de la conjetura y la conjetura ABC.

Answer 2

Esta no es una solución sino un comentario extendido.

Aquí es un muy tentador algoritmo:

• si $n$ es divisible por $3$, se divide por $3$. De otra manera :

  $\qquad\bullet$ si $n$ es divisible por $2$ luego se dividen por $2$. De otra manera :

  $\qquad \qquad \bullet$ $n$ es $6k+1$ (en cuyo caso restar $1$) o $6k-1$ (en cuyo caso agregar $1$).

Recorrer.