Beatty sequence ($\lfloor n\alpha \rfloor$)

The sequence $\lfloor n\alpha \rfloor$ for $n=1,2,\dots$, with a fixed positive irrational number $\alpha$. Complementary Beatty sequences for $\alpha ,\beta >1$ partition the positive integers when $1/\alpha +1/\beta =1$.

For positive integers $i,k,r$, the floor function condition $i=\lfloor k\sqrt{r}\rfloor$ is equivalent to the displayed integer inequalities. Since $r\ge 1$, a witness satisfies $k\le i$. Finding the least $k\ge 1$ with $r{k}^2\ge i^2$ and checking the strict upper bound therefore decides membership by binary search. Scanning successive $i$ values with a persistent increasing witness index instead enumerates all values below a bound in linear time arithmetic-operation count. Exact integer comparison avoids floating-point errors near an integer boundary.

Let $\alpha >1$ be irrational and $\beta =\alpha /(\alpha -1)$, so $1/\alpha +1/\beta =1$. The Beatty sequences $\lfloor n\alpha \rfloor$ and $\lfloor n\beta \rfloor$, $n\ge 1$, partition the positive integers.

Indeed, the numbers of terms at most $m$ are $\lfloor (m+1)/\alpha \rfloor$ and $\lfloor (m+1)/\beta \rfloor$. Their arguments sum to the integer $m+1$, and neither is integral, so the counts sum to $m$. Subtracting the count at $m-1$ shows that every integer occurs exactly once in the two lists together. This proof interprets reciprocity as an exact complementarity of two densities.

If $\alpha ,\beta >1$ are irrational numbers with $1/\alpha +1/\beta =1$, the Beatty sequences $\lfloor n\alpha \rfloor$ and $\lfloor n\beta \rfloor$ partition the positive integers.