¿Cómo encuentro un número de la forma $2^i3^j5^k$ más cercano a un determinado número $n$, $i, j, k \in \mathbb{N}$ numéricamente? Por supuesto, puedo tratar de combinaciones de $\lfloor \log_2{n}\rfloor \times \lfloor\log_3{n}\rfloor \times \lfloor \log_5{n}\rfloor$ $i$, $j$ y $k$ y elegir aquella que minimiza la diferencia. Me preguntaba si hay formas más elegantes de hacer esto.
Respuesta
¿Demasiados anuncios?
Una cosa a tener en cuenta es que no siempre una solución única - $11$ está a la misma distancia de$10=2\times5$$12=2^2\times3$. Aún así, podemos estrechar abajo donde buscamos soluciones de algo mediante la aplicación de algunas heurísticas:
$2^i3^j5^k\approx n\implies i\log2+j\log3+k\log5\approx\log n\implies(i,j,k)\cdot(\log2,\log3,\log5)\approx\log n$
Así, ahora sabemos que nuestro aproximado de las soluciones debe a que se encuentran cerca de un avión. Teniendo en cuenta que estamos tomando también $i,j,k\geq0$, podemos restringir nuestra búsqueda aún más, lo que da a los límites de la lista en su mensaje inicial.
Así, en lugar de una búsqueda de fuerza bruta sobre un prisma, se puede reducir a una búsqueda de fuerza bruta sobre un (barrio de) cara triangular de un simplex. Esto significa que un 2d de búsqueda en lugar de un 3d de búsqueda, los cuales deberían reducir la complejidad de algo - me imagino que si el algoritmo original es $O(\log^3n)$, esto debería ser $O(\log^2n)$. Así que es un paso adelante en algún sentido.
Quizás vale la pena señalar que el número de enteros $\leq n$ expresable en la forma$2^i3^j5^k$$\sim \frac{\log^3n}{(3)!\log2\log3\log5}$.
