Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

  1. What is the shortest range of possible value of x that we could iterate to find the answer of the problem above?

  2. 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:

  1. Why $l_1 = \max \{ 1, \sqrt{n} - 162/2 \}$ also gives us correct solution?
share|improve this question
add comment

4 Answers

up vote 4 down vote accepted

While not a full answer to your questions, here is a trick that will allow you to reduce the collection of numbers you have to try (and so an answer to question 2).

Because $10\equiv 1 \pmod 9$, we have $10^k \equiv 1 \pmod 9$ for every $k\in \mathbb N$. If we write a number in terms of its digits, $x=\sum a_k 10^k$, then since $\sum a_k 10^k \equiv \sum a_k \pmod 9$, we have $s(x)\equiv x \pmod 9$. This fact can be used to give a way to check arithmetic, among other things.

Therefore, if $x^2 + s(x)x = n$, then $2x^2 \equiv n \pmod 9$. Since $(2)(5)=10 \equiv 1 \pmod 9$, we can multiply to get $x^2 \equiv 5n \pmod 9$.

The squares modulo 9 are $0, 1, 4, 7$, so unless the remainder of dividing $5n$ by $9$ is one of these numbers, there are NO solutions.

If the remainder is one of those numbers, you need to know the square roots modulo 9 to know what values of $x$ to try.

For this, we have the following.

$0^2\equiv 3^2 \equiv 6^2 \equiv 9 \pmod 9$, $1^2\equiv 8^2 \equiv 1 \pmod 9$, $2^2\equiv 7^2 \equiv 4 \pmod 9$ and $4^2 \equiv 5^2 \equiv 7 \pmod 9$.

The upshot of this is that if $n$ is a multiple of $9$, then you only have to check the multiples of $3$ (reducing the number of things you have to check by a factor of $3$). Otherwise, depending on the modulus of $5n\bmod 9$, you either have to check NO numbers (5 of the remaining cases), or you have to check $2/9$ of the numbers (3 of the remaining cases). Thus, whatever range you are working in, you have at least a speed up by a factor of $3$, if not more.


Another comment, which gives a small speedup over what you already have but answers question 3. As you observed, $x<\sqrt n$, and the number of digits of $x$ is at most $\lceil \log_{10} x \rceil$, and since $s(x)$ is at most $9$ times the number of digits of $x$, we have $s(x)<9 \lceil \log_{10} \sqrt n \rceil=9\lceil \frac{1}{2}\log_{10} n \rceil$.

Therefore, given $n$, you can limit your search for $x$ to $[\sqrt n - 9\lceil \frac{1}{2}\log_{10} n \rceil, \sqrt n]$. The factor of $1/2$ here answers question 3. Note, we could probably shave off $1$ or $2$ numbers from the range by being more careful with rounding, but I don't see any obvious reason we could shave off more. If we combine this with the beginning of my answer, you have to check at most $3\lceil \frac{1}{2}\log_{10} n \rceil$ numbers to find your solution, if it exists, and no numbers a good portion of the time when no solution exists.

share|improve this answer
    
I think $(2)(5)=10 \equiv 1 \pmod 5$ in pharagraph 3 should be $(2)(5)=10 \equiv 1 \pmod 9$. –  Kamal Hajjaj Isa Oct 28 '12 at 14:58
    
@KamalHajjajIsa: Yes, that is correct. Thank you. –  Aaron Oct 29 '12 at 3:07
    
I like the Idea of using $\pmod 9$. –  Kamal Hajjaj Isa Oct 29 '12 at 4:56
add comment

Beside the excellent modulo 9 tricks Aaron gave you, if $n$ passes his tests the easiest thing is to try the range of $1 \le s(x) \le 162$ with the proper $s(x) \pmod 9$. Just plug each one into the quadratic formula and solve for $x$. If it doesn't come out integral, go on to the next. If it does, check the sum of digits against the assumed $s(x)$. If it matches, success and report it. If not, go on to the next. At most $50$ numbers to try, which should fit in 2 seconds easily.

share|improve this answer
add comment

This only answers the third question

If you use the general quadratic equation formula for the equation $ax^2+bx+c=0$ $$\displaystyle x= \frac {-b \pm \sqrt{b^2-4ac}}{2}$$ It follows from $x^2 + s(x)\cdot x - n = 0$ that $$\displaystyle x= \frac {-s(x) \pm \sqrt{s^2(x)+4n}}{2}$$ Since all the variables are positive and obviously $\sqrt{s^2(x)+4n}>s(x)$ , one can remove the negative sign and have $$\displaystyle x= \frac {-s(x) + \sqrt{s^2(x)+4n}}{2}$$ If one extends the range of values of $n$ to $0$, we have that the lowest possible value of $s(x)$ is $0$ and that $s(x) \ge 0$ which implies that $$\displaystyle x \ge \frac {-s(x) + \sqrt{4n}}{2} = \frac {-s(x)}{2} + \frac {2\sqrt{n}}{2} \ge \frac {-162}{2} + \sqrt n, \space \space (-s(x) \ge -162) $$ and there you have your inequality $$x \ge \sqrt n - \frac {162}{2}$$

Extending the range to $0$ doesn't change the validity of the inequality and helps to simplify it. You've been working with the maximum value of $s(x)$, using the minimum value helps in this case.

share|improve this answer
add comment

Since $x<\sqrt n$ and $n\le10^{18}$, we have that $x<10^9$. Then $x$ has at most $9$ digits and $s(x)\le9\times9=81$. This implies that $x^2+81\,x-n\ge0$. It follows easily that we must have $$ x\ge\frac{-81+\sqrt{81^2+4\,n}}{2}=\sqrt{n+(81/2)^2}-81/2. $$

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.