I recently found a question that stated as follows:
Let $f:\mathbb N\to\mathbb N$ be defined as follows: $$f(n)=2n+1-2^{\lfloor\log_2n\rfloor+1}$$ and let $f^\alpha(n)=f(f^{\alpha-1}(n))$. Let $t(n)$ be the smallest positive integer such that there exists a positive integer $N$ such that $f^{t(n)}(n)=f^{t(n)+N}(n)$. Determine $$\sum^{2^{2021}}_{n=2^{2020}}f^{t(n)}(n)\pmod{1009}$$
I was able to solve the problem as follows:
First, $f(n)\leq n$. To show this, we first note that to minimize $2^{\lfloor\log_2n\rfloor+1}-n$, we want $n$ to be as close to a power of $2$ as possible without exceeding said power of $2$. This is because provided $2^a\leq n<2^{a+1}$, $2^{\lfloor\log_2n\rfloor+1}=2^{a+1}$, i.e. the value of $2^{\lfloor\log_2n\rfloor+1}$ does not change regardless of where $n$ is in the interval $[2^a, 2^{a+1}-1]$. Within this interval, we can rewrite $f(n)$ as $2n-c$ where $c=2^{a+1}-1$. Hence, we have:
$$f(n)\leq n$$ $$\Rightarrow 2n-c\leq n$$ $$\Rightarrow n\leq c$$
As $n$ is bounded above by $2^{a+1}-1=c$, this inequality is always true. We note that the equality holds when $n$ is of the form $2^m-1$ for some positive integer $m$, i.e. all integers of the form $2^m-1$ are fixed points of $f$. Finally, $N=1$. If $N=2$, then $f^{t(n)}(n)>f^{t(n)+1}(n)$ by the above inequality ($f^{t(n)}(n)\neq f^{t(n)+1}(n)$ because $N\neq1$). We also have $f^{t(n)+2}(n)=f^{t(n)}(n)>f^{t(n)+1}(n)$ by definition of $N$. However, $f^{t(n)+2}(n)>f^{t(n)+1}(n)$, a contradiction. Therefore, $N\neq2$ and if $N\neq1$, then $f^{t(n)+2}(n)<f^{t(n)}(n)$. By induction, we can show $N\neq3,4\cdots$ and hence $N=1$.
Thus, we are interested in the fixed points of $f(n)$. We first note that $f\left(2^b\right)=1$ for all positive integer $b$. This is because $f\left(2^b\right)=2\left(2^b\right)+1-2^{\left\lfloor\log_22^b\right\rfloor+1}=2^{b+1}+1-2^{b+1}=1$. We also note that $1=2^1-1$ and is hence a fixed point of $f$ Hence $f\left(2^{2021}\right)=1$ and $\sum^{2^{2021}}_{n=2^{2020}}f^{t(n)}(n)\pmod{1009}=\sum^{2^{2021}-1}_{n=2^{2020}}f^{t(n)}(n)+1\pmod{1009}$.
We can try looking at which fixed point each number in the interval $[16, 31]$ "reach" via iterated composition to find a pattern. In the below graphs, I showed the sequence formed by applying $f$ to numbers in $[16, 31]$ multiple times. Numbers in the interval $[16, 31]$ are marked with $\color{blue}{\text{blue}}$, numbers that are fixed points are marked with $\color{red}{\text{red}}$, and numbers that are both fixed points and lie in the interval $[16, 31]$ are marked with $\color{purple}{\text{purple}}$.
$$\begin{align*} &\color{purple}{31} \\ &\color{blue}{30},\color{blue}{29},\color{blue}{27},\color{blue}{23},\color{red}{15} \\ &\color{blue}{28},\color{blue}{25},\color{blue}{19},\color{red}7 \\ &\color{blue}{26},\color{blue}{21},11,\color{red}7 \\ &\color{blue}{24},\color{blue}{17},\color{red}3 \\ &\color{blue}{22},13,11,\color{red}7 \\ &\color{blue}{20},9,\color{red}3 \\ &\color{blue}{18},5,\color{red}3 \\ &\color{blue}{16},\color{red}1 \end{align*}$$
So in total, $1$ number reaches $2^5-1$, $4$ numbers reach $2^4-1$, $6$ numbers reach $2^3-1$, $4$ numbers reach $2^2-1$, and $1$ number reaches $2^1-1$. This looks suspiciously like the binomial coefficients.
This led to the following hypothesis:
Within the interval $\left[2^a, 2^{a+1}-1\right]$, the number of numbers that reach the fixed point $2^b-1$ with $b$ being a positive integer satisfying $b\leq a+1$ is $\binom a{b-1}$.
The hypothesis applied to to the interval $[16, 31]$ (as shown above) and $[8, 15]$. Not wanting to spend too much time on this problem, I decided that I was going to assume this hypothesis was true.
Hence,
$$\sum^{2^{2021}-1}_{n=2^{2020}}f^{t(n)}(n)=\sum^{2020}_{k=0}\binom{2020}k2^{k+1}-1=2\sum^{2020}_{k=0}\binom{2020}k2^k-\sum^{2020}_{k=0}\binom{2020}k$$
Applying Binomial theorem, we know $\sum^{2020}_{k=0}\binom{2020}k2^k=(1+2)^{2020}=3^{2020}$ and $\sum^{2020}_{k=0}\binom{2020}k=2^{2020}$. We also note that $1009$ is prime, and thus we can use Fermat's little Theorem.
Thus,
$$\sum^{2^{2021}-1}_{n=2^{2020}}f^{t(n)}(n)+1\pmod{1009}=2\cdot 3^{2020}-2^{2020}+1\pmod{1009}=2\cdot \left(3^{1009}\right)^2\cdot 3^2-\left(2^{1009}\right)^2\cdot 2^2+1\pmod{1009}=2\cdot3^2\cdot3^2-2^2\cdot2^2+1\pmod{1009}=2\cdot3^4-2^4+1\pmod{1009}=162-16+1\pmod{1009}=147\pmod{1009}$$
Though $147$ is the correct answer, my solution does not feel very satisfying. I had to assume my hypothesis was true and in the end I still am not sure why this hypothesis applied. Therefore, I would like to ask why my hypothesis is true, i.e.
Let $f:\mathbb N\to\mathbb N$ be defined as follows: $$f(n)=2n+1-2^{\lfloor\log_2n\rfloor+1}$$ and let $f^\alpha(n)=f(f^{\alpha-1}(n))$. Let $t(n)$ be the smallest positive integer such that $f^{t(n)+1}(n)=f^{t(n)}(n)$. Show that, $\forall a\in\mathbb{Z}_+\forall b\in\mathbb{Z}_+$ s.t. $b\leq a+1$, we have $|\{n\in \mathbb{Z}, n\in[2^a, 2^{a+1}-1]: f^{t(n)}(n)=2^b-1\}|=\binom a{b-1}$
(Note: This answer uses binary numbers)
This answer provides an interesting perspective on the definition of $f(n)$ and how we should think of $n$.
Essentially, suppose $n$ is a binary string and the digit $1$ of $n$ appears $y$ times at $a_1, a_2, \cdots, a_y$, i.e.
$$n=\sum^y_{k=1}10^{a_k}$$
We know $f(n)=10n+1-10^{\left\lfloor\log_{10}n\right\rfloor+1}$. We note that $\left\lfloor\log_{10}n\right\rfloor+1$ is the position of the largest digit in $n$, plus $1$.
So we have:
$$f(n)=10\sum^y_{k=1}10^{a_k}+1-10^{a_y+1}=\sum^{y-1}_{k=1}10^{a_k+1}+\sum^0_{k=0}10^k$$ $$f^2(n)=10\sum^{y-1}_{k=1}10^{a_k+1}+10\sum^0_{k=0}10^k+1-10^{a_{y-1}+2}=\sum^{y-2}_{k=1}10^{a_k+2}+\sum^1_{k=0}10^k$$ $$\vdots$$ $$f^m(n)=\sum^{y-m}_{k=1}10^{a_k+m}+\sum^{m-1}_{k=0}10^k, m<y$$ $$\vdots$$ $$f^y(n)=\sum^{y-y}_{k=1}10^{a_k+y}+\sum^{y-1}_{k=0}10^k=\sum^{y-1}_{k=0}10^k=10^y-1$$ We note that $10^y-1$ is a fixed point of $f$. Therefore, $t(n)=y$ and $f^{t(n)}(n)=10^y-1$.
My conjecture earlier asks about numbers in the interval $[10^a, 10^{a+1}-1]$. This is equivalent to asking about asking about all $a+1$ digit numbers.
We know that, for $f^{t(n)}=10^b-1$, $n$ must contain exactly $b$ $1$s (and $a-b+1$ $0$s), and the first digit must be $1$, so there are in total $\frac{(b-1+a-b+1)!}{(b-1)!(a-b+1)!}=\binom a{b-1}$ such $n$. Therefore the conjecture is correct.