¿Cómo calcular la siguiente/anterior número racional puede representarse?

Question

Un (aproximado) no negativo número racional representación es un par de números naturales de cada uno de ellos no mayor a un límite fijo de M (y, por supuesto, el denominador de ser distinto de cero).

Con esta condición hay número finito de representable los números racionales. Esto significa que para cada número, nombre de anterior y siguiente número en el conjunto (de curso, excepto para los más pequeños de 0 y más grande 1). Cómo calcularlos?

En otras palabras, vamos a tener un conjunto de números

$$ R(M)=\{\frac{p}{q} : p,q\in\mathbb{N},q\neq0,p\leq q\leq M\} $$

donde $M\in\mathbb{N}_+$

y dado el número de $\frac{p_1}{q_1}\in R(M)$.

Quiero encontrar los números de $\frac{p_S}{q_S}\in R(M)$ $\frac{p_L}{q_L}\in R(M)$ (si existen) de tal manera que

$$ \frac{p_S}{q_S}<\frac{p_1}{q_1} \wedge \neg\exists_{\frac{p}{q}\in R(M)}\frac{p_S}{q_S}<\frac{p}{q}<\frac{p_1}{q_1} $$

y smilarly

$$ \frac{p_L}{q_L}>\frac{p_1}{q_1} \wedge \neg\exists_{\frac{p}{q}\in R(M)}\frac{p_1}{q_1}<\frac{p}{q}<\frac{p_L}{q_L} $$

Answer 1

Echale un vistazo al siguiente link: http://en.wikipedia.org/wiki/Farey_sequence . En general, la secuencia de Farey se ocupa exactamente con ese tipo de pregunta.

Answer 2

Todo esto necesita es una sola modular de inversión, con la complejidad de la $O(\log M \log \log M)$ (o algo así).

Se nos da $p/q$ en términos mínimos, con $p, q \in \mathbb{N}$$q > 0$. Queremos que los vecinos más próximos de $p/q$, $a/b < p/q < c/d$, sujeto a $a,b,c,d \in \mathbb{N}$$c,d > 0$. Supongamos por el momento que $p < q$.

Considere la posibilidad de $c/d$. Es el elemento después de $p/q$ en la secuencia de Farey $F_n$, lo que significa que $cq - dp = 1$. En particular, $dp+1 = 0 \pmod q$, es decir,$d = -1/p \pmod q$. Así que vamos a

$r = 1/p \pmod q$

Ahora hacer $d$ tan grande como sea posible, sujeto a (i) $d = -r \pmod q$ y (ii) $d \leq n$. Entonces sólo hay que poner $c = (dp+1)/q$.

Del mismo modo, para calcular el $a/b$, hacen que las $b$ tan grande como sea posible sujeto a (i) $b = +r \pmod q$ y (ii) $b \leq n$. A continuación, poner $a = (bp-1)/q$.

Un ejemplo Supongamos $p/q = 28/61$$n=100$. Entonces la inversa de a$28 \pmod{61}$$r=24$. Por lo $d = 37 \pmod{61}$, y podemos tomar $d=98$,$c=(98.28+1)/61 = 45$. Y $b = 24 \pmod{61}$, así que podemos aprovechar $b = 85$,$a = (85.28-1)/61=39$. Así, obtenemos:

$39/85 < 28/61 < 45/98$

Sólo tenemos que modificar esta ligeramente para manejar el caso $p > q$: en lugar de calcular el mayor $d \leq n$ que satisface el modulo requisito, nos encontramos con el correspondiente modulo requisito para $c$, y, a continuación, busque el más grande de $c \leq n$. Usted puede completar los detalles para usted.

Answer 3

Como mencioné en un estrechamente relacionadas con la cuestión, esto tiene una muy hermosa interpretación geométrica el empleo de la selección de la Zona Teorema: $\rm\: a/b < c/d\:$ son dos términos adyacentes en una secuencia de Farey si el triángulo $\rm T$ con vértices $\rm (0,0), u = (b,a), v = (d,c)$ no contiene celosía puntos, excepto para los vértices. Selección de la fórmula de esto es cierto iff $\rm\ area\ T = $ #interior_points $\ +\ 1/2\ $ #boundary_points $\:-\ 1\ =$ $\ 0 + 3/2 - 1 = 1/2\:.$ Pero por básicos de la geometría analítica $\rm\: area\ T\: =\: |det(u,v)|/2 = |ad-bc|/2\:.\:$ por lo tanto $\rm\:a/b,\:c/d\:$ son meighbors en algunos secuencia de Farey iff $\rm\:|ad-bc| = 1\:.\:$

Por lo tanto el problema se reduce a resolver el lineal de la ecuación de Diophantine $\rm\:ax+by = 1\:.\:$ Como es bien sabido, tales ecuaciones pueden resolverse mediante el empleo del algoritmo de Euclides extendido, que está muy bien implementado por realizar el algoritmo de Euclides en paralelo en una identidad aumentada del sistema de ecuaciones. Para un ejemplo trabajado en detalle ver mi post aquí.

De hecho, merece ser conocido mucho mejor que Elegir aplicado originalmente a su fórmula del área de una manera similar a la que dan una hermosa prueba geométrica de la Bezout representación lineal de la dpc.

Answer 4

Hasta ahora he encontrado el algoritmo itera sobre denominadores (inspirado por mjqxxxx del comentario). Por lo tanto es de $O(M)$ tiempo de complejidad (sin embargo cada iteración es corto y simple).

En la secuencia de Farey durante dos mandatos consecutivos fracciones $\frac{p_1}{q_1}<\frac{p_L}{q_L}$ sostiene que $p_L q_1 - p_1 q_L=1$. Por lo tanto $p_L=\frac{p_1 q_L + 1}{q_1}$. Tenemos $\frac{p_1}{q_1}$ $M$ y queremos saber $\frac{p_L}{q_L}$.

Desde $1\leq q_L\leq M$ ahora podemos iterar sobre todos los números naturales en el rango de $[1;M]$, y para cada uno vea si $\frac{p_1 q_L + 1}{q_1}$ es un número natural. Si es así que tenemos la fracción deseada $\frac{p_L}{q_L}$.

Puede suceder que este será resuelto por más de un valor en ese intervalo. Esto significa que dependiendo $M$ la solución son diferentes fracciones. Por lo tanto de interés es el último (creo yo - yo no he demostrar que) el valor y sería mejor para recorrer de $M$ $1$en lugar de la otra manera.

(La búsqueda de la anterior fracción se puede hacer en la misma forma con $p_S=\frac{p_1 q_S – 1}{q_1}$.)

Queda abierta la cuestión de si, de hecho el más grande $q_L$/$q_S$ que resuelve la ecuación de números naturales es la solución. También esto todavía es $O(M)$ así que tal vez algo más rápido se puede encontrar?