Does there exist a computable $\pi : \mathbb{N} \to \mathbb{N}$, bijective† and such that for all $i,j\in\mathbb{N}$ there is a $k\in\mathbb{N}$ with $$ \pi^k(i) > j, $$ and, if yes, what is a natural example?
†I'm reasonably sure that at least the inverse will have to be uncomputable, but I would need only $\pi$ itself to be computable.
A simple example is the permutation $\pi$ given by $\pi(n)=n+2$ if $n$ is even, $\pi(1)=0$, and otherwise $\pi(n)=n−2$. It should be clear that $\pi$ is computable and has the desired property.
By the way, regarding the footnote: if a bijection is computable, so is its inverse, so $\pi^{-1}$ is computable as well. In general, given a computable bijection $\sigma$, a simple algorithm to compute $\sigma^{−1}$ is as follows: Given $n$, to compute $\sigma^{-1}(n)$, compute in succession $\sigma(0),\sigma(1),\dots$, until you reach a $k$ such that $\sigma(k)=n$, which must happen since $\sigma$ is a bijection. This tells us that $\sigma^{−1}(n)=k$.