2
$\begingroup$

Full question: Numbers of the form $a+b\sqrt{q}$, where $a$ and $b$ are nonnegative integers, and $q$ is an integer which is not he square of another integer, have special properties, e.g. they are closed under addition and multiplication. For $q=2$, some of the first few numbers of this form are given: $0 + 0\sqrt{2}, 1 + 0\sqrt{2}, 0 + 1\sqrt{2},\ldots$

Design an algorithm for efficiently computing the $k$ smallest numbers of the form $a+b\sqrt{2}$ for nonnegative integers $a$ and $b$.

(Hint: systematically enumerate points.)

I have the solution available. The first paragraph is: "A key fact about $\sqrt{2}$ is that it is irrational, i.e., it cannot equal to $a/b$ for any integers $a,b$. This implies that if $x + y\sqrt{2} = x' + y'\sqrt{2}$, where $x$ and $y$ are integers, then $x = x'$ and $y = y'$ (since otherwise $\sqrt{2} = (x-x')/(y-y')$).

I just don't see how knowing that $\sqrt{2}$ is irrational helps to reason about the problem, especially how it's a "key fact".

$\endgroup$
  • $\begingroup$ Without seeing the rest of the solution, it is difficult to say. Presumably, had $\sqrt{q}$ been rational, the solution would become more complicated due to the fact that several numbers of the form $a + b \sqrt{q}$ could coincide. $\endgroup$ – Yuval Filmus Nov 9 '18 at 4:58
  • $\begingroup$ I suggest you try replacing $\sqrt{2}$ with $\sqrt{4}$ and see what happens in the resulting algorithm. Is the algorithm still correct? Does the same proof correctness still go through? $\endgroup$ – D.W. Nov 9 '18 at 5:03
  • $\begingroup$ The brute force solution involves just generating all combinations of a, b for 0 <= a, b <= k. So it's k^2, and then sorting and returning the first k. Not optimal at all. The second solution recognizes that we don't need that many solutions, we can instead create a BST of the form {a,b} and initialize it with the value {0,0}. Then we repeatedly add {BST.min.a +1, BST.min.b}, {BST.min.a, BST.min.b +1} to the BST, and remove the minimum after that, adding it to a result set. This gives O(k log k). The final solution gets O(n) by keeping two pointers i,j in a vector and tracking the smallest a,b $\endgroup$ – arealhumanbean Nov 9 '18 at 5:20
1
$\begingroup$

One way to solve this exercise is to notice that there are at least $k$ numbers of the form $a + b \sqrt{2}$ smaller than $\lfloor \sqrt{k} \rfloor + \lfloor \sqrt{k} \rfloor \sqrt{2}$ (namely, those with $0 \leq a,b \leq \sqrt{k}$). Conversely, every such number of the form $a + b \sqrt{2}$ must have $a,b \leq (1 + \sqrt{2})\sqrt{k}$. Therefore we could simply take all $O(k)$ values of the form $a+b\sqrt{2}$ with $a,b \leq (1+\sqrt{2})\sqrt{k}$, find the $k$th smallest in time $O(k)$, and then go over the list in $O(k)$ and output the $k$ smallest elements. The entire algorithm runs in time $O(k)$ (ignoring the cost of arithmetic operations).

This algorithm needs to compare two numbers of the form $a + b\sqrt{2}$. This can be done as follows. Suppose we want to determine whether $a + b \sqrt{2} \leq c + d \sqrt{2}$. If $a = c$ then this happens iff $b \leq d$, and similarly if $b = d$ then this happens iff $a \leq c$. Suppose, without loss of generality, that $d > b$. If also $c > a$ then $a + b \sqrt{2} < c + d \sqrt{2}$, so suppose that $a > c$. Then $$ a + b \sqrt{2} \leq c + d \sqrt{2} \Leftrightarrow a-c \leq (d-b) \sqrt{2} \Leftrightarrow \frac{a-c}{d-b} \leq \sqrt{2} \Leftrightarrow \\ \left(\frac{a-c}{d-b}\right)^2 \leq 2 \Leftrightarrow (a-c)^2 \leq 2(d-b)^2. $$

What would happen to this approach if we replaced $\sqrt{2}$ by, say, 2? Then there are only $O(\sqrt{k})$ numbers smaller than $\lfloor \sqrt{k} \rfloor + 2\lfloor \sqrt{k} \rfloor$, since not all combinations of the form $a + 2b$ for $0 \leq a,b \leq \sqrt{k}$ are distinct. Indeed, we need to take the upper bound on $a,b$ to be linear in $k$ in order to find the $k$ smallest values of the form $a + 2b$. So the irrationality of $\sqrt{2}$ does make a big difference for the algorithm.

$\endgroup$
  • $\begingroup$ Thank you. One moment while I work through this. $\endgroup$ – arealhumanbean Nov 9 '18 at 5:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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