Preserving historical information of the Collatz function?

Question

In some sense this two equations are the same, namely $f_2$ preserves the historical information of $f_1^n$, where the exponent is function composition, but I am not sure how to show this rigorously. $f_1$ is well known,

$ f_1(s)= \begin{cases} 3s+1&\text{if}\, s \in \mathbb{N}_{odd}\\ \frac{S}{2}&\text{if } s \in \mathbb{N}_{even} \\ \end{cases} $

$f_2(s)=3s+2^{E(s)}$

where $E(s)=\max(\; b \in \mathbb{N} \cup \{0\}: \;\;2^b|s\;)$, and $$f_1^n(s)=1 \iff (f_2^m(s) \text{ is a power of two for some } m)$$

How do I show $f_1$ and $f_2$ are equivalent in this sense? Any ideas or references would be appreciated.

Edit 1:

My argument to move from $f_1$ to $f_2$ is as follows:

Represent the input $s$ in binary form. And consider $f_1^{odd}(s)=3s+1$ and $f_1^{even}(s)=\frac{s}{2}$ for odd and even inputs, respectively.

Applying $f_1^{even}$ repeatedly on the input $s_{even}$ until we obtain an output that is $s_{odd}$ to then use $f_2^{odd}(s)$ amounts to two operations:

1. Finding the first/lowest bit set on $s_{even}$ and adding one bit at that position. This is equivalent to adding $2^{E(s_{even})}$ to $s_{even}$; this will make that bit position become 0.
2. Adding $(s_{even}<<1)$ to the above computation, i.e. shifting by one to left or multiplying by two. Leaving the position where the lowest bit was set on $s_{even}$ intact.

Hence, after doing the two operations above we get, $f_2$. In particular, at all times

$$ popcount(\; f_{odd}(s) \;) = popcount(\;f_2(s) \;) $$

$$ popcount(\; f^n_{even}(s) : n = \text{ (a power until output is odd)} + 1 \;) = popcount(\;f_2(s) \;) $$

The bits that change after both operation are the same bits modulo the number of trailing zeroes; that is, in $f_2$ they are at an offset.

Hence, when the Collatz function has a one bit output, our function $f_2$ is power of two; as only powers of two have only one bit set in binary.

$ \\ \\ $

Edit 2: By convention we use $\mathbb{N}$ to mean natural numbers greater than zero.

Consider the following functions:

\begin{align} E(s) &= \max(\; r \in \mathbb{N} \cup \{0\} \; : \; \; \; 2^r\; | \;s) \\ C(s) &= \begin{cases} 3s+1&\text{if}\, s \in \mathbb{N}_{odd}\\ \frac{s}{2}&\text{if } s \in \mathbb{N}_{even} \\ \end{cases}\\ G(s) &= C^{E(s)+1}(s) \\ F(s) &= 3s + 2^{E(s)} \end{align}

By convention we define $G^0(s)=s,\;F^0(s)=s$. We make the following claims:

$\begin{align} 1.& \quad \forall s \in \mathbb{N},& 2^{E(s)}G(s) = F(s) \\ 2.& \quad \forall n,s \in \mathbb{N}, &\left( 2^{\sum_{k=1}^n E(G^{k-1}(s))} \right) G^n(s)=F^n(s)\\ \end{align}$

$ \\ $

Claim 1 Proof Suppose $s=2^ks_0$ where $s_0$ is odd. We have $E(s)=k$. We start as follows,

\begin{align*} G(s) &= C^{E(s)+1}(s) \\ G(s) &= C^{k+1}(s) \\ G(s) &= C^{k+1}(2^ks_0) \\ \end{align*}

since $2^ks_0$ is even until it is divided by $2$ a total number of $k$ times, we have

\begin{align} G(s) &= C^{1}(s_0) \\ G(s) &= 3s_0+1 \end{align}

Hence,

\begin{align} 2^{E(s)}G(s) &= 2^{E(s)}( 3s_0+1) \\ &= 2^k(3s_0+1) \end{align}

Now we calculate $F(s)$,

\begin{align*} F(s) &= 3s+2^{E(s)} \\ &= 3s+2^{k} \\ &= 3(2^ks_0)+2^k \\ &= 2^k(3s_0+1) \\ \end{align*}

Therefore, we have $ 2^{E(s)}G(s) = F(s) $.

A proof for claim 2 would get the points.

Answer 1

$\text{let } {x=E(s)} \text{ therefore } {\exists\space y\in\Bbb{N}\space}\text{|}{\space 2^xy=s}\text{ (This implies } y \text{ is odd).}$

$\text{Also let }{f_3(s)=3(\frac{s}{2^x})+1=(3y+1)}\text{.}$

${f_3\left(s\right)}\text{ is equivalent to using } {f_1}\text{ on } s \text{ until an odd step is applied.}$

$\text{So }$

$\exists\space p\space \text{|}\space f_1^p(s)=1\iff\exists\space q\space|\space f_3^q(s){=4\text{ [1]}}$

${f_3^q(s)=4 \iff f_3^{q-1}(s)=2^k} \text{ (for some k}{\in\Bbb{N})\space [2]}$

$\text{If we apply one step of } {f_2} \text{ on } {s} \text{ we have: }$

${f_2(s)=f_2(2^xy)}$ ${=}$ ${3\cdot 2^xy+2^x=2^x(3y+1)}$

${f_2(s)} \text{ is a power of two } {\iff (3y+1)} \text{ is a power of two.}$

$\text{Let} {f_4(s)=\frac{f_3(s)}{2^x}=3y+1}\text{.}$

$\text{So } {f_4(s)} \text{ is a power of two } {\iff f_2(s)} \text{ is a power of two.[3]}$

${f_4(s)=(3y+1)=f_3(s)} \text{ implies that } {f^n_4(s)=f^n_3(s)}\text{.[4]}$

$\text{The logical connection between Statements [1]-[4] shows that: }$ ${f_1^n(s)=1 \iff (f_2^m(s) }\text{ is a power of two for some m)}$

$\text{Recommended ordering [1][2][4][3] or [3][4][2][1]}$

Edit to prove claim 2:

$\text{we want to show by induction that:}$

$$\left( 2^{\sum_{k=1}^n E(G^{k-1}(s))} \right) G^n(s)=F^n(s)\Rightarrow \left( 2^{\sum_{k=1}^n E(G^{k}(s))} \right) G^{n+1}(s)=F^{n+1}(s)$$ $\text{(we already have the base case from claim 1)}$

$\text{I first want to prove an identity of the } F \text{ function. }(F(\frac{s}{2^c})=\frac{F(s)}{2^c})$

$\text{notice that } E(\frac{s}{2^c})=E(s)-c \text{.}$

$F(\frac{s}{2^c})=\frac{3s}{2^c}+2^{E(\frac{s}{2^c})}=\frac{3s}{2^c}+2^{E(s)-c}=\frac{3s+2^{E(s)}}{2^c}=\frac{F(s)}{2^c}$

$$\left( 2^{\sum_{k=1}^n E(G^{k-1}(s))} \right) G^n(s)=F^n(s)$$

$$ G^n(s)=\frac{F^n(s)}{\left( 2^{\sum_{k=1}^n E(G^{k-1}(s))} \right)}\text{ [0]}$$

$$ G^{n+1}(s)=G\left(\frac{F^n(s)}{\left( 2^{\sum_{k=1}^n E(G^{k-1}(s))} \right)}\right)\text{ [1]}$$

$\text{On the right side of [1] the input of G is divided by } 2^{E(G^n(s))}$

$\text{ then is multiplied by three then summed with one as shown in [2]}$

$$ G^{n+1}(s)=\frac{3F^n(s)}{\left( 2^{\sum_{k=1}^n E(G^{k}(s))} \right)}+1 \text{ [2]}$$

$$ 2^{E(G^n(s))}G^{n+1}(s)=\frac{3F^n(s)}{\left( 2^{\sum_{k=1}^n E(G^{k-1}(s))} \right)}+2^{E(G^n(s))}\text{ [3]}$$

$\text{the right side of [3] is equivalent to plugging in the right side of [0] in F}$

$\text{ as shown on the right side of [4]}$

$$ 2^{E(G^n(s))}G^{n+1}(s)=F\left(\frac{F^n(s)}{\left( 2^{\sum_{k=1}^n E(G^{k-1}(s))} \right)}\right)\text{ [4]}$$

$\text{using the F identity}$

$$ 2^{E(G^n(s))}G^{n+1}(s)=\frac{F^{n+1}(s)}{\left( 2^{\sum_{k=1}^n E(G^{k-1}(s))} \right)}\text{ [5]}$$

$\text{finally}$

$$\left( 2^{\sum_{k=1}^n E(G^{k}(s))} \right) G^{n+1}(s)=F^{n+1}(s)$$

Edit2 shortened proof of claim 2:

$\text{we want to show by induction that:}$

$$\left( 2^{\sum_{k=1}^n E(G^{k-1}(s))} \right) G^n(s)=F^n(s)\Rightarrow \left( 2^{\sum_{k=1}^n E(G^{k}(s))} \right) G^{n+1}(s)=F^{n+1}(s)$$

$\text{(we already have the base case from claim 1.) Claim 1 also shows that:}$

$$F(z)=G(z)2^{E(z)}\text{ (for any z }\in\Bbb{N}\text{) [1]}$$

$\text{I first want to prove an identity of the } F \text{ function. }(F(s2^c)=F(s)2^c)$

$\text{notice that } E(s\cdot 2^c)=E(s)+c \text{.}$

$F(s2^c)=3s2^c+2^{E(s2^c)}=3s2^c+2^{E(s)+c}=(3s+2^{E(s)})2^c=F(s)2^c$

$$G^n(s)\left( 2^{\sum_{k=1}^n E(G^{k-1}(s))} \right)=F^n(s)$$

$$F\left(G^n(s)\left( 2^{\sum_{k=1}^n E(G^{k-1}(s))} \right)\right)=F^{n+1}(s)$$

$\text{By the F identity}$

$$F\left(G^n(s)\right)\left( 2^{\sum_{k=1}^n E(G^{k-1}(s))} \right)=F^{n+1}(s)\text{ [2]}$$

$\text{By using [1] when } z=G^n(s),$

$\text{the } F(G^n(s))\text{ term in [2] can be substituted for } G^{n+1}(s)2^{E(G^n(s))}\text{.}$

$\text{Which gives the result:}$

$$G^{n+1}(s)\left( 2^{\sum_{k=1}^n E(G^{k}(s))} \right)=F^{n+1}(s)$$

Answer 2

I missed out on the bounty :( but the best and most compact proof of the equivalence of the two functions is the simple observation that $f_2(x)$ commutes with $2x$, i.e. $f_2(2x)=2f_2(x)$

Then for any sequence of divisions by $2$ denoted $2^{s_1},2^{s_2},\ldots:2^{s_n}\in\{2,4,8,16\ldots\}$, you have that $f_2^n(x)=\prod_n 2^{s_n}\times f_1^n(x)$

$\prod_n 2^{s_n}$ is clearly $2^{s_1+s_2+\ldots s_n}$