Find a closest integer of form $3^x 5^y$?

Question

Given a arbitrary positive integer, is it possible to have a close-form solution of finding the closest (either smaller or larger) integer of form $3^x 5^y$, where $x$ and $y$ are non-negative integers? I can only think of using computer to search but wonder if it can be done better?

Answer 1

It is easy to see that the $(x,y)$ that realize the closest integer must also realize the minimum of $n/ 3^x 5^y$ or the minimum of $3^x 5^y/n$, depending if it is above or below $n$.

These minima are equivalently found as $ \min \log n - x \log 3 - y \log 5$ and $x \log 3 + y \log 3 - \log n$ , in the region where the quantities are positive.

Now let $T := \{ (x,y): x, y \in \mathbb{N} \}$, and take the line $\ell := \{ (t, s) : (\log 3 ) t + (\log 5) s = \log n\}$. We are searching for the two closest point to $\ell$ in $T$ , one from the region above the line and one from the region below the line.

Note that the line intersect the axis at $\log_3(n), \log_5(n) $, which are bounded from above by $m= \log_3(n) $.

Below there is a mse answer where you have an algorithm described to solve this general problem, where at each step you change the line without changing the solution. There is a stated hypothesis that would mean $\log(n) $ small, but it is not used in the answer. The answer runs in time $\log m \simeq \log \log n$.

Diophantine approximation - Closest lattice point to a line (2d)

Also, let me notice that Gerry is right: I don't think you can do much better than $\log \log n$. Let $x_0, y_0$ be an integral solution to the closest to the line problem, and $x_1, y_1$ the projection of that point to the line. In particular it holds:

$$ (1) \ \ y_1 = - x_1 \log_5 3 + \log_5 n $$ $$ (2) \ \ |y_1 - y_0| \le 1/2 , |x_1 - x_0 | \le 1/2$$

(1) originally comes from $y_1 \log 5 + x_1 \log 3 = \log n$. In particular, we can suppose wlog $ x_1 \log_3 \le (\log n) /2$.

The second inequality comes from the fact that a line in a 1 times 1 square has a vertex which has distance at most $1/2$ in each coordinate.

The first equation implies, substituting $ x_1= [ \log_3 n ] - x_1'$, that

$$ y_1 = - [\log_3 n] \log_5 3 + (\log _5 3)x_1' + \log_5(n) $$

Notice that the modulus of the constant term

$$ | [\log_3 n] \log_5 3 - \log_5 n| = | (\log_3 n +\epsilon(n) )\log_5 3 - \log_5 n | = |\epsilon(n) | \log_5 3 < 1/2$$

Because the deviation $[\alpha] - \alpha$ from a number to its closest integet is at most 1/2. Dividing by $x_1'$ we get

$$ | \frac{y_1}{x_1'} - \log_3 5 | \le \frac{1}{2x_1'} $$

It's not hard to see that $|y_1/x_1 - y_0/x_0| \le 2/x_0 $ using the derivatives of $f(a, b) = a/b$, so that triangular inequality gives

$$ | \frac{y_0}{x_0'} - \log_3 5 | \le \frac{5}{2x'} $$

This means that one between $\{ (y_0-2) /x'_0, .. (y_0+2) /x'_0\}$ is the closest rational number with denominator at most $x_0'$. (I could be wrong with specific numbers, there could be a 3 instead of a 2, but the principle is the same). Also, notice that $x_0' \approx x_1' \approx \log_3 n - x >= (\log_3 n) /2 $ because of the WLOG assumption.

Up to my knowledge, the fastest way to produce rational approximants is to use continued fractions, that generally produce a denominator $\approx 2^k$ in k steps, so that the number of steps to produce a denominator $q$ is $\log q$.

Since our problem produces a denominator $\log(n) $, it's running time should be at least $\log \log n$, as the Gerry algorithm (and mine above) does.

Answer 2

For any $n$, $b = \lfloor log_2(n) \rfloor$ is an upper bound for the exponents in its prime factorization. So, both $x$ and $y$ are bounded by $b$.

If your $b$ is small, you can just do an exhaustive search of $3^x5^y$ by varying $x, y$ between $0$ to $b$ and check them.

It is also true that $x + y$ is bounded by $b$. So, you can use that to make the search even more efficient.

Answer 3

Well, $3^3=27 = 2+5^2$. I hoped I could find a "closer" pair of $\frac {3^k - 5^j}{\operatorname{avg}(3^k,5^j)} < \frac 2{\operatorname{avg}(27,25)}$ and maybe if I wrote a program I would have bout $3^3-5^2 = 2$ is pretty small.

For $n$ for $k,j$ so that $5^k \le n < 5^{k+1}$ and $3^{j-1} < n \le 3^j$. (If either are equal we are done and we can stop)

Check whether $5^{k-2}3^2$ (which is $5^k+2*5^{k-2}$) is larger or smaller then $n$ and check whether $3^{j-3}5^2$ (which is $3^j - 2*3^{j-3}$) is larger or smaller than $n$.

We will end that and every sequential step with a result that $3^{j'}5^{k'} \le n \le 3^{\overline j}5^{\overline k}$ for some $j',k',\overline j,\overline k$.

If you reach an equality you are done. Otherwise repeat the step by comparing $3^{j'+3}5^{k'-2}$ to $n$ and $3^{\overline 3-3}5^{\overline k + 2}$.

If you never hit an equality you will eventually reach some $j',k',\overline j, \overline k$ where $3^{j'}5^{k'}< n < 3^{j'+3}5^{k'-2}$ and $3^{\overline j-3}5^{\overline k+2}< n < 3^{\overline j}5^{\overline k}$ and $j'$ and $\overline j$ will be within three of each other and $k'$ and $\overline k$ will be within $2$ of each other.

We finish by comparing $3^{j'+1}5^{k}; 3^{j'+2}5^{k'};3^{j'}5^{k'+1}; 3^{j'+1}5^{k'+1};3^{j'+2}5^{k'+1};3^{j'}5^{k'+2};3^{j'+1}5^{k'+2};3^{j'+2}5^{k'+2}$ if necessary.