Is my sequence its own inverse?
Today I asked a question on codegolf.se about a rather elementary sequence. The sequence is defined as a function $f : \mathbb{Z}^+\setminus\{1\} \mapsto \mathbb{Z}^+ \setminus \{1\}$ where $f(n)$ is the smallest number $m$ such that the following properties are satisfied:
$\gcd(m,n) = 1$
$\nexists x < n:f(x) = m$
$\left|n-m\right| > 1$
The first couple terms in this sequence are
$$ 5,7,9,2,11,3,13,4,17,6,19,8,23,22,21,10,25,12,27,16,15,14$$
Along with the challenge to write code to calculate the sequence I also added a extra challenge to prove that $f$ was its own inverse.
Commenters verified that this was the case for the first few million values in the sequence, but no one has been able to prove that it is the case as of yet. I looked for literature, but because I made the sequence up and it has no OEIS entry I did not get very far.
What I have proven so far is that there can be no loops of size $3$, (that is $f\circ f\circ f(x)\neq x$). To prove this let us assume we have $3$ values $a$, $b$, and $c$ such that $a < b < c$. In order to have a 3 loop we need either:
\begin{equation}f(a) = b, f(b) = c, f(c) = a \end{equation}
or
\begin{equation}f(a) = c, f(c) = b, f(b) = a \end{equation}
The first cannot be the case because for $f(b)$, $a$ must satisfy all of the requirements, because $f(a)=c$ they are coprime and differ by more than 1 and because $f(b)=a$ we know that $a$ cannot have already appeared in the sequence. Thus $f(b)=a$ contradicting our earlier statement. The same reasoning can be applied to the other case.
I think this reasoning may be extensible to larger loops but I am not very sure that this is the case, and even if we prove that loops of size larger than $2$ are impossible we still have to prove that every number does loop, in order to get the result we want.
Solution 1:
Suppose $f$ is not its own inverse, i.e. $f(f(m)) \ne m$ for some $m$. Let $m$ be the least integer $> 1$ such that $f(f(m)) \ne m$.
Let $k = f(m)$, so by assumption $f(k) \ne m$. We certainly have $\gcd(m,k) = 1$ and $|m -k| > 1$, so why shouldn't $f(k) = m$?
There are only two possible reasons:
- There is some $m' < m$ that was a candidate: thus $f(k) = m' < m$.
- The value $m$ was already taken, i.e. $f(k') = m$ for some $k' < k$.
In case (1), by minimality of $m$, $f(f(m')) = m'$. But since $f(k) = m'$, we must have $k = f(m')$, and then we can't have $f(m) = k$, contradiction!
In case (2), why was $f(m) \ne k'$? It must be that $k' = f(m'')$ for some $m'' < m$. But then $f(f(m'')) = f(k') = m \ne m''$, contradicting minimality of $m$.