### Bekh's blog

By Bekh, history, 4 months ago, ,

Hello,

In problem: 233B - Non-square Equation
I was wondering why in submissions like this 12604154 it is sufficient to only check a small range around the square root of n. How can I deduct something like this from the equation, and how to prove it?

Thanks.

Update: Here's a formulation that helped me understand it, maybe it'll be useful for someone.

The main equation is: $X^2 + X * S(X) = N$

Let $Y = X + S(X)$.
$Y^2 = X^2 + 2 * X * S(X) + {(S(X))}^2$ $Thus$
$Y^2 >= X^2 + X * S(X)$

Since $X^2 + X * S(X) = N$ then
$Y^2 >= N$
${(X + S(X))}^2 >= N$
$X + S(X) >= sqrt(N)$

$X >= sqrt(N) - S(X)$

Also, check mohamedeltair's comment for a general proof for the upper bound.

• +8

 » 4 months ago, # |   0 Auto comment: topic has been updated by Bekh (previous revision, new revision, compare).
 » 4 months ago, # | ← Rev. 2 →   +3 It's obvious that $X$ is only up to $10^9$ since $X^2 \leq 10^{18}$ at that limit else the function becomes negative you can also write the formulate the following way $X+S(X) = N/X$.Since $S(X)$ is really small $\leq 81$ so it doesn't contribute to the answer that much making it obvious that I should check only a small bound around $sqrt(N)$
•  » » 4 months ago, # ^ |   0 I was asking if there was a way to deduct an estimate for the bound. The term $X * S(X)$ can get close to $10^{11}$ if $X$ is close to $10^9$ and $S(X)$ is close to $90$. I know that $10^{11}$ would be a small amount when compared to the $10^{18}$ of the $X^2$, and it makes sense to check only a small bound around $sqrt(N)$, but I was looking more for a systematic way to get an estimate of that bound or prove that it is sufficient. How much would the bound change if the upperbound on $S(X)$ changes (if it was some other constant not related to the summation of the digits of course) ?
•  » » » 4 months ago, # ^ |   +3 Assuming that you have a different $S(X)$, assuming there is such $X$ that $S(X)$ equals any integer from $1$ to $K$, I am pretty sure your bound is $K$ if that's what you're asking.
•  » » » » 4 months ago, # ^ | ← Rev. 2 →   0 Sorry my head has been stuck far ahead looking at it as $X^2 + X * S(X) = N$ and I couldn't comprehend how a value as big as $X * S(X) -> 10^{11}$ could be covered with a range small as $100$. But now I've understood that the bound is independent of $X$. Thank you that was helpful. I've also updated the blog with a similar formulation that helped me understand it more.
 » 4 months ago, # |   0 Auto comment: topic has been updated by Bekh (previous revision, new revision, compare).
 » 4 months ago, # |   0 Auto comment: topic has been updated by Bekh (previous revision, new revision, compare).
 » 4 months ago, # |   +3 Extending to your formulation that proves the lower bound, here is a one that proves the upper bound:Let $Z = X - S(X) \\ Z^2 = X^2 - 2*X*S(X) + S(X)^2 \\ Z^2 \leq X^2 - X*S(X) \, (Because \, X*S(X) \geq S(X)^2) \\ Z^2 \leq N \\ (X-S(X))^2 \leq N \\ X-S(X) \leq \sqrt{N} \\ X \leq \sqrt{N}+S(X)$
•  » » 4 months ago, # ^ | ← Rev. 2 →   +8 Thank you. I got a tighter upper bound since $S(X) > 0$ we can say $X^2 <= N$ and thus $X <= sqrt(n)$ directly. But your formulation is useful in case S(X) was another constant that could take negative values. I'll update the blog to refer to your comment.
•  » » » 4 months ago, # ^ |   +3 I don't think my proof will work work for negative values of $S(X)$ (because in the third line, $Z^2$ will be $\geq X^2 - X*S(X)$). But yes, the best bounds to check the answer within are $[\sqrt{N}-S(X),\, ceil(\sqrt{N})-1]$.
•  » » » » 4 months ago, # ^ |   +8 Completely missed that. Thank you for pointing it out :).