Sequence of quadratic surds over nonnegative integers without having to delete or sort?

Question

I am trying find an strictly increasing iterative sequence that gives this set sorted: $$[a+\sqrt{b}: a,b \in \mathbb{N_0}].$$ These are a subset of constructable numbers. When I look at it, there are obvious patterns, but I cannot seem to find an efficient algorithm to find them without deleting or sorting. I don't know if this is even possible. Any help is appreciated.

I can generate the first 20 using Mathematica:

Take[Sort[Flatten[Table[Select[DeleteDuplicates[Total[Tuples@{Table[i,{i,0,k}], Table[Sqrt[i],{i,0,k}]}, {2}]],# <= k&],{k,60,60}]],Less],20]

$$\left\{0,1,\sqrt{2},\sqrt{3},2,\sqrt{5},1+\sqrt{2},\sqrt{6},\sqrt{7},1+\sqrt{3},2\sqrt{2},3,\sqrt{10},1+\sqrt{5},\sqrt{11},2+\sqrt{2},1+\sqrt{6},2\sqrt{3},\sqrt{13},1+\sqrt{7}\right\}$$

Answer 1

First, here is a subroutine: figuring out the number of elements of $S$ less than $\sqrt k$ for some integer $k$. (Call this number $r_k$; we will refer to it later.)

If $\sqrt k$ is an integer, then $r_k$ is easier to find and has a closed form. In $S \cap [0,\sqrt k)$, there are

• $\sqrt k$ elements of the form $a$;
• $\sqrt k-1$ elements of each of the forms $a + \sqrt2$ and $a+\sqrt3$;
• $\sqrt k-2$ elements of each of the forms $a + \sqrt 5, a + \sqrt6$, $a + \sqrt7$, $a + \sqrt8$;
• and so forth.

Apart from the first $\sqrt k$ cases, there are $2j$ values of $b$ in the range strictly between $j^2$ and $(j+1)^2$, which appear $\sqrt k - j$ times. So we have $$r_k = \sqrt k + \sum_{j=1}^{\sqrt k} 2j(\sqrt k - j) = \frac{(k+2)\sqrt k}{3}.$$

If $k$ is not an integer, things are harder, but at least we don't have to worry about edge cases as much. Fix $a$; then $a + \sqrt b < \sqrt k$ if and only if $b < (\sqrt k - a)^2$ or $b < a^2 + k - 2a\sqrt k$. Including $0$, there are $a^2 + k - \lfloor 2a\sqrt{k}\rfloor$ values of $b$ in this range. However, to avoid duplicates, we don't want $\sqrt b$ to be a positive integer; there are $\lfloor \sqrt k\rfloor - a$ cases to exclude. Summing over all values of $a$ from $0$ to $\lfloor \sqrt k\rfloor$, we have $$ r_k = \sum_{a=0}^{\lfloor \sqrt k\rfloor} (a^2 + a + k - \lfloor 2a\sqrt{k}\rfloor - \lfloor \sqrt k\rfloor). $$

---

We will use the formula for $r_k$ to recursively generate the sorted elements of $S \cap [n,n+1)$ using the sorted elements of $S \cap [n-1,n)$. There are two cases:

• If $a + \sqrt b \in S \cap [n,n+1)$ and $a>0$, then $(a-1) + \sqrt b \in S \cap [n-1,n)$, so we can just take the corresponding element of $S \cap [n-1,n)$ and add $1$.
• If $\sqrt b \in S \cap [n,n+1)$, then it occupies the $(r_b+1)$-th position in $S$ globally, but there are $r_{n^2}$ elements of $S$ that come before $n$ and don't appear in $S \cap [n,n+1)$, so $\sqrt b$ occupies the $(r_b - r_{n^2}+1)$-th position in this interval.

To make this happen, loop through $S \cap [n-1,n)$ and add $1$ to each element you find, but keep track of the next element of the form $\sqrt b$ you have to include. When you get to the $(r_b - r_{n^2}+1)$-th position, put in $\sqrt b$ instead, and move on to waiting to include $\sqrt{b+1}$ at the appropriate moment.

Here is a Mathematica implementation; for an integer n, sequence[n] will generate all the elements of $S$ less than n in order, by joining together the appropriate intervals.

r[k_] := r[k] = If[IntegerQ[Sqrt[k]], ((k + 2) Sqrt[k])/3, 
    Sum[a^2 + a + k - Floor[2 a Sqrt[k]] - Floor[Sqrt[k]], 
      {a, 0, Floor[Sqrt[k]]}]];
interval[0] = {0};
interval[n_] := interval[n] = Module[{nextb = n^2 + 1, nextbpos, i = 1},
      nextbpos = r[nextb] - r[n^2] + 1;
      Table[If[j == nextbpos, 
          nextb++; nextbpos = r[nextb] - r[n^2] + 1; Sqrt[nextb - 1],
          interval[n - 1][[i++]] + 1]
      ,{j, Length[interval[n - 1]] + 2 n}]
    ]
sequence[n_] := Flatten[interval /@ Range[0, n - 1]]

---

Alternatively, here is a simpler solution if some amount of comparing values in $S$ is permissible. Here, we still use the idea that each element of $S$ is either $\sqrt b$ or else $1 + x$ where $x$ is a smaller element of $S$, but we don't try to intelligently calculate which it should be. At each step, we just compare the least unused element of each type, and use the smaller of the two.

Use s[n] to generate the first n elements of $S$, in order:

s[n_] := Module[{output = {0}, lastB = 2, lastI = 1},
  Do[If[Sqrt[lastB] < output[[lastI]] + 1,
     AppendTo[output, Sqrt[lastB++]];
     lastB += Boole[IntegerQ[Sqrt[lastB]]],
     AppendTo[output, 1 + output[[lastI++]]]];
   , {n - 1}]; output]