How close are the closests cells of the same color in a periodically colored grid? In a square grid, if we have a coloring of the form $c(x, y) = (x + ny) \bmod m$, what is the minimum (positive!) taxicab distance (i.e. sum of absolute value fo coordinates) between different cells of the same color?
 
(In this example I colored all values except for 0 the same color. We are interested in the distance between yellow cells.)
This is the same as minimizing the following function, 
$$d(m, n) = |mk + n\ell| + |\ell|$$
for fixed $0 \leq m < n$, and $k, \ell$ are integers that can be chosen freely (not both 0). 
Ideally, I would like a formula for the minimum value of $d$ in terms of $m$ and $n$.
For the example shown above, $m = 7, n = 3$, and we find the minimum of $d$ to be $3$ (with $k = -1$ and $\ell = 2$). 

It looks like this should be very easy but I find it tricky in the general case. 
Background: I came across this question: Minimum colors needed to color Z2 with connected subsets restriction, where a specific instance of this problem is used in the answer. This is also related to another question I asked: What is the minimum distance between vertices on an integer grid with the form $(m(m+2), 0)p + (m, 1)q$? (Although in that question the Euclidean distance rather than the taxicab distance is being minimized.)

Update: I wrote a program to calculate the value of $d(m, n)$. There are obviously patterns, although I have not worked out exactly what. 

Here is the same data arranged in a triangle; obviously factors play a role.

One interesting observation: the maximum value in each row (for fixed $m$), is roughly $\sqrt{2m}$, and in fact exactly $\sqrt{2m}$ for $m = 2, 8, 18, 32, ...$ (whenever $m$ is double a perfect square).
 A: There's a continuous variant of this problem that tells you pretty well why the patterns you see exist:

First, let $|\cdot |:\mathbb R \rightarrow [0,1/2]$ be the function that takes a real number to the distance from it to the closest integer. Let $m>0$ be a real number. Define a function
  $$f_m(x)=\min_{b\in\mathbb N}m|bx|+b.$$

In the main question, we are trying to find a non-trivial pair $a,b\in\mathbb Z$ minimizing $|a|+|b|$ such that $a+nb\equiv 0\pmod{m}$. If we divide through by $m$ we get $\frac{a}m + b\cdot \frac{n}m\equiv 0 \pmod{1}$. Note that, for any $b$, the size of the smallest $a$ possible to make this happen is $m\cdot |b\cdot \frac{n}m|$. As a result, we find that the closest point is exactly $f_m(n/m)$ away in the taxicab metric.
So, what is this function $f_k$ like? Well, you can write it as a minimum of other functions; Let $g_{m,a,b}(x)=m|bx-a|+b$ for $a,b\in\mathbb N$. This is just a "cone" of slope $mb$ with vertex at $\left(\frac{a}b,b\right)$. Then, we can express
$$f_m=\min_{a,b}g_{m,a,b}$$
which basically tells us that, if we increase $m$ to be rather large, the only points with small distances will be those that are very close to $\frac{a}b$ for some small enough $b$. This is where the "stripes" in your diagram come from.
Here's an animation of the function $f_m$ over the interval $[0,1]$ for $m$ increasing from $1$ to $20$. Notice how, as the parameter increases, the function sweeps upwards and "catches" on the node points

Each of these "cones" where the function catches is a brief window of small values that persists whenever the ratio of that value to $m$ is there - and note that this does transfer to the set of evaluations only at multiples of $1/m$ since $g_{m,a,b}$ has slope $\pm mb$ everywhere, so has to be within $\frac{b}2$ of the minimum possible value for some multiple of $1/m$.
One can use Dirichlet's approximation theorem to show that the maximum of $f_m$ grows on the order of $\sqrt{m}$, as you observe; in particular, for every $x$, there must be some some pair of integers $a,b$ with $1 \leq b \leq \sqrt{m}$ so that $|bx-a| < \frac{1}{\sqrt{m}}$ - equivalently so that $g_{m,a,b}(x) \leq b + \sqrt{m} \leq 2\sqrt{m}.$ Thus $f_m(x) \leq 2\sqrt{m}$ everywhere. For a lower bound, one can note that $\frac{1}{2\sqrt{m}}$ is closer to $0$ than to any fraction with denominator at most $\sqrt{m}$, so $f_m\left(\frac{1}{2\sqrt{m}}\right) = \frac{\sqrt{m}}2$; if you're a little more careful, you can improve the lower bound fairly easily, although I'm not sure how to improve the upper bound.
Similar reasoning also gives a good hint at what you do if you want to compute $f_m(x)$, you only need to look at pairs $(a,b)$ where $|bx-a|$ is smaller than it is for any pair $(a',b')$ with smaller $b$; these are called best rational approximations of the second kind and are precisely the convergents $a/b$ of the continued fraction for $x$. Thus, to compute the value really quickly, you just compute $g_{m,a,b}(x)$ at convergents $a/b$ of $x$ until the smallest evaluation of this quantity is less than the denominator of the convergent you have reached - this should happen really quickly since the denominators of a continued fraction grow at least as fast as the sequence of Fibonacci numbers and you can definitely stop by the time the denominators have reached $m/2$. This also tells you that, for a fixed $x$, the growth of $f_m(x)$ is controlled by how quickly the convergents to $x$ converge to $x$.
A: I do not know  very well about these type of problem but I think this link may help https://books.google.co.in/books?id=OIpZxK8naikC&pg=PA104&lpg=PA104&dq=How+close+are+the+closest+cells+of+the+same+color+in+a+periodically+colored+grid?&source=bl&ots=u9o1Z7ZF8G&sig=ACfU3U1ekJGse9l9ZzTU_z3GGOsCQ2hMow&hl=en&sa=X&ved=2ahUKEwi-pMH9lMzmAhVayzgGHdGtBgMQ6AEwAXoECAwQAQ#v=onepage&q=How%20close%20are%20the%20closest%20cells%20of%20the%20same%20color%20in%20a%20periodically%20colored%20grid%3F&f=false.
If this does not satisfy you,you can comment below and I will remove my answer.
