Lambek–Moser theorem

In combinatorial number theory, the Lambek–Moser theorem is a generalization of Beatty's theorem that defines a partition of the positive integers into two subsets from any monotonic integer-valued function. Conversely, any partition of the positive integers into two subsets may be defined from a monotonic function in this way.

The theorem was discovered by Leo Moser and Joachim Lambek. Dijkstra (1980) provides a visual proof of the result.

The theorem applies to any non-decreasing and unbounded function f that maps positive integers to non-negative integers. From any such function f, define f * to be the integer-valued function that is as close as possible to the inverse function of f, in the sense that, for all n,

It follows from this definition that f ** = f. Further, let

Then the result states that F and G are strictly increasing and that the ranges of F and G form a partition of the positive integers.

Let f (n) = n²; then ${\displaystyle f^{\ast }(n)=\lfloor {\sqrt {n-1}}\rfloor }$. Thus F(n) = n² + n and ${\displaystyle G(n)=\lfloor {\sqrt {n-1}}\rfloor +n.}$ For n = 1, 2, 3, ... the values of F are the pronic numbers

...
Wikipedia