Design an algorithm for efficiently computing the k smallest numbers of the form a+b*sqrt(2)
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 &gt; b$. If also $c &gt; a$ then $a + b \sqrt{2} &lt; c + d \sqrt{2}$, so suppose that $a &gt; 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.