This problem comes from an programming competition website, but I'd interested in analyze it from mathematics prespective. Given this problem below, we must create a program that could give us the correct output from the given input. The program must run under the time limit that provided by the system.
The Problem
Let define function $s$ that take input from positive integers, such that $s(x)$ is the sum of the digit of $x$.
For example, $s(1024) = 1 + 0 + 2 + 4 = 7$
Given some integer constant $n$ as the input of the program. Now, find positive integer solution of $x$ in equation
$x^2 + s(x) \cdot x - n = 0.$
If more than one solution exist, choose the lowest one. If the solution doesn't exist, give output -1.
Time Limit of the program: 2 second.
Range of the input $n$: $[1, 10^{18}]$
The Solution
In finding the solution, we could iterate from some range of possible value of x, and try each of these value whether it satisfy the equation or not.
To improve the run time of the program, we must choose the shortest range for x.
My Question
What is the shortest range of possible value of x that we could iterate to find the answer of the problem above?
Is there a better way to find the solution without iterating from the set possible value of x?
My Attempt:
Consider that $x^2 + s(x) \cdot x - n = 0$ $\Leftrightarrow x ( x + s(x) ) = n$
and since both $x$ and $(x + s(x))$ are positive integers and the product of both number is $n$, we can conclude that $x$ and $(x + s(x))$ is a pair of positive factor of $n$.
Since $x$ is a factor of $n$, we now have the first possible range of $x$, that is $[1, n]$.
But, iterating $x$ over this range gives bad performance to the program. For small value of $n$, it won't matter, but for $n \geq 10^{17}$, the program will reach it's time limit.
If I could recall correctly, we have this theorem
$x_1 \cdot x_2 = x$
and
$x_1 \leq x_2$
implies that
$x_1 \leq \sqrt{x} \leq x_2$
And since $x (x + s(x)) = n$ and $x \leq x + s(x)$
we have $x \leq \sqrt{n} \leq x + s(x)$
Now we have the second range: $[1, \sqrt{n}]$
But, still, this range also give bad performance for larger $n$.
My last attempt is by considering the biggest possible value of $s(x)$, that is the digit of $x$ is all $9$ and $x$ less than or equals to the maximum value of $n$, $10^{18}$.
$s(x) \leq s(999,999,99 \cdots 9,999) = 9 \cdot 18 = 162$
Hence, we have
$x + s(x) \leq x + 162$
so that, $\sqrt{n} \leq x + s(x) \leq x + 162 \leq \sqrt{n} + 162$ hence, $\sqrt{n} - 162 \leq x \leq \sqrt{n}$
Now, we have better range that will suffice for all value of $x$. $l_1 = \max \{ 1, \sqrt{n} - 162 \}$ $l_2 = \sqrt{n}$ the range is $[l_1, l_2]$
But, I though there must be a better solution to this problem. Hence I try $l_1 = \max \{ 1, \sqrt{n} - 162/2 \}$ And that range is also correct. But I can't justify my finding.
So, hence my third question:
- Why $l_1 = \max \{ 1, \sqrt{n} - 162/2 \}$ also gives us correct solution?