Coprime pairs of large integers Denote $ I = [1, +\infty).$ Define the function $f: I\times I \to \mathbb R^+$ as follows:  $$f(x, y) = \inf_{(n, m)\in {\rm CP}}\big(|x-n|+|y-m|\big), \,\, (x,y) \in I\times I,$$
where ${\rm CP}$ is the set of pairs of coprime integers. i.e.
$${\rm CP} : = \{(n,m) \in \mathbb N\times \mathbb N\,\, \text{s. t.}\,\, {\rm gcd}(n,m) = 1\}.$$
It has been proven here that $f$ is not bounded.
Let now $k\geq 1$ be an integer and denote
$$S_k : = \{n \in \mathbb{N}\,\, \text{s. t.}\,\, \exists m \in \mathbb{N},\,\, m\geq n\,\, \text{where}\,\, f(n,m)\geq k\}.$$
I wonder if there is a method to find $\inf S_k.$ Regarding the tow answers introduced here, my intuition is that $\inf S_k$ grows enormously as $k$ getting larger. It might be possible to find a lower bound for $\inf S_k$ that gives a clear picture of such growth.
Thank you for any hint/answer.
PS: I'm not an "algebraist". Then, I'd be very grateful for detailed answers.
 A: Disclaimer: I only have a start on this problem, and a very loose lower bound that only takes into account a single condition.

With integer $n,y,k$, $f(n,y)\ge k$ if and only if $\gcd(a,b)\not=1$ for $|a-n|+|b-y|<k$ or equivalently, for $|a-n|+|b-y|\le k-1$. The ordered pair $(a,b)$ runs over all pairs with Manhattan distance less than $k$ from $(n,y)$. For $k=1$, all you need is $\gcd(n,y)\not=1$. For $k=2$, it gets a bit more complicated, as you need $\gcd(n,y)\not=1, \gcd(n,y+1)\not=1, \gcd(n,y-1)\not=1, \gcd(n-1,y)\not=1, \gcd(n+1,y)\not=1$, and for general $k$, you will have $2k(k-1)+1$ inequalities.
Here we are only concerned with the minimum $n$ for which there exists a solution in $y$. With these many $\gcd$ constraints, you can get constraints on $n$ (or more generally, what conditions an element of $S_k$ must satisfy).
In order to help define $S_k$ more clearly, I'll define $R_m$ (for integer $m\ge 1$) as the set of integers $z$ such that there exists a $y$ such that for all $x\in[y, y+m)$, $\gcd(z, x)\not=1$. Written more formally, $$R_m:=\{z\in\mathbb{N}\mid \exists y\in\mathbb{N}\forall x\in[y, y+m):\gcd(z, x)\not=1\}$$
For $m=1$, this is just the set of all integer $z$ greater than $1$, since you could set $y=z$ (divisible by at least one prime). For $m=2$, this is the set of integer $z$ that are divisible by at least two primes. For $m=3$, it would seem like it's just the set of integers that are divisible by at least three primes, but in addition to that, it's the set of integers that are divisible by $2$ and divisible by at least one prime. This is because if $z$ is even, you could let $y$ be even as well so that $\gcd(z, y) \ge 2$ and $\gcd(z, y+2)\ge 2$ and so all you need in addition is $\gcd(z, y+1)\not=1$. Continuing on, you basically want the primes to "cover" all the integers from $0$ to $m-1$.
Then $S_k$ is the set of integers $n$ such that $$\forall r\in[0, k-1]:n-r\in R_{2(k-r)-1}\wedge n+r\in R_{2(k-r)-1}$$
Using this and the fact that $R_{k_1}\subseteq R_{k_2}$ for $k_1\ge k_2$, you can get a recursive definition that $$n\in S_{k}\iff n-1\in S_{k-1} \wedge n+1\in S_{k-1} \wedge n\in R_{2k-1}$$
As you can see, the requirements get much harder at each step, but to get a very loose lower bound on $\inf S_k$, you could use just the condition that $n\in R_{2k-1}$. This would give you that $a_{2k} \le \inf S_k$ where $a_{k}$ is sequence A034386 from the OEIS. Since $a_k=\exp\left(\left(1+o(1)\right)\cdot k\right)$, $\inf S_k$ grows at least as fast as $\exp(2k)$.
