racional aproximación de $\pi$, donde el denominador se encuentra en $[a,b]$

Question

En una codificación de la competencia, que me encontré con la siguiente pregunta:

Dado $1\le a,b \le 10^{15}$ , encontrar un entero $Q$ en este rango de $[a,b]$, de tal manera que $P/Q$ es la más cercana a $\pi$. Donde $P$ es cualquier número entero.

La comprobación de la convergencia para cada número entero en el rango es computacionalmente ineficiente y no aceptado por la plataforma.

Answer 1

Se puede bajar la de Stern–Brocot árbol de localización de $\pi$, la grabación de las mejores aproximaciones racionales que tienen denominador en el rango dado, tomando las mejores aproximaciones que se encuentran a cada paso.

Answer 2

Sugerencia: Desde $\pi$ es un número real entre el$3$$4$, puede ser escrita en la forma: $$\pi=\sum_{k=0}^\infty c_k10^{-k}$$ donde $c_k\in\{0,1,2,\dots,9\}$ por cada $k=0,1,2,\dots$. Podemos "cortar" la cola de la serie, y obtener que: $$\pi\approx\sum_{k=0}^{15}c_k10^{-k}$$ o, en otras palabras: $$\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}}$$ Ahora, supongamos que $[a,b]$ contiene más de una enteros - si sólo hay un número entero, la selección de $Q$ es trivial. Deje $q_1<q_2<\dots<q_n$ ser estos enteros. Vamos también $$p_i=\left[q_i\frac{\sum\limits_{k=0}^{15}10^{15-k}c_k}{10^{15}}\right]$$ Así, queremos que la aproximación más cercana a $\pi\approx\frac{10^{15}c_0+10^{14}c_1+\dots+c_{15}}{10^{15}}$, por lo tanto, queremos minimizar la diferencia con respecto al $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|$$ que es igual a $$\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}$$ Ahora, usando la conocida dígitos de $\pi$, trate de encontrar el mencionado mínimo (puede ser útil tener en cuenta que la cantidad que necesitamos para minimizar tiende a 0 $q_n$ crece infinitamente).

Answer 3

Las mejores aproximaciones racionales será el convergents de la continuación de la fracción de $\pi.$ Tenemos:

$$\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]$$

Entonces es fácil calcular el convergents por iteración hasta llegar a un denominador más grande que $10^{15}$. Los dos primeros convergents se $3$$22/7$. Si los numeradores de las convergents se $p_0, p_1, \ldots$ y los denominadores son $q_0, q_1, \ldots,$, la recursividad fórmula es:

$$\frac{p_n}{q_n} = \frac{a_n p_{n-1} + p_{n-2}}{a_n q_{n-1}+q_{n-2}}.$$

Así que calcular convergents hasta que el denominador es demasiado grande:

$$3, \frac{22}{7}, \frac{333}{106}, \frac{355}{113}, \frac{103993}{33102}, \ldots \frac{428224593349304}{136308121570117}, \frac{5706674932067741}{1816491048114374}.$$

Así que el último segundo de la fracción anterior es el 28 de convergentes y es el último de una menor que $10^{15}.$