Consider the below function: $$f(x)=2x+1-2^{\lfloor \log_2x\rfloor+1}$$ Let $f^x(x)$ refer to the composition of $f(x)$, $x$ number of times.
Now after having observed some patterns, I've hypothesized that: $$f^x(x)=2^y-1$$ Where:
- $x=2^{a_1}+2^{a_2}\cdot \cdot + 2^{a_y}$
- $\{a_1,a_2\cdot\cdot\cdot\cdot a_y\}$ All elements in this set are distinct, and $\in \{Z^++\{0\}\}$ (i.e. belong to the set of non-negative numbers).
- $x \in Z^+$
How can I go about proving this?
Short version: if you use binary numbers, then your function removes the leading bit, shifts all remaining bits up by $1$, and adds a $1$ to the ones place. With this understanding, your observation is clear.
For example, with $n=37$, in binary that is $100101$ with $y=3$. And applying the sequence I described above: $$\color{blue}100\color{magenta}10\color{green}1\to\color{magenta}10\color{green}11\to\color{green}111\to111\to\ldots\to111=1000-1$$
All numbers below are in binary (except the ones in the limits of summation and in the exponents).
Your function is $$f(x)=10x+1-10^{\lfloor\log_{10}x\rfloor+1}$$ Let $n$ be an integer. So $n=\sum_{k=1}^y10^{a_k}$. Then $$\begin{align} f(n)&=\sum_{k=1}^y10^{a_k+1}+1-10^{a_y+1}=\sum_{k=1}^{y-1}10^{a_k+1}+1\\ f(f(n))&=\sum_{k=1}^{y-1}10^{a_k+2}+10+1-10^{a_{y-1}+2}=\sum_{k=1}^{y-2}10^{a_k+2}+10+1\\ f^{3}(n)&=\sum_{k=1}^{y-2}10^{a_k+3}+100+10+1-10^{a_{y-2}+3}=\sum_{k=1}^{y-3}10^{a_k+3}+100+10+1=\sum_{k=1}^{y-3}10^{a_k+3}+\sum_{i=0}^210^i \end{align}$$ This can continue, inductively. Note that the largest term here is in the first sum, so the floored logarithm will always be defined from that. This gives $$f^m(n)=\sum_{k=1}^{y-m}10^{a_k+m}+\sum_{i=0}^{m-1}10^i$$ for $m\leq y$. This eventually brings you to $m=y$: $$f^{y}(n)=\sum_{i=0}^{y-1}10^i=10^y-1$$ which is not quite what your statement says.
But if you keep going from here: $$\begin{align} f(f^{y}(n))&=10^{y+1}-10+1-10^y\\ &=(10^{y}+10^y)-(1+1)+1-10^y\\ &=10^{y}-1 \end{align}$$ So at this point further composition with $f$ fixes the output. Since $n>y$, this gives you $$f^{n}(n)=10^y-1$$ as stated.