Find the minimum value of $f(x)= N-x^{\lfloor log_x(N)\rfloor}$ for $1 Is there any efficient way to find the $x$ value for which $f(x)$ is the minimum in the range of $1 < x < 1000$ so that
$$f(x)= N-x^{\large{\lfloor \log_x(N)\rfloor}}\;?$$
Note: $N,x$ are positive integers and $N\gt x$.
 A: Let's generalize the problem setting a bit: If $x$, $x_{max}$, $y$ and $N$ are positive integers satisfying $$2\leq x\leq x_{max}\leq N$$ and $$x^y\leq N$$ what is the maximum possible value of $x^y$? (answering this is equivalent to minimizing $(N-x^y)$, which is what the original problem is about)
Instead of working with $x^y$, we can also work with $\log x^y = y\log x$, since $\log$ is an increasing function.
There are two similarly straightforward approaches to this problem:


*

*We can enumerate the possible values of $x$ and see what is the greatest $y$ for which $x^y$ still doesn't exceed $N$. For each given $x$, such an $y$ can be computed directly as $$y=\left\lfloor \log_x N\right\rfloor$$
Thanks to the identity $$\log_a b = \frac{\log_c a}{\log_c b}$$ we can also rewrite it as $$y=\left\lfloor \frac{\log N}{\log x}\right\rfloor$$ and get $$\log x^y = \left\lfloor \frac{\log N}{\log x}\right\rfloor\log x$$
In other words, we can compute $\log N$ once and then compute one logarithm for each value of $x$, followed by a few simple arithmetic operations: division, truncation and multiplication. As we only need to test $(x_{max}-1)$ possible values of $x$, we are looking at $\Theta(x_{max})$ operations in total.

*Instead of iterating through possible values of $x$, we can look at possible values of $y$. For a given value of $y$, the best possible $x$ would be $$x=\left\lfloor N^{1/y}\right\rfloor$$
The given bounds on $x$ can be used to derive bounds on $y$: Since $x\geq 2$, we must have $$y\leq \lfloor \log_2 N\rfloor$$ and the upper bound $x\leq x_{max}$ tells us that we also need to have $$y\geq \left\lfloor\log_{x_{max}} N\right\rfloor = \left\lfloor\frac{\log_2 N}{\log_2 x_{max}}\right\rfloor$$
Since $$N^{1/y}=\exp\left(\frac{1}{y}\log N\right)$$ we can compute $\log N$ once and use it to compute $\log x^y$ for each particular $y$ using one exponentiation and one logarithm (plus the relatively cheap operations of division, multiplication and truncation). Thus, we are looking at $\Theta(\log_2 N)$ operation. 


While the analysis above ignored many available optimizations (for example, work purely with integers rather than their logarithms might be more efficient and less error-prone due to underestimated precision), it should be sufficient to suggest that with a fixed $x_{max}$, the second approach is apparently faster when $N$ is smaller, but as $N$ keeps growing, the first one will eventually win -- although the crossover may be too far for any practical purposes.
For example, with $x_{max}=256^4$ and $N\leq 256^{1024}$ (as indicated in the comments of the question), the second approach looks considerably better (since it only needs to test less than $8000$ candidates for $y$, while the naive iteration over $x$ would yield more than $4\cdot 10^9$ tests).
A: The term $x^{\lfloor log_x(N)\rfloor}$ is the greatest perfect power of a number less than $1000$ that is less than $N$.  This bounces around a lot.  I just did a little sample with $N=123456789$ and restricting $1 \lt x \lt 32$.  The $x$ that gave the minimum was $22$ with $22^6=113379904$ and it looks like $22$ will give the minimum up to $3^{17}=129140163$, then it stays $3$ until $2^{27}=134217728$  With $N$ this small you have a whole range of exponents that round down to the same power of $x$, so you can ignore all of them until the last where the exponent takes a drop.  For my example of $N=123456789$ the exponent on $x$ is $6$ for $15$ through $22$ so we can ignore $15-21$.  When $N$ gets very large you won't have that any more, so I don't think there is an efficient way.
