Define a permutation $\sigma:\mathbb{N}\to\mathbb{N}$ recursively by the following rule:
$\sigma(1)=1$ and $\sigma(n)$ is the least $x\ $ in $\ \mathbb{N}\setminus\{\sigma(k): k\leq n-1\}$ such that $x - \sigma(n') \neq n-n'\quad \forall n'\leq n-1.$
If we have two columns of $\mathbb{N}$ in order where the rows are equally spaced, then $\sigma:\mathbb{N}\to\mathbb{N}$ are the arrows from the left column to the right column. We already have arrows from $k$ to $\sigma(k)$ for every $k\leq n-1.$ $\sigma(n)$ is chosen to be the least integer from the remaining range with the condition that the gradient of the arrow from $n$ to $\sigma(n)$ is not the same gradient of any of the arrows before it.
It is clear that $\sigma$ is an injection. I decided to investigate $\sigma$ by writing down the first few terms of $\sigma(n)$ and using arrows to represent the function $\sigma.$
The first few terms are:
$\sigma(1) = 1,\ \sigma(2) = 3,\ \sigma(3) = 2,\ \sigma(4) = 6,\ \sigma(5) = 8,\ \sigma(6) = 4,\ \sigma(7) = 11,\ \sigma(8) = 5,\ \sigma(9) = 14,\ldots $.
Using my arrow diagram, it was not difficult to see that $\sigma$ is surjective also. But I also noticed that there was a symmetry of reflection in my diagram, and this surprised me, because I couldn't think of a good reason for this symmetry. In mathematical terms, it seems that $\sigma(\sigma(n))=n.$
My question is:
Is it true that $\sigma(\sigma(n))=n$ for all $n,$ and why is this/ how can this be proven?
As pointed out in the comments, a full proof is given here (proof of (b)) on pages $8$ and $9$.