The answer is $k \ge 2$. For mod $2$ reasons, it is easy to check that $k=1$ fails. Now we construct a function $f$ for which $\gcd(fn+m, fm+n) \le 2$ for all $m \neq n$. We select our function $f$ of the form \[ f(n) = 2^{g(n)} - n - 1 \]for some large $g$, determined recursively by $g(1) = 1000$, and $g(k+1) = 1 + \left( 1000^{g(k)} \right)!$. Now, assume $n > m$ and define \begin{align*} A &= fn + m = 2^{g(n)} - n + m - 1 \\ B &= fm + n = 2^{g(m)} - m + n - 1 \\ \implies A+B &= 2^{g(m)} + 2^{g(n)} - 2. \end{align*}Since $A+B \equiv 2 \pmod 4$, $4 \nmid \gcd(A,B)$. Now, suppose $p \mid B$ is an odd prime, hence $p \le B < 1000^{g(n-1)}$. Consequently, $g(n) \equiv 1 \pmod{p-1}$. So by Fermat's theorem, we obtain $A+B \equiv 2^{g(m)} \pmod p$, hence $p \nmid A+B$, which concludes the proof.

Answer: Such $k$-good functions exists for all $k\ge 2$ only. First we claim that there is no $1$-good function. If there exist $m\neq n$ with $m, f(m)$ has same parity, and $n, f(n)$ has same parity, then $\gcd(f(m)+n, f(n)+m)$ is even, false. Then we can find two distinct $m, n$ with $m,f(m)$ has different parity and $n, f(n)$ has different parity, but then $\gcd(f(m)+n, f(n)+m)$ is still even, false. Now we construct a $2$-good function. Take $f(m)=g(m)-m$, then we want to evaluate $d=\gcd(g(m)-m+n, g(n)-n+m)=\gcd(g(m)-m+n, g(m)+g(n))$, and we want to make $d\le 2$ for all $m,n \in \mathbb{N}$. First let us restrict $v_2(d)$. We may achieve this by defining $g(m)=2^{h(m)+1}-1$. Then $d|2^{h(m)+1}+2^{h(n)+1}-2$, but $4\nmid 2^{h(m)+1}+2^{h(n)+1}-2$ because $h(m), h(n) \ge 1$. So $v_2(d)\le 1$. Now we define $h$ inductively. Set $h(1)=1$. Suppose we can define $h(1), h(2), \cdots h(k)$ for some $k$, it suffices to find $h(k+1)$ such that in the original function $f$, $\gcd(f(k+1)+m, f(m)+k+1) \le 2$ for all $m\le k$. Till this end, set $D=\max\{2^{h(i)+1}-i+(k+1)-1\}$ for all $1\le i\le k$, then if $p\mid g(m)-m+(k+1)=2^{h(m)+1}-m+(k+1)-1$, then $p\le D$. Take $Q$ to be the product of all odd primes at most $D$, then take $h(k+1)=\phi(Q)$. We claim that this choice works. Indeed, if $p|2^{h(m)}+2^{\phi(Q)}-1$, then since $p\le D$, then $p\mid Q$, so $p\mid Q\mid 2^\phi(Q)-1 \Rightarrow p\mid 2{h(m)} \Rightarrow p=2$. So $d=\gcd(m+f(n),n+f(m))$ will not have odd prime factors, and $v_2(d)\le 1$, thus $d\le 2$. So this function is $2$-good, as desired.

This is my problem! (James Rickards, Canada) Until I saw the official solutions, I didn't know of an explicit function $f$ which worked (like in v_Enhance's solution). A first approach to solving the problem (it was what I did initially at least) might take the form: set $f(1)=1$, and define $f$ recursively. Let $P$ be the set of odd primes and $4$, and assume $f$ has been defined up to $f(m-1)$. Let $S=\{p\in P \text{ such that } p\mid f(n)+m,\text{ some } n<m\}$. Then, using CRT define: \begin{align*} f(m)\equiv f(m-p) \pmod{p} \text{ for } p\in S, p<m\\ f(m)\equiv 0 \pmod{p} \text{ for } p\in S, p\geq m\\ \end{align*}This construction almost works, if $p\mid \gcd(f(m)+n,f(n)+m)$, then $p\in S$, so if $p\geq m$ then $p\mid n$, so $p\leq n< m\leq p$ contradiction. So $p<m$, and induction on the pair $(m-p,n)$ gives a contradiction, so the $\gcd$ is $1$ and you are done! So what went wrong? The (quite easy to miss) problem is the case $n=m-p$, for then you can't use induction that $\gcd(f(m-p)+n,f(n)+m-p)=1$ (this is of course equal to $f(n)+n$ when $m-p=n$). Unfortunately this can't be resolved very easily as is, but if you go back and be more careful with residues and your definition of $f$, then you can modify this approach into a solution (make sure the set $f(n)+n$ does not take up too many residue classes modulo $p\in P$).

The answers are all $k\geq 2$. We first show that there is no $1$-good function. Indeed, we show that for all function $f:\mathbb Z_{>0}\to\mathbb Z_{>0}$ there exists $m,n$ such that $$f(m)+n\text{ and }f(n)+m$$are both even. This is not hard. Notice that if $f(1),f(3)$ is both odd then $f(1)+3,f(3)+1$ is both even, therefore, $f(1),f(3)$ cannot both be odd, similarly $f(2),f(4)$ cannot both be even. WLOG assume $f(1)$ is even while $f(2)$ is odd then $f(1)+2$ and $f(2)+1$ are both even as desired. We now show that there is a $2$-good function. Let $P$ be the union of the set of odd primes and $4$. It suffices to show that there exists a function $f$ such that $$p\nmid (f(m)+n,f(n)+m)$$for all $m\neq n$ and $p\in P$. We will strengthen the condition such that $f(n)+n$ is a prime for all $n$ and that $f(n)+n$ is injective. We define $f$ recursively. Define $f(1)=1$, $f(2)=3$. Now suppose we have define $f(1),f(2),...,f(n-1)$, we will assign a value for $f(n)$. We will do so by showing that given $p\in P$ there exists $0\leq g_p(n)\leq i$ such that $$p\nmid (f(m)+n,g(p)+m)$$for every $1\leq m\leq n-1$. Then by Chinese Remainder Theorem we can take $f(n)\equiv g_p(n)\pmod p$ for all $p\in P$. If $p=3$ we can take $$g_3(n)\equiv 2n-1\pmod 3$$If $p=4$ we can take $g_4(n)=2,1,3,2,3$ for $5\leq n\leq 8$ and extend it periodically with period $4$. Let $P_s$ be the set of elements in $P$ smaller than $n$. Suppose $p\in P_s$, we call $p$ bad if $$f(n-p)\equiv -n\pmod p$$and good otherwise. Notice that if $p$ is good, then we can let $f(n)\equiv f(n-p)\pmod p$, then if $m<n$ we have $$(f(n)+m,f(m)+n))\equiv (f(n-p)+m,f(m)+n-p)\not\equiv 0\pmod p$$So we can just take $g(p)\equiv f(n-p)\pmod p$. Now suppose $p$ is bad. Since $f(m)+m$ is a prime by inductive hypothesis, for each $p$ there exists exactly one integer $n$ such that $n$ is bad. Therefore, we have $n<2p$ and $f(m)\equiv f(m-p)\pmod p$ for all $m=p+1,...,n-1$. Therefore, at most $n-2$ of the following numbers $$\{f(1)+n,f(2)+n,...,f(n-1)+n\}$$will be equal to $0\pmod p$ (since $f(1)+n\not\equiv f(2)+n\pmod p$). Therefore suppose $p\nmid f(i)+n$ we can just take $g_p(n)\equiv -i\pmod p$. If $p\in P$ and $p\geq n$ then again the following $n-1$ $$\{f(1)+n,f(2)+n,...,f(n-1)+n\}$$contain at most $n-2<m-1$ multiples of $p$, so suppose $p\nmid f(i)+n$ we can just take $g_p(n)\equiv -i\pmod p$. This completes the proof. Bacteria wrote: This is my problem! (James Rickards, Canada) Congratulations on finding such an amazing problem! It turns out that my idea is exactly the same as yours. I try to construct the function recursively using the quite obvious way (CRT with $f(m)\equiv f(m-p)$ for every prime. But indeed I find out that it is impossible due to the case $n=m-p$. So basically all my wordy explanation is try to avoid that case.

The answer is $\boxed{k\ge2}.$ If we have two integers $m,n$ of different parities where $f(m), f(n)$ have different parities than $m,n$ respectively, then $2 \mid \gcd(f(m)+n, f(n)+m).$ Otherwise, there exists two integers $m,n$ of the same parity where $f(m), f(n)$ also have that same parity. Then $2 \mid \gcd(f(m)+n, f(n)+m)$ still. It suffices to construct a $2$-good function, we construct this inductively. Let $f(1) = 2^2-1-1=2.$ Suppose we have constructed valid $m$ up to a certain $n.$ Then consider an integer $C$ larger than $f(m) + n$ for any $m < n.$ Then set $f(n) = 2^{C! + 1} - n-1.$ For any positive integer $m < n,$ we have $$f(m) + n + f(n) + m \equiv 2^{C!+1} + 2^{c} - 2 \equiv 2 \pmod{4}$$where we assume to have set $f(m) = 2^{c} - m - 1$ earlier, so $4$ does not divide the gcd. Also if prime $p$ divides $f(m) + n,$ then $p-1$ divides $C!$ and $$f(m) + n + f(n) + m \equiv 2^{C!+1} + 2^{c} - 2 \equiv 2^{c} \not\equiv 0 \pmod{p}$$by FLT, so this works. $\blacksquare$

rickards... The answer is $k \geq 2$. I first show $k=1$ fails. Suppose that $f$ works. If it sends some odd $a_1$ to an even and some even $a_2$ to an odd, we get a contradiction since $2 \mid \gcd(f(a_1)+a_2,f(a_2)+a_1)$. Thus $f$ must either send all evens to evens or all odds to odds (possibly both), which clearly fails too. I will now construct a function $f$ that is $2$-good, which finishes the problem. We construct $f$ of the form $$f(n)=2^{g(n)}-n-1$$for a function $g$ that will be defined as follows: let $g(1)=1000$, and then recursively define $g(n)$ such that all the prime divisors of $f(m)+n=n-m+2^{g(n)}-1>0$ across any $m<n$ also divide $2^{g(n)}-2$, and $g(n)>g(n-1)$. This is easy: for each prime divisor $p$ just multiply a factor of $p-1$ to $g(n)-1$. Now suppose some prime $p$ divides $\gcd(f(m)+n, f(n)+m)$, so it has to divide $2^{g(n)}-2$ as well. On the other hand, we require $$p \mid m+n+f(m)+f(n)=2^{g(m)}+2^{g(n)}-2 \implies p \mid 2^{g(m)} \implies p=2.$$Furthermore, since $m+n+f(m)+f(n) \equiv 2 \pmod{4}$, we cannot have $4 \mid \gcd(f(m)+n,f(n)+m)$, hence we always have $\gcd(f(m)+n,f(n)+m) \leq 2$, as desired. $\blacksquare$ Remark: The driving motivation behind this solution is the fact that if we allow $f$ to go from $\mathbb{Z}^+ \to \mathbb{Z}$ then $f(n)=-n+1$ works perfectly, so we need a way to translate this to some $\mathbb{Z}^+ \to \mathbb{Z}^+$ function that sort of has the same behavior "modulo primes". My first idea was to define $f(n)=p_{g(n)}\#-n+1$ (a primorial that grows sufficiently large), but if you write stuff out you realize that it's more convenient to have $f(n)+n+1$ be a convenient form whose prime factors we can control easily: this turns out to be possible as well, and we're done!

Answer: For all $k \ge 2$. Firstly observe that there isn't any 1-good function because of modulo 2 reasons. Now we'll construct function $f$ for which $\gcd(f(m)+n, f(n)+m) \le 2$. We'll select $f(n) = 2^{g(n)} - n - 1$ for some $g \colon \mathbb{N} \to \mathbb{N}$. Let $N$ be a sufficiently large integer and let $g(1) = N$. Now we'll construct the sequence $g(n)$ recursively. Assume $g(1), \dots, g(n-1)$ are defined and we'll define $g(n)$ such a way: $g(n) > \max(g(1), g(2), \dots, g(n-1))$ and for all primes $p$ less than $f(n-1) + n + 1$, $g(n) \equiv 1 (p-1)$. Then it suffices to check that $\gcd(f(m) + n, f(n) + m) \le 2$ for all $1 \le m \le n - 1$. Since $f(m) + n + f(n) + m = 2^g(n) + 2^g(m) - 2 \equiv 2 (4)$, so $4 \nmid \gcd(f(m) + n, f(n) + m)$. Now assume the contrary, let $p$ be an odd prime that $p \mid \gcd(f(m) + n, f(n) + m)$. Since $p \mid f(m) + n$, so $p \le f(m) + n < f(n-1) + n + 1$, so $g(n) \equiv 1 (p-1)$. Thus by FLT, we have $f(n) + m = 2^{g(n)} - n - 1 + m \equiv 2 - n - 1 + m = m + 1 - n \equiv 0 (p)$. On the other hand, $0 \equiv f(m) + n = 2^{g(m)} - m - 1 + n \equiv 2^{g(m)} (p)$, so $p \mid 2^{g(m)}$, a contradiction. Thus $\gcd(f(m) + n, f(n) + m) \le 2$ for all $1 \le m \le n - 1$ and we can construct $g$ recursively. Thus we're done. $\blacksquare$ Remark: This is a very difficult problem, or I'm so bad at constructions. Somehow I managed to solve it, but it doesn't feel intuitive after solving it. Firstly I think if we let $f(m) + f(n) + m + n$ is a power of 2, then we only have to deal 4. Thus $f(n) = 1 - n$ perfectly work. And I think I have to enhance $f$, so my first idea was taking $f(n) = 2^{g(n)} - n$ and it didn't work well. And I think I should at least deal with 4, so I take $f(n) = 2^{g(n)} - n + 1$ and I thought defining $g$ recursively by using CRT would work. But it didn't work. It took almost 2 hours to realise that if we're gonna deal with 4, so $f(n) = 2^{g(n)} - n + 2k + 1$ would work. So I chose $f(n) = 2^{g(n)} - n - 1$ and that works perfectly.

We claim the answer is $k\ge 2$. Claim: There is a $2$-good function. Proof: Let $p_1=4$ and $p_2, p_3,\dots$ be the odd primes in order. We will recursively define sequences $x_1, x_2,\dots$, $s_1, s_2,\dots$, and $f(1), f(2),\dots$ of positive integers. First, define $x_{1} =\dots = x_{10} = 1$, $s_1=10$, and $f(1) = p_1\dots p_{10}$. Go through each value of $i>1$. Define $s_i>s_{i-1}$ such that \[p_{s_i}> i+\max_{m<i}(f(m)).\]Then, for each $s_{i-1}<j\le s_i$, choose a value of $x_j\not\equiv 0\pmod{p_j}$ such that \[x_j+m+f(m)\not \equiv 0 \pmod{p_j}\]for all $m< i$. This is possible because $p_j>p_{s_{i-1}}\ge i$. Then, choose $f(i)$ such that $i+f(i)\equiv x_j\pmod{p_j}$ for all $j\le s_i$. Assume towards a contradiction that $p_i\mid f(a)+b$ and $p_i\mid f(b)+a$ for $a<b$. Then, $p_i \le f(a)+b < p_{s_b}$. So, $f(b)+b \equiv x_i \pmod{p_i}$. Let $r$ be the lowest number such that $s_r\ge i$. Case 1: $a<r$ Then, by definition, \[b+f(b)+a+f(a)\equiv x_i+a+f(a)\not \equiv 0\pmod{p_i},\]a contradiction. Case 2: $a\ge r$ Then, \[b+f(b)+a+f(a)\equiv 2x_i\not \equiv 0\pmod{p_i},\]a contradiction. Claim: There is no $1$-good function. Proof: Assume toward a contradiction $f$ is $1$-good. There is at most $1$ value of $x$ such that $x\equiv f(x)\equiv 0\pmod{2}$ and at most $1$ value of $x$ such that $x\equiv f(x)\equiv 1\pmod{2}$. So, there exists $a, b$ such that $a\equiv f(b)\equiv 0\pmod{2}$ and $b\equiv f(a)\equiv 1\pmod{2}$, a contradiction.

your telling me this whole induction is what? Note that a $1$-sunny function can't exist, since if $f$ maps infinitely many even numbers to even numbers or odd numbers to odd numbers, taking both $m, n$ to be that type of even / odd number gives $k \ge 2$. If there are infinitely many even numbers mapped to odd and odd mapped to even, then taking $m, n$ to be different parity that satisfy the above gives $k \ge 2$ as well. We claim that a $2$-sunny function exists and construct it through transfinite induction. Claim: Suppose that $m \mapsto -f(m)$ has no involutions and forms a digraph on residues $\pmod{p}$, other than $r + f(r) \equiv 0 \pmod{f(p)}$ holding for at most one number $r$. Then $p \nmid \gcd(f(m)+n, f(n)+m)$ for all $n, m$. Proof. A contradiction can only occur if $n \equiv -f(m) \pmod{p}, m \equiv - f(n) \pmod{p}$. Our graph is just a non-involutive arrow graph with one node pointing to itself which still has no involutions other than taking that arrow twice, which can't occur since there's at most one $r$. $\blacksquare$ The idea is to iteratively construct this digraph for each prime $p$, at each time only worrying about finitely many primes. For all small primes $k$ and $4$ we can manually construct a working digraph and function $f_p$ on residues $\pmod{p}$ that forms the digraph $G_p$. Define a set $\mathcal{S}$ of dirty primes initially empty. Define a set $\mathcal{C}$ of completed primes containing all small primes and $4$. Construct $f(n)$ by CRT to have its correct residue of $f_p(n) \pmod{f(p)}$. For each dirty prime $q$, we take $f(n) \equiv f_q(n)$ to continue building the digraph $G_q$ (at this point we have our one fixed number $r$). If $G_q$ has been specified for all residues properly, we remove $q$ from $\mathcal{S}$ and add it to $\mathcal{C}$. We add all prime divisors of $n + f(n)$ to the set $\mathcal{S}$ of dirty primes (as this is their fixed point), which keeps it finite. At the end of this transfinite induction process, all primes and $4$ are in $\mathcal{C}$, and thus by our claim $\gcd(f(m) + n, f(n) + m)$ isn't divisible by any element of $\mathcal{C}$ as desired.