Number of integer functions satisfying three constraints I am trying to understand how many functions $\mathbb{Z^+}\to \mathbb{Z^+}$ which satistfy the three following constraints exist:


*

*For every $n \in \mathbb{Z^+}$
$$f(f(n))\leq\frac{n+f(n)}{2}$$

*For every $n \in \mathbb{Z^+}$
$$f(n)\leq f(n+1)$$

*For every $(n,m)\in \mathbb{Z}^{+}\times\mathbb{Z}^+ $ such that $n \neq m$ 
$$\text{GCD}(f(n),f(m))=1$$
One of these functions is indeed $f(n)=1$ for every $n \in \mathbb{Z}^+$, but any other constant function does not satisfy the third constraint, which is probably the strongest. 
My first intuition about other functions was something on the lines of $f(n)=\text{the n-th prime number}$, but this functions (or any of its multiples) does not satisfy the first constraint, already for $n=2$. 
Are there any other functions that satisfy these constraints? How can they be found?
 A: The constant function $f(n)=1$ is indeed the only solution, even if we weaken the first condition to: $f(f(n)) \le C(n+f(n))$ for some fixed $C>0$ (no matter how large).
As a proof-of-concept, we prove: there is no such solution with $f(1)>1$. Note that if $f(1)>1$ then $f(n+1)>f(n)$ (strictly) for all $n$, because of the gcd condition. In particular, $f(n)>n$; so it suffices to show there is no solution even if we replace $f(f(n)) \le C(n+f(n))$ by $f(f(n)) \le 2Cf(n)$. To do so, it suffices to show that $\lim_{k\to\infty} \frac{f(k)}k = \infty$.
Each of the values $f(1),\dots,f(k)$ is divisible by at least one prime, and these primes are distinct by the gcd condition; therefore $f(k)$ is at least as large as the $k$th prime. In particular, $f(k) > k\ln k$ by Rosser's theorem, and so indeed $\lim_{k\to\infty} \frac{f(k)}k = \infty$.
This shows that there is no such solution with $f(1)>1$. To consider any solution with $f(1)=1$: If $f(n)$ is not constant, then choose $K$ such that $f(K+1)>1$, and redo the above proof with the values $f(K+1), \dots, f(K+k)$ instead of $f(1),\dots,f(k)$.
A: Suppose $\exists n$ so that $f(n) \gt n$. Then, from the second condition we get:
$$
f(f(n)) \ge f(n) \tag 1
$$
and, using (1) and the first condition:
$$
f(n) \le f(f(n))\leq\frac{n+f(n)}{2} \tag 2
$$
from (2) we get:
$$
f(n) \le \frac{n+f(n)}{2} \tag 3
$$
which contradicts our assumption $f(n) \gt n$.
We just proved that $f(n) \le n, \forall n$. 
Now let's suppose there is $m$ so that $f(m)>1$. We have 
$$ n \ge f(n) \ge f(m) \gt 1, \forall n \gt m \tag 5$$
and because of the third condition:
$$ n \ge f(n) \gt f(m) \gt 1, \forall n \gt m \tag 6$$
We can also extend (6):
$$
n \ge f(n)\gt f(n -1)\gt f(n -2)\gt .. \gt  f(m + 1) \gt  f(m) \tag 7
$$
Let's define $A = \lbrace f(m+1),f(m+2), .. ,f(n) \rbrace$ and $B=\lbrace f(m) + 1, .. ,n \rbrace$
Then A has $n-m$ elements, B has $n-f(m)$ elements  and $A \subset B$.
Let's take $n$ so that $n > (m+1)f(m) \tag 8$ 
Because of the third condition, all multiples of $f(m)$ are not in $A$, therefore we can define $C=B\setminus\lbrace kf(m)| 2 \le k \le m + 1  \rbrace$ and still having: $$A \subset C \tag 9$$
But $C$ has $n - f(m) - m$ elements while A has $n-m$ elements, so the inclusion (9) is not possible, therefore the assumption there is $m$ so that $f(m)>1$ is false.
