# Approximating reals with rationals

I don't have any particular motivation for this question, it just popped into my head.

We play the following game: you give me a real number between 0 and 1, and I have to do my best to approximate it as a rational number with a limit on the size of the denominator. More formally, you choose $$x \in [0,1]$$, and I have to come up with a pair of integers $$p,q \leq N$$ that minimize the error: $$E = \bigg| x - \frac{p}{q} \bigg|$$

For a given $$N$$, how should you choose $$x$$ to make me incur the largest possible error?

I made a plot to see how all the possible fractions fall on the number line for each $$N$$ between 1 and 100. It has a rather interesting pattern which seems to have a fractal nature. For any $$N$$, the hardest choices of $$x$$ seem to be at the extremes of the interval: between 0 and the smallest possible fraction larger than 0, and between 1 and the largest possible fraction smaller than $$1$$.

The rationals with denominator less than $$N$$ form part of the Farey sequence. The largest gap is between $$0$$ and $$\frac 1N$$ and again from $$\frac {N-1}N$$ to $$1$$. The smallest gap is from $$\frac 1N$$ to $$\frac 1{N-1}$$ and again from $$\frac{N-2}{N-1}$$ to $$\frac {N-1}N$$, a gap of $$\frac 1{N(N-1)}$$ To find the best rational approximation to a given $$x$$, you find its continued fraction and quit with the last convergent with denominator less than $$N$$, and see if a small adjustment can improve it.
The ordered set of fractions you can choose is by definition the Farey sequence of order $$N$$. All Farey sequences have the property that any two adjacent fractions $$\frac ab<\frac cd$$ are separated by a gap of $$\frac1{bd}$$. I thus want to find adjacent fractions with $$bd$$ as small as possible for the given $$N$$, and then choose the number midway between those two fractions.
Now I argue that except if $$b=1$$ or $$d=1$$, two adjacent fractions must have $$bd>N$$. The natural number inequality $$x+y holds whenever $$x,y>1$$ and $$(x,y)\ne(2,2)$$. If $$bd\le N$$, the mediant $$\frac{a+c}{b+d}$$ of the assumed-adjacent fractions would come between them in the Farey sequence of order $$N$$ – contradiction. For $$b=d=2$$ there is only one selectable fraction with denominator $$2$$, so we cannot speak of two such fractions being adjacent in the first place.
Now $$b=1$$ or $$d=1$$ means the largest gap I desire lies at the endpoints. Accordingly, to induce the largest approximation error I choose $$\frac1{2N}$$ or $$1-\frac1{2N}$$, which incurs the largest error of $$\frac1{2N}$$.
Certainly, if $$x = \frac{1}{2N}$$, then that forces an error of $$\frac{1}{2N}$$ or more - since $$\frac{p}{q}$$ with $$q \le N$$ is either equal to 0, or else $$\frac{p}{q} \ge \frac{1}{N}$$.
Now, given any other $$x \in [0, 1]$$, consider the continued fraction expansion of $$x$$, $$x = [a_0, a_1, a_2, \ldots] = a_0 + \frac{1} {a_1 + \frac{1} {a_2 + \ddots}}.$$ Certainly, if $$x$$ is a rational number with denominator $$\le N$$, then we can approximate $$x$$ with error 0, so let us exclude that case. Otherwise, if some truncation $$\frac{p_k}{q_k} = [a_0, a_1, \ldots, a_k]$$ has denominator $$2 \le q_k \le N$$, then choose the largest such $$k$$. Then $$q_{k+1} > N$$, and so $$\left| x - \frac{p_k}{q_k} \right| \le \frac{1}{q_k q_{k+1}} < \frac{1}{2N}$$. The only other cases are $$x = [0, M, \ldots]$$ with $$M > N$$, or $$x = [0, 1, M, \ldots]$$ with $$M > N - 1$$. In the first case, $$0 < x < \frac{1}{N}$$, so either $$\frac{0}{1}$$ or $$\frac{1}{N}$$ is within $$\frac{1}{2N}$$ of $$x$$; in the second case, $$1 - \frac{1}{N} < x < 1$$, so either $$\frac{N-1}{N}$$ or $$\frac{1}{1}$$ is within $$\frac{1}{2N}$$ of $$x$$.