An idea on the Collatz problem I am using the T-version of the function:
$$
T(x)=\left\{\begin{array}{cl}
\text{down}(x)=x/2,& \mbox{x even}\\
\quad\,\,\,\text{up}(x)=(3x+1)/2,& \mbox{x odd}\end{array}\right.
$$
I will also make use of the iterating function $G(x,0)=x,G(x,1)=T(x),G(x,2)=T(T(x)),...$
The goal is to get an idea about when the T increases or decreases it's argument. Let's fix some $n\in \mathbf{N}$ constant for the moment and define
$$
\mathbf{A}=\{2^n+k,k=0,1,\dots,2^n-1\}
$$
ie the set of all the integers from $2^n$ to $2^{n+1}-1$.
Now let's define a word to be a sequence of zeroes and ones of length $n$. Finally Let's denote by $\mathbf{W}$ the set of all distinct words. Every $x \in \mathbf{A}$has an "address" in $\mathbf{W}$ which we denote by $path(x)$, given by 
$$
path(x)=\{x,T(x),G(x,2),...G(x,n-1)\} \pmod{2}
$$
Now here is the punch line: There is a $1-1$ correspondence between the set of numbers $\mathbf{A}$ and the set of words $\mathbf{W}$, given by the path function. Once we establish that we will have to deal with words instead of numbers which might prove to be more informative.
How to show that? First of all note that both sets have $2^n$ elements. So if we can show that the path function is invertible we are done. Equivalently that every word $w \in \mathbf{W}$ has a unique element $a \in \mathbf{A}$ with $path(a)=w$. Equivalently $path(a)=path(b) \Rightarrow a=b$. Here is where I need help because the words are not in standard order, they come scrambled!. Take a look:
For $n=1$:
$\mathbf{A}=\{2,3\}$, $path(\mathbf{A})=\{0,1\}$
For $n=2$:
$\mathbf{A}=\{4,5,6,7\}$, $path(\mathbf{A})=\{00,10,01,11\}$
For $n=3$:
$\mathbf{A}=\{8,9,10,11,12,13,14,15\}$, $path(\mathbf{A})=\{000,101,010,110,001,100,011,111\}$
I have checked it for up to $2^8$ and it holds. No word is repeated, so I am convinced it's true.
For any $x \in \mathbf{N}$ now we find the corresponding $n$ (which is basically $[\log{x}]$), the $\mathbf{A}$ set and then we find the path, so the path function is defined over all of $\mathbf{N}$.
The power of the words representation: $1101001$ means go up twice, go down, go up, go down twice and go up. There are many interesting questions to ask: Can this be a non-trivial cycle? Conversely, given any word $w$, can it belong to a non-trivial cycle? Must there be more ones than zeroes in a non-trivial cycle? Is there an upper bound or lower bound on the fraction of number of ones over the number of zeroes?
I guess you can say that I am asking too many questions, but the only answer I really need is this $1-1$ correspondence. I can't crack it but I bet some group theorist out there can help. Many thanks in advance.
 A: Your work here seems similar to that of Everett's "Iteration of the Number-Theoretic Function" (1977); there is also a similar paper by Terras - "A stopping time problem on the positive integers" (1976). Both Terras and Everett prove a $1 - 1$ correspondence between the numbers from $1$ to $2^n$, and the set of binary numbers with n digits; from that, one could make a corollary to the $1 - 1$ correspondence you're looking for.
Everett uses a proof by induction, which should work for what you're looking for as well.
A: Definition/Notation:
$$
T(x)=\left\{\begin{array}{cl}
\text{down}(x)=x/2,& \mbox{x even}\\
\quad\,\,\,\text{up}(x)=(3x+1)/2,& \mbox{x odd}\end{array}\right.
$$
$$
G(x,0)=x,G(x,1)=T(x),G(x,2)=T(T(x)),...
$$
$$
\text{orbit}(x,n)=(x_0,x_1,\dots x_{n-1}),\ x_k=G(x,k)
$$
$$
\text{parity}(x,n)=(\bar x_0,\bar x_1, \dots \bar x_{n-1}),\ \bar x_k=x_k \mod 2,
$$
$$
A_n=\{0,1, \dots, 2^n-1\}
$$
$$
B_n=\{0,1\}^n=\{(w_1,w_2, \dots, w_n),w_k \in\{0,1\}\}
$$
$P(N)$: For any N-long dyadic word $w \in B_N$ there exists a unique $a \in A_N$ such that
$$
w=\text{parity}(a,N).
$$
THEOREM: $P(N)$ is true for all $N \in \mathbf{N}$.
Thus the parity function defines a natural bijection between $A_N$ and $B_N$.
PROOF: by induction on $N$.
Proving $P(1)$: $A_1=\{0,1\}, B_1=\{0,1\}$, $\text{parity}(0,1)=(0)\ \text{and}\ \text{parity}(1,1)=(1)$ which is trivial.
Assuming $P(N)$, we have to show that the words $\{ \text{parity}(x,N+1),x \in A_{N+1}\}$ are all distinct. The words $\{ \text{parity}(x,N),x \in A_N\}$ are all distinct by the induction hypothesis. The same must hold for the words $\{ \text{parity}(x,N+1),x \in A_N\}$ of length $N+1$ since they are extensions of the corresponding words of length $N$. 
Now we need to compute the words $\text{parity}(x,N+1)$, for $x=2^N,2^N+1, \dots, 2^{N+1}-1$. In other words we need to find $\text{parity}(x+2^N,N+1)$, for each $x \in A_N$. 
Lemma: If $x \in A_N$ and $y=x+2^N$ then
$$
\bar y_k=\bar x_k \text{ for } k=0,1,\dots,N-1 \text{ and } \bar y_N=1-\bar x_N
$$
That follows from the fact that for $k=0,1,\dots,N$,
$$
y_k=x_k+3^{S_k}2^{N-k},\ S_k=\sum_{i<k}{\bar x_i}
$$
which can be proved by induction: 
Suppose first that $k=0$. Then $S_k=0$ and we have $x_0=y_0+3^02^N$ which holds since $x_0=x$ and $y_0=y$.
Assuming it holds for some $k<N$. Consider the two cases:
1) $\bar x_k=0.$ Then $S_{k+1}=S_k,\ x_k$ and $y_k$ are both even. We now have 
$$
y_{k+1}=\frac{y_k}{2}=\frac{1}{2}(x_k+3^{S_k}2^{N-k})=x_{k+1}+3^{S_{k+1}}2^{N-(k+1)}
$$
2) $\bar x_k=1.$ Then $S_{k+1}=S_k+1,\ x_k$ and $y_k$ are both odd. In this case
$$
y_{k+1}=\frac{3y_k+1}{2}=\frac{1}{2}(3x_k+3^{S_k+1}2^{N-k}+1)=x_{k+1}+3^{S_{k+1}}2^{N-(k+1)}
$$
which completes the induction step. Once this has been established it's easy to see that
$$
y_k\mod 2=x_k \mod 2,\ k=0,1,\dots,N-1,\ x_N \mod 2 \ne y_N \mod 2,
$$
which implies the Lemma.
Hence $\text{parity}(x,N+1)$ and $\text{parity}(y,N+1)$ agree on all but the last bit which is flipped, which implies $P(N+1)$ and completes the proof of the Theorem.
