On a theorem by Lambek and Moser.

While looking for interesting functions mapping sequences of integers into sequences of integers, W.H.J. Feijen found in [1] the following results attributed to J. Lambek and L. Moser.

Let f be an ascending continued concatenation of natural numbers, more precisely:

(Ax : x ≥ 0 : 0 ≤ f xf (x+1)) ,
such that, furthermore, f x exceeds any given bound F for sufficiently large x, more precisely:
(AF : F ≥ 0 : (EX : X ≥ 0 : (Ax : x ≥ X : f x > F))) .

Let the function C with g = C f be defined by the relation for all y ≥ 0

g y = (Nx : x ≥ 0 : f xy)
(The right-hand side being read as “the number of distinct natural values x such that f x is at most y”). Obviously, g is also an ascending continued concatenation such that g y exceeds any given bound G for sufficiently large y.

The first result attributed to Lambek and Moser is that then f = C g, as is illustrated by the example

f :011366781010......
g :1334446788......

Let for any continued concatenation q of natural numbers the function D be defined by the relation for all n ≥ 0

D q n = n + (q n) .

In the above example we would have

D f :0236101113151819......
D g :14578912141617......

The second result attributed to Lambek and Moser is that D f and D g form a partitioning of the natural numbers. For people willing to generalize pictures the visualization “proves” these results. The elements of f and D f have been represented by vertical bars, one wide and of the corresponding length, those of g and D g have been represented by a horizontal ones. The mapping C then becomes a reflection.

Tracing the plot, we can place the bars in the order of increasing length: bar 14 is next (horizontally), bar 15 vertically, bars 16 and 17 again horizontally, etc.

[1] Honsberger, Ross
“Ingenuity in Mathematics”
New Mathematical Library, Vol 23
Mathematical Association of America (1970)


Plantaanstraat 59 October 1980
5671 AL NUENENprof. dr. Edsger W. Dijkstra
The NetherlandsBurroughs Research Fellow

Transcribed by Martin P.M. van der Burgt
Last revision 10-Nov-2015 .