Mínimo $ab$ para Número Racional $a/b$ en un intervalo

Question

Dados números racionales $L$ y $U$ , $0<L<U<1$ encuentra el número racional $M=a/b$ tal que $L \le M<U$ y $(a\times b)$ es lo más pequeño posible $a$ y $b$ son números enteros. Por ejemplo,

• Si $L=66/101$ y $U=19/29$ entonces $M=17/26$ .
• Si $L=66/101$ y $U=19/28$ entonces $M=2/3$ .

Ahora mismo estoy usando una búsqueda ingenua que es exponencial en complejidad. ¿Existe un método mejor?

Si sirve de ayuda, se puede suponer la factorización en primos del numerador y del denominador de $U$ y $L$ son conocidos.

Answer 1

Basta con encontrar el menor $b$ y, a continuación, el más pequeño posible $a$ dado $b$ . Esto no es del todo obvio, así que intentaré demostrarlo:

Supongamos que tenemos números enteros positivos $a,b$ tal que

(i) $b$ es el menor denominador de todas las fracciones en $[L,U)$ y

(ii) $a/b$ es el múltiplo más pequeño de $1/b$ en $[L,U)$ .

Esto significa que $(a-1)/b < L \le a/b$ y así $a-1<bL\le a$ .

N enteros $c,d$ tal que $c/d \in [L,U)$ y $cd < ab$ . Entonces $b < d$ , por (i), por lo que $bL < dL$ . (El caso $b=d$ i tendríamos $c \ge a$ por (ii), y por tanto $cd \ge ab$ .)

Pero ahora tenemos $a-1 < bL < dL \le c$ porque $c/d \ge L$ .

Por lo tanto $a < c$ que junto con $b < d$ nos da $ab < cd$ , contradiciendo nuestra suposición.

Y para encontrar el menor denominador en un intervalo $[L,U)$ basta con calcular las fracciones continuas de $L$ y $U$ y truncarlos en la primera posición en la que difieran. Sus ejemplos:

$66/101 = [0;1,1,1,7,1,3]$
$19/29 = [0;1,1,1,9]$
Así que la respuesta es $[0;1,1,1,8] = 17/26$

$66/101 = [0;1,1,1,7,1,3]$
$19/28 = [0;1,2,9]$
Así que la respuesta es $[0;1,2] = 2/3$

En realidad no es muy tan simple como eso, porque las fracciones continuas oscilan alrededor de su convergente, en lugar de converger monotónicamente. Pero puedes buscar en Google "fracciones continuas" para conocer los detalles.

Answer 2

Según la respuesta de TonyK, sólo es necesario encontrar el denominador más pequeño para el que una fracción en $[L,U)$ existe. Para evitar lo que él llama oscilaciones "desordenadas", podemos proceder del siguiente modo:

1. Comience con $(a,b,c,d)=(0,1,1,1)$ .
2. *[Observación: Tenemos $\frac ab<L<U\le \frac cd$ y $ad-bc=-1$ y cualquier fracción entre $\frac ab$ y $\frac cd$ tiene denominador $\ge b+d$ ]* $\quad$ Sea $u\leftarrow a+c$ , $v\leftarrow b+d$ .
3. Si $u<Lv$ , dejemos que $a\leftarrow u$ , $b\leftarrow v$ y vaya al paso 2
4. Si $u\ge Uv$ , dejemos que $c\leftarrow u$ , $d\leftarrow v$ y vaya al paso 2.
5. Hemos encontrado $M=\frac uv$ cuyo producto $uv$ es mínima. Terminar

Answer 3

¿Por qué su algoritmo es exponencial?

Aquí hay una opción: No pienses en los números como fracciones, sino como pares. Tu objetivo es encontrar el par $(a,b)$ tal que $L\leq a/b\leq U$ tal que $a\times b$ es mínima. En este caso, NO reducimos fracciones.

Para un $b$ podemos encontrar fácilmente el $a$ que cumpla las condiciones calculando $a=\lceil bL\rceil$ . (Debe comprobarlo: Si $bL\in\mathbb{Z}$ utilice $a+1$ y compruebe también que $a/b<U$ .) Este $a$ da el mejor par posible con denominador $b$ (cualquier cosa más grande tiene un $a$ -valor).

Utilizando el mejor mínimo hasta el momento, sigue calculando hasta que tu denominador alcance este valor. Una condición de parada débil viene dada por la fracción $\frac{1}{2}(L+U)$ que sabes que está en el intervalo.