Bekh's blog

By Bekh, history, 5 years ago, In English

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.

  • Vote: I like it
  • +8
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Bekh (previous revision, new revision, compare).

»
5 years ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

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)$$$

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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) ?

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      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.

      • »
        »
        »
        »
        5 years ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        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.

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Bekh (previous revision, new revision, compare).

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Bekh (previous revision, new revision, compare).

»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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)$$$

  • »
    »
    5 years ago, # ^ |
    Rev. 2   Vote: I like it +8 Vote: I do not like it

    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.

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      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]$$$.

      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        Completely missed that. Thank you for pointing it out :).