# Design an algorithm for efficiently computing the k smallest numbers of the form a+b*sqrt(2)

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".

• 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. – Yuval Filmus Nov 9 '18 at 4:58
• 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? – D.W. Nov 9 '18 at 5:03
• 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 – arealhumanbean Nov 9 '18 at 5:20

## 1 Answer

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.

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