How to find a multiple of an integer that approximates a perfect square.

Question

I'm looking for an efficient algorithm for minimizing (approximate solutions welcome) an integer function of the form: $$ f(j) = \min\left({jn - \left\lfloor \sqrt {jn} \right\rfloor}^2,{\left\lceil \sqrt {jn} \right\rceil}^2-jn\right)$$ for $1 \le j < n$, where $n$ could be a very large number.

Answer 1

It's $f(n)$ and not $f(j)$, right? Also, the second $|...|$ should be $\lceil...\rceil$, should it not?

That being said, every number has a multiple which is a perfect square. OK, you forbid that by requiring $j<n$. Well, then $j=n-2$ gives you a multiple which is 1 away from the nearest square. So the answer is: 1 for squarefree $n$, 0 for the rest.