The Collatz Conjecture or 3x+1 problem states that applying the function $$ f(x) = \left\{ \begin{array} & \frac{x}{2} & x \text{ even} \\ \frac{3x + 1}{2} & x \text{ odd} & \end{array} \right.$$ to any $x \in Z^{+}$ will, after repeated aplication, eventually converge to 1. Assuming the conjecture to be true we can create a novel binary numbering system.
First let's look at the base-2 number system. Take any number and apply the following function: $$ f(x) = \left\{ \begin{array} & \frac{x}{2} & x \text{ even} \\ \frac{x - 1}{2} & x \text{ odd} & \end{array} \right.$$
If every time we land on an even number we encode it as $0$ and every time we land on an odd number (greater than 1) then we encode it as $1$ then it can be seen that the sequence of $0$s and $1$s generate a string representing the base-2 binary encoding of the original value, in reverse order. For example take the number 5: 5 is odd so encode a $1$, apply $f(x)$ to obtain 2 $\to$ 2 is even so read off $0$ and apply $f(x)$ to obtain 1 $\to$ 1 is final value and odd so read off $1$ and stop. We have generated the string $101_{2}$ which is indeed the binary representation of 5.
This works by reading off a $1$ or a $0$, shifting and repeating. All values will eventually end at 1 when the most significant digit has been reached. The following function shows the procedure.
def encodeBinary(n):
x=n
str=''
while x!=1:
if x%2==0:
x = x>>1
str += '0'
else:
x = (x-1)>>1
str += '1'
str += '1'
return str[::-1] # reverse
print(encodeBinary(5))
101
In a similar way, if we believe the Collatz Conjecture, then all positive integers can be reached by the $3x+1$ variant by applying the same procedure. For example let's start at 5 again: 5 is odd so read off $1$ apply $f(x)$ to obtain 16 $\to$ 16 is even so read off $0$ and apply $f(x)$ to obtain 8 $\to$ 8 is even so read off $0$ and apply $f(x)$ to obtain 4 $\to$ 4 is even so read off $0$ and apply $f(x)$ to obtain 2 $\to$ 2 is even so read off $0$ and apply $f(x)$ to obtain 1 $\to$ 1 is final vaue and odd so read off $1$ and stop. We have generated the string $10001_{collatz}$ which is the Collatz binary representation of 5.
def encodeCollatz(n):
x=n
str=''
while x!=1:
if x%2==0:
x = x>>1
str += '0'
else:
x = (3*x+1)>>1
str += '1'
str += '1'
return str[::-1] # reverse
print(encodeCollatz(5))
10001
What's the use of this? I have absolutely no idea. It's obviously not an efficient encoding; the length of the encoded string is the length of the trajectory of the number to 1 which could be large for relatively small starting values.
I'm wondering if there would be some way of representing the distance between numbers in this encoding as a metric on the encoding space and investigating the geometry. Maybe that would be a way of investigating the conjecture itself.