Patterns in the sesquinary representations of integers

We can represent all positive integers in a 2<- 3 exploding dots machine using the digits 0, 1, and 2.

We call such a representation the sesquinary representation (from “sesqui” = “one and a half”).

The integers between 15 and 23 have 5 digits in their sesquinary representation:

Reading the digits from the left we see:

The 1st digit (from the left) is always 2 – just 1 possible pattern.
The first two digits are always 2, 1- just 1 possible pattern.
The first three digits are either 2, 1, 0 or 2, 1, 2 – 2 possible patterns.
The first four digits are either 2, 1, 0, 1 or 2, 1, 2, 0 or 2, 1, 2, 2 – 3 possible patterns.

Jim Propp

Jim Propp examined (Endnote #7) the number of different patterns for the first 1, 2, 3, 4, 5, 6 ,…, 20 digits, for numbers large enough to have more than 20 digits.

What he found was a number sequence: 1, 1, 2, 3, 4, 6, 9, 14, 21, 31, 47, 70, 105, 158, 237, 355, 533, 799, 1199, 1798, … that the Online Encyclopedia of Integer Sequences indicated occurred in an apparently entirely different context, namely the $n^{th}$ term in this sequence is the least integer greater than, or equal to, (1+ sum of preceding terms)/2.

To proceed a little more systematically, we can compute those integers that require d digits:

and in each of those ranges we can examine the number of distinct patterns of the left-most digits.

What we see is that the pattern count for the first d digits of a sesquinary (d+1)-digit number is stable, but the pattern count for the whole d+1 digits is not:

What we compute, therefore, are the numbers P(d) of distinct patterns for the first d digits of an integer with d+1 sesquinary digits. That is what yields the sequence 1, 1, 2, 3, 4, 6, 9, 14, 21, 31, 47, 70, 105, 158, 237, 355, 533, 799, 1199, 1798, … which Jim Propp located, in a different context, in the Online Encyclopedia of Integer Sequences.

This sequence $a(n)$ can be calculated recursively as follows:

$a(1)=1$

$b(1)=1$

$a(n)=\textrm{Ceiling}((1 + b(n - 1))/2)$

$b(n)=b(n - 1) +a(n)$

This recursive definition of the sequence $a(n)$ allows for rapid calculation, unlike the very slow calculation that was required to produce the (apparently same) sequence 1, 1, 2, 3, 4, 6, 9, 14, 21, 31, 47, 70, 105, 158, 237, 355, 533, 799, 1199, 1798, … from the patterns of the first d digits of the representation of integers with d+1 sesquinary digits.

Glenn Whitney

Now, somewhat mysteriously, on the Online Encyclopedia of Integer Sequences page that describes the sequence $a(n)$ there is a remark by Glenn Whitney – founder of the Museum of Math – that these numbers – the $a(n)$ – are essentially the number of even integers with d+1 sesquinary digits.

Let’s see how these three equalities: $P(d+1) = a(n) =$ number of even integers with d+1 sesquinary digits – work in a few examples:

So it seems these 3 quantities are equal: the number of distinct patterns for the first d digits in integers with d+1 sesquinary digits, the recursively defined number a(d), and the number of even integers with d+1 sesquinary digits.

But why?