Number of the form $2^i3^j5^k$ closest to a given number $n$

Question

How do I find a number of the form $2^i3^j5^k$ closest to a given number $n$, with $i, j, k \in \mathbb{N}$ numerically? Of course, I could try $\lfloor \log_2{n}\rfloor \times \lfloor\log_3{n}\rfloor \times \lfloor \log_5{n}\rfloor$ combinations of $i$, $j$, and $k$, and pick the one which minimizes the difference. I was wondering if there are more elegant ways to do this.

Answer 1

One thing to note is that there won't always be a unique solution - $11$ is the same distance from $10=2\times5$ and $12=2^2\times3$. Still, we can narrow down where we look for solutions somewhat by applying some heuristics:

$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$

So, we now know that our approximate solutions ought to lie close to a plane. Given that we're also taking $i,j,k\geq0$, we can restrict our search further, which gives the bounds you list in your initial post.

So, instead of a brute-force search over a cuboid, we can reduce it to a brute-force search over a (neighbourhood of a) triangular face of a simplex. This means a 2d search rather than a 3d search, which ought to reduce the complexity somewhat - I imagine if the original algorithm is $O(\log^3n)$, this ought to be $O(\log^2n)$. So it's a step forward in some sense.

Perhaps worth noting that the number of integers $\leq n$ expressible in the form $2^i3^j5^k$ is $\sim \frac{\log^3n}{(3)!\log2\log3\log5}$.