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.
Auto comment: topic has been updated by Bekh (previous revision, new revision, compare).
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)$$$
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) ?
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.
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.
Auto comment: topic has been updated by Bekh (previous revision, new revision, compare).
Auto comment: topic has been updated by Bekh (previous revision, new revision, compare).
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)$$$
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.
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]$$$.
Completely missed that. Thank you for pointing it out :).