The following is a nearly verbatim copy of a letter received from Oleg Dopertchouk on October 11, 2004, reproduced here with his permission. I don't think my minor editing has spoiled anything in it.

I have noticed you looked at the (*3x+3^n*) sort of
sequences, here is a result which you might find useful in your
further explorations.

Basically, the *3x+3^n* sequences are images of the basic
*(3x+1*) sequence under scaling.

More specifically: We'll call a function f:Z->Z a Collatz
function, if it has a form: *f(x)= x/2* if * x* is even
and *a*x+b* otherwise.

Since I'll be referring to those a lot, I'll denote such a
function f(x)=[a,b]. I'll sometimes refer to *a* as the
multiplication coefficient and *b* as the addition coefficient.

For example

[3,1] is the standard functionx->(3*x+1)/2^n[3,5] is the functionx->(3*x+5)/2^nand so forth.

We'll consider transformations between Collatz functions, a
standard trick in math. A function H:Z->Z is a
Collatz-morphism (or simply a morphism) between
Collatz-functions *f* and *g* iff

g(H(x)) = H(f(x)) for allx

Some simple examples of Collatz-morphisms:
trivial function id: *x->x*
any power of a Collatz-function gives rise to a Collatz-morphism:

f^n(f(x))=f(f^n(x))

A particularly interesting case is a morphism:
S_{k} : *x->k*x* , where *k* is some positive integer.

Theorem: For any odd integer *k* and any Collatz-function
f=[a,b], the function S_{k}: *x->k*x* is a
morphism S_{k}: f->g where g=[a,b*k]

Consider what *f* does to different sorts of numbers:

ifxis even,x=2*nthenf(x)=x/2

And
g(S_{k}*(x))=x*k=(x/2)*k*

and
S_{k}*(f(x))=k*(x/2)*=g(S_{k}(*x*))

Note that g(S_{k}(*x*))=*(x/2)*k* is odd iff
*f(x)=x/2* is odd, because k is odd (by assumption).

On the other hand:
if *x* is odd *f(x)=a*x+b*

g(S_{k}(x)) = a*k*x+k*b = k * (a*x+b)= S_{k}(f(x))

Again, g(S_{k}(*x*)) is odd iff *f(x)* is odd.

In other words, scaling by factor *k* transforms the
Collatz function [a,b] into another Collatz function
[*a,b*k*], for instance

[3,1] produces a sequence:

10->5->16->8->4->2->1while [3,5] produces a sequence

50->25->80->40->20->10->5

which is, of course, the same sequence multiplied by 5.

This theorem can help us explore the universe of
Collatz-functions. For example, if we consider a sequence [a,b]
and at some point we encounter a number *x* that is a multiple of b:
*x=y*b* , then we can immediately know how the sequence will behave
later on. It's the same way as the sequence [a,1] starting from
the number *y*. For an example let's take the sequence [3,3] starting from
22:

22->11->36

Now, 36 is 12*3 and so we can tell that from now on the sequence will behave just like [3,1] starting from 12 (with an additional factor of 3).

[3,1]: 12->6->3->10->5->16->8->4->2->1 [3,3]: 36->18->9->30->15->48->24->12->6->3

In fact, we can say even more than that. Since *3x+3 =
3(x+1)* it follows that we will reach a multiple of 3 the very first
multiplicative step. So, if we disregard the first series of
divisions by 2 and the initial multiplicative step, then we can
say that [3,3] is isomorphic to [3,1]. The same holds true,
of course, for any Collatz-function of the form [3,3*k].

Slightly more generally, if we take sequence [*p*k,q*k*]
(that is *x->(x*p*k+q*k)/2^n)* then after the very
first mutiplicative step we get *x*p*k+q*k*, which is the
image of *x*p*k+q* under Collatz morphism *x->k*x*. From
this point on the sequences [*p*k,q*k*] and [*p*k,q*] move in
step. This means that the only "interesting" functions are those
where the coefficients are relatively prime. All others can be
converted to those using the scaling trick.

There is one more observation along these lines. If *a* and *b* are
relatively prime and odd, then consider odd *x* , such
that *x* has a common factor with *b (b>1), x=p*k,
b=q*k*. As we have noted above, subsequent values of *x
*can be generated using the system [a,q] with scaling *k*,
but how could we get to such an *x* in the first place?
Division by 2 couldn't have produced it, it only removes factors
of 2. The previous multiplicative step should have been:

a*y+b = x*2^nora*y+q*k = k*p*2^nsoa*y = k*p*2^n-q*k=k*(p*2^n-q)

Since *a* and *b* are relatively prime, the factor
of* k* can only come from y. So this means the common factor
is "conserved" by the function. In other words, if
*b=k*q* then {*k*i*}=kZ forms a set closed under the action of the
function [a,b] **and** under the action of the inverse function
[a,b]^-1. (It is not really a function, since it has countably
many values, but all these values only differ by the factor of 2
and they all belong to the set). This is an analog of a notion of
a sub-group, sub-algebra, etc. Everything that
happens on that set can be derived from behavior of a Collatz-function
[*a,b/k*] with smaller coefficients. By throwing away such
"uninteresting" subsets we are left with a set S all elements of which
are relatively prime with *b*. It is the only one worth
investigating (assuming we have already explored all functions
with smaller coefficients).

Best regards,

Oleg Dopertchouk

In a separate e-mail on March 16, 2005 Oleg calls another transformation to our attention:

The Collatz system 3x+1 is linear conjugate (meaning can be
mapped via a
linear transformation y=px+q) to a collatz-like system:

f(y)={(ay+b)/2 if y is even, (cy+d)/2 if y is odd)},

(where parameters
a,c,d are assumed to be odd and b is assumed even, because otherwise
the function is rather trivial).

iff a=1, b=q, c=3 d=p-q or a=3, b=p-q, c=1, d=q

The reference is to a paper by K. Monks.

Collaz Home Page Index to Terms Used