Question about problem 233 — B. Non-square Equation

Revision en5, by Bekh, 2019-06-12 23:55:08

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.

Tags #math, #help

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en5 English Bekh 2019-06-12 23:55:08 102
en4 English Bekh 2019-06-09 08:50:34 2 Tiny change: '* S(X) + {S(X)}^2$ ' -> '* S(X) + {(S(X))}^2$ '
en3 English Bekh 2019-06-09 08:49:07 382 Tiny change: ' S(X) = N$, or $X + S(X)' -> ' S(X) = N$ $OR$ $X + S(X)'
en2 English Bekh 2019-06-09 06:14:45 30 Tiny change: 'lo, \n\nI was wo' -> 'lo, \n\nIn problem: [problem:233B]\nI was wo'
en1 English Bekh 2019-06-09 06:13:48 293 Initial revision (published)