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.
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.
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).
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}.$
