Functions $f:\mathbb{N}\to\mathbb{N}$ satisfying divisibility properties

Question

I recently saw and answered this question that I thought was pretty interesting. It's asking about functions $f:\mathbb{Z}^+\to\mathbb{Z}^+$ such that for all $x,y\in\mathbb{Z}^+$, there exists exactly one $k$ with $x+1\le k \le x+f(y)$ such that $y|f(k)$. In that question, they're asking to show there are infinitely many $n$ such that $f(n)=n$, but my question is what functions $f$ can satisfy this?

Repeating a bit from my answer to that question, we have that divisibility of $f$ by $y$ is a $f(y)$-periodic function, which also implies that $f(n)|f(mn)$ for all $m,n\in\mathbb{Z}^+$. We also have that $[n|f(n)]\iff f(n)=n$ and $[n|f(m)]\iff [f(n)|m]$ $(\star)$.

Letting $f(n)=k$, we have from $(\star)$ that $n|f(k)$. If we use $(\star)$ again but the other way around, we get that $f(k)|n$. Thus for all $n$, $[f(n)=k]\iff[f(k)=n]$. This also implies that $f$ is injective.

Using $(\star)$ again with $m=n$, we have that $[n|f(n)]\iff [f(n)|n]$ and since $[n|f(n)]\iff f(n)=n$, this means that $[n|f(n)]\iff [f(n)|n]\iff f(n)=n$. So if $f(n)\not=n$, $f(n)$ can be neither a multiple or divisor of $n$.

Since divisibility by $n$ is $(f(n)=k)$-periodic and divisibility by $k$ is $n$-periodic, we have that $f(\mathrm{lcm}(n,k))=\mathrm{lcm}(n,k)$.

Coming to my final questions: what are all the possible functions $f$ such that the original property holds? It's true that $f$ defined as $f(n)=n$ works, but are there other functions? Is it possible to specify all such $f$?

Edit: This is what I've found must be true of $f$:

1. $f(n)|f(mn)$
2. $[n|f(n)]\iff f(n)=n$
3. $[n|f(m)]\iff f(n)|m$
4. $f(n)|n\iff f(n)=n$
5. $f(n)=k\iff f(k)=n$
6. $f$ is bijective
7. $f(n)=k\implies f(\gcd(n,k))=\gcd(n,k)$
8. $f(n)=k\implies f(\mathrm{lcm}(n,k))=\mathrm{lcm}(n,k)$
9. $f(ag)=bg\implies f(g)|\gcd(a,b)\cdot g$
10. for $p$ prime, $f(p)=p$ or $f(p\cdot f(p))=p\cdot f(p)$
11. for $p$ prime and $f(ap)=bp$, $f(p)=p$ or [$f(p)|\gcd(a,b)$ and $f(p)\not| p$]
12. for $p$ prime, $f(p)$ must be a prime. This also implies that $f$ restricted to the primes is bijective.
13. $f$ is a multiplicative function.

I think that all multiplicative $f$ satisfying $f(p)$ prime for $p$ prime and $f(f(p))=p$ work, but I'm not sure about this.

Answer 1

Your final conjecture is necessary and sufficient: $f$ satisfies the original proposition if and only if $f$ is multiplicative and $f(f(n))=n$ for every prime $p$, $f(p)$ is prime and $f(f(p))=p$. (This also implies $f(f(n))=n$ for all $n$.) It sounds like you've already proved if $f$ satisfies the proposition, then $f$ has these properties, so I'll focus in proving an $f$ with these properties satisfies the original proposition.

One point I'll add which you didn't directly mention (though "multiplicative" implies it): The given proposition implies $f(1)=1$. (This can't be shown from periodicity, since $1$ is never an element of the set $x+1, \ldots, x+f(y)$.) Taking $y=1$, it's given the set described contains exactly one multiple of $1$, which means it must have exactly one element total, so $f(y)=1$.

Enumerate the prime numbers $p_1, p_2, \ldots$. Given a multiplicative $f$ which maps primes to primes, let $\sigma$ be the bijection on $\mathbb{Z}^+$ with $f(p_k) = p_{\sigma(k)}$. Since $p_k = f(f(p_k)) = p_{\sigma(\sigma(k))}$ for all $k$, $\sigma \circ \sigma = \mathrm{id}$.

By the prime factorization theorem, we can uniquely write any positive integer $n$ as $n = \prod_{k=1}^\infty p_k^{a_k}$ where $a_k$ are non-negative integers (and finitely many are positive). The value $f(1)=1$, the values $f(p_k)$, and the multiplicative property determine the value $f(n)$ as:

$$ f(n) = f\!\left(\prod_{k=1}^\infty p_k^{a_k}\right) = \prod_{k=1}^\infty p_k^{a_{\sigma(k)}} $$

Taking another positive integer $y=\prod_{k=1}^\infty p_k^{b_k}$, we then have

$$ f(y) = \prod_{k=1}^\infty p_k^{b_{\sigma(k)}}$$

So $y \mid f(n)$ if and only if for every positive $k$, $b_k \leq a_{\sigma(k)}$. Since $\sigma$ is a bijection, this is equivalent to $\forall k \in \mathbb{Z}^+: b_{\sigma(k)} \leq a_{\sigma(\sigma(k))} = a_k$. This in turn is equivalent to $n \mid f(y)$. Therefore it's true that for any $x$, exactly one element of $(x+1, x+2, \ldots, x+f(y))$ is a multiple of $f(y)$, and so exactly one element of $(f(x+1), f(x+2), \ldots, f(x+f(y)))$ is a multiple of $y$.

We can also describe the set of functions $f$ satisfying the proposition in terms of the corresponding bijections $\sigma$: there is a bijection between the functions $f$ and the bijections $\sigma: \mathbb{Z}^+ \to \mathbb{Z}^+$ with $\sigma \circ \sigma = \mathrm{id}$.