More on k-automatic sequences

[David W. Wilson]

For Seqfans not in the know, Jeffrey Shallit and I cowrote a paper for
the EATCS a few years ago (more precisely, I supplied the idea, Jeffrey
actually wrote and published the paper, crediting me).  The paper made
a connection between the Collatz conjecture (3x+1 conjecture) and
2-regular sets (sets of integers whose base-2 reps form a regular set
(set of strings recognized by a finite automaton).

For sequence fans not familiar with Collatz:

The Collatz function is

    f(x) =
        x/2 if x is even
        3x+1 if x is odd

The Collatz trajectory of positive integer n is the sequence of integers
obtained by repeatedly applying the Collatz function to n.  The sequence
ends if 1 is reached.  For example, the Collatz trajectory of 7 is

    (7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1)

The Collatz conjecture is that the Collatz trajectory of every positive
integer is finite, that is, repeatedly applying the Collatz function to
any positive integer eventually results in 1.  The Collatz conjecture
is a seriously tough problem which seems true, but has thus far resisted
proof.

Let S(n) be the set of positive integers having n odd integers in their
Collatz trajectories.  We then have

    S(1) = (1, 2, 4, 8, 16, 32, 64, 128, 256, 512, ...)
    S(2) = (5, 10, 20, 21, 40, 42, 80, 84, 85, 160, ...)
    S(3) = (3, 6, 12, 13, 24, 26, 48, 52, 53, 96, ...)
    S(4) = (17, 34, 35, 68, 69, 70, 75, 136, 138, 140, ...)
    S(5) = (11, 22, 23, 44, 45, 46, 88, 90, 92, 93, ...)
    S(6) = (7, 14, 15, 28, 29, 30, 56, 58, 60, 61, ...)
    S(7) = (9, 18, 19, 36, 37, 38, 72, 74, 76, 77, ...)
    S(8) = (25, 49, 50, 51, 98, 99, 100, 101, 102, 196, ...)
    S(9) = (33, 65, 66, 67, 130, 131, 132, 133, 134, 260, ...)
    S(10) = (43, 86, 87, 89, 172, 173, 174, 177, 178, 179, ...)

If the Collatz conjecture is true, each positive integer occurs in
exactly one S(n).

It is fairly easy to show that S(1) consists of the powers of 2.  In
base 2 we would write

    S(1) = (1, 10, 100, 1000, 10000, 100000, 1000000, ...)

If these base-2 representations are taken as strings, they form a
regular language described by the regular expression 10* (meaning 1
followed by any number of 0's).  A set of integers whose base-k reps
form a regular language is called a k-automatic set.  Thus S(1) is a
2-automatic set.

If we write S(2) in base 2, we get

   S(2) = (101, 1010, 10100, 10101, 101000, 101010, 1010000, ...)

which can be described by the regular set 101(01)*0* (101 followed
by any number of 01's followed by any number of 0's).  Hence S(2) is
2-automatic as well.

What Jeffrey and I showed in our paper is that all S(k) are
2-automatic.  The proof was not especially deep (I understand it
appears as an exercise in Jeffrey's new book).  I was hoping at one
time to generate the finite state machines for small S(k), to see if
there might be some structure that could be leveraged against the
Collatz conjecture, but I gave up for lack of basic tools for logical
and arithmetical manipulation of k-automatic sets.

It would be nice if Mathematica provided a k-automatic set package.
Given Wolfram's penchant for cellular automata and the like, this
would be right up his alley.