In a coding competition, I encountered following question:
Given $1\le a,b \le 10^{15}$ , find an integer $Q$ in this range $[a,b]$, such that $P/Q$ is closest to $\pi$. Where $P$ is any suitable integer.
Checking convergence for each integer in the range is computationally inefficient and not accepted by platform.
On
You can go down the Stern–Brocot tree locating $\pi$, recording the best rational approximations that have denominator in the given range, taking the best approximations found at each step.
On
The best rational approximations will be the convergents of the continued fraction for $\pi.$ We have:
$$\pi = [a_0; a_1,a_2,\ldots]=[3, 7, 15, 1, 292, 1, 1, 1, 2, 1, 3, 1, 14, 2, 1, 1, 2, 2, 2, 2, 1, 84, 5,\ldots]$$
Then it's easy to compute the convergents by iteration until you hit a denominator bigger than $10^{15}$. The first two convergents are $3$ and $22/7$. If the numerators of the convergents are $p_0, p_1, \ldots$ and the denominators are $q_0, q_1, \ldots,$ then the recursion formula is:
$$\frac{p_n}{q_n} = \frac{a_n p_{n-1} + p_{n-2}}{a_n q_{n-1}+q_{n-2}}.$$
So we compute convergents until the denominator is too big:
$$3, \frac{22}{7}, \frac{333}{106}, \frac{355}{113}, \frac{103993}{33102}, \ldots \frac{428224593349304}{136308121570117}, \frac{5706674932067741}{1816491048114374}.$$
So the second last fraction above is the 28th convergent and is the last one smaller than $10^{15}.$
Hint: Since $\pi$ is a real number between $3$ and $4$, it can be written in the form: $$\pi=\sum_{k=0}^\infty c_k10^{-k}$$ where $c_k\in\{0,1,2,\dots,9\}$ for every $k=0,1,2,\dots$. We can "cut" the tail of the series, and get that: $$\pi\approx\sum_{k=0}^{15}c_k10^{-k}$$ or, in other words: $$\pi\approx c_0+\frac{c_1}{10}+\frac{c_2}{10^2}+\dots+\frac{c_{15}}{10^{15}}=\frac{10^{15}c_0+10^{14}c_1+\dots+c_{15}}{10^{15}}$$ Now, let us assume that $[a,b]$ contains more than one integers - if there's only one integer, the selection of $Q$ is trivial. Let $q_1<q_2<\dots<q_n$ be these integers. Let also $$p_i=\left[q_i\frac{\sum\limits_{k=0}^{15}10^{15-k}c_k}{10^{15}}\right]$$ So, we want the closest approximation to $\pi\approx\frac{10^{15}c_0+10^{14}c_1+\dots+c_{15}}{10^{15}}$, hence, we want to minimise the difference - with respect to $i$: $$\left|\frac{p_i}{q_i}-\frac{10^{15}c_0+10^{14}c_1+\dots+c_{15}}{10^{15}}\right|=\left|\frac{\left[q_i\frac{\sum\limits_{k=0}^{15}10^{15-k}c_k}{10^{15}}\right]}{q_i}-\frac{10^{15}c_0+10^{14}c_1+\dots+c_{15}}{10^{15}}\right|$$ which is equal to $$\left|\frac{\left[q_1\sum_{k=0}^{15}c_k10^k\right]-q_i\sum_{k=0}^{15}c_k10^k}{q_i}\right|=\frac{q_i\sum_{k=0}^{15}c_k10^k-\left[q_i\sum_{k=0}^{15}c_k10^k\right]}{q_i}$$ Now, using the known digits of $\pi$, try find the aforementioned minimum (it might be useful to bear in mind that the quantity we need to minimise tends to 0 as $q_n$ grows infinitely).