Fila de farey

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 6 de diciembre de 2019; las comprobaciones requieren 3 ediciones .

La serie de Farey (también fracciones de Farey, secuencia de Farey o cuadro de Farey ) es una familia de subconjuntos finitos de números racionales .

Definición

La sucesión de Farey de orden th es una serie ascendente de todas las fracciones propias irreducibles positivas cuyo denominador es menor o igual que : $norte$ $norte$

F_{n}{\stackrel {\text{def}}{=}}\left\{{\frac {a_{i}}{b_{i}}}:0\leqslant a_{i}\ leqslant b_{i}\leqslant n,\ \gcd(a_{i},b_{i})=1,\ {\frac {a_{i}}{b_{i}}}<{\frac {a_{ i+1}}{b_{i+1}}}}\derecha\}.

La secuencia de Farey de una orden se puede construir a partir de la secuencia de la orden mediante la siguiente regla: $n+1$ $norte$

Copiamos todos los elementos de la secuencia del pedido . $norte$
Si la suma de los denominadores en dos fracciones adyacentes de la secuencia de orden da un número no mayor que , entonces insertamos su mediana entre estas fracciones , igual a la razón de la suma de sus numeradores a la suma de los denominadores. $norte$ $n+1$

Ejemplo

Secuencias Farey del 1 al 8: $norte$

F_1=\izquierda\{\frac{0}{1},\;\frac{1}{1}\derecha\};

F_2=\izquierda\{\frac{0}{1},\;\frac{1}{2},\;\frac{1}{1}\derecha\};

F_3=\left\{\frac{0}{1},\;\frac{1}{3},\;\frac{1}{2},\;\frac{2}{3},\; \frac{1}{1}\derecho\};

F_4=\left\{\frac{0}{1},\;\frac{1}{4},\;\frac{1}{3},\;\frac{1}{2},\; \frac{2}{3},\;\frac{3}{4},\;\frac{1}{1}\right\};

F_5=\left\{\frac{0}{1},\;\frac{1}{5},\;\frac{1}{4},\;\frac{1}{3},\; \frac{2}{5},\;\frac{1}{2},\;\frac{3}{5},\;\frac{2}{3},\;\frac{3}{ 4},\;\frac{4}{5},\;\frac{1}{1}\right\};

F_6=\left\{\frac{0}{1},\;\frac{1}{6},\;\frac{1}{5},\;\frac{1}{4},\; \frac{1}{3},\;\frac{2}{5},\;\frac{1}{2},\;\frac{3}{5},\;\frac{2}{ 3},\;\frac{3}{4},\;\frac{4}{5},\;\frac{5}{6},\;\frac{1}{1}\right\} ;

F_7=\left\{\frac{0}{1},\;\frac{1}{7},\;\frac{1}{6},\;\frac{1}{5},\; \frac{1}{4},\;\frac{2}{7},\;\frac{1}{3},\;\frac{2}{5},\;\frac{3}{ 7},\;\frac{1}{2},\;\frac{4}{7},\;\frac{3}{5},\;\frac{2}{3},\;\ fracción{5}{7},\;\frac{3}{4},\;\frac{4}{5},\;\frac{5}{6},\;\frac{6}{7 },\;\frac{1}{1}\derecho\};

F_8=\left\{\frac{0}{1},\;\frac{1}{8},\;\frac{1}{7},\;\frac{1}{6},\; \frac{1}{5},\;\frac{1}{4},\;\frac{2}{7},\;\frac{1}{3},\;\frac{3}{ 8},\;\frac{2}{5},\;\frac{3}{7},\;\frac{1}{2},\;\frac{4}{7},\;\ fracción{3}{5},\;\frac{5}{8},\;\frac{2}{3},\;\frac{5}{7},\;\frac{3}{4 },\;\frac{4}{5},\;\frac{5}{6},\;\frac{6}{7},\;\frac{7}{8},\;\frac {1}{1}\derecho\}.

Propiedades

Si hay dos fracciones adyacentes en la serie de Farey, entonces . $p_1/q_1<p_2/q_2$ $q_1p_2-q_2p_1=1$

Prueba.

Tenga en cuenta que el triángulo está en el plano con vértices y no puede contener puntos enteros que no sean vértices. De lo contrario, si el punto completo está contenido en , entonces la fracción se encuentra entre y y el denominador no excede a . Entonces, de acuerdo con la fórmula del Pico , su área es igual a . Por otro lado, el área es . H.t.d. $A=(0,\;0)$ $B=(p_1,\;q_1)$ $C=(p_2,\;q_2)$ $(r,\;s)$ $\triángulo ABC$ $r/s$ $p_1/q_1$ $p_2/q_2$ $s$ $\max\{q_1,\;q_2\}$ $1/2$ $\triángulo ABC$ $(q_1p_2-q_2p_1)/2$

Lo contrario también es cierto: si las fracciones son tales que , entonces son miembros vecinos de la serie de Farey . $p_1/q_1<p_2/q_2$ $q_1p_2-q_2p_1=1$ $F_{\máx\{q_1,q_2\}}$

Algoritmo de generación

El algoritmo para generar todas las fracciones F n es muy simple, tanto en orden ascendente como descendente. Cada iteración del algoritmo construye la siguiente fracción basada en las dos anteriores. Así, si y son dos fracciones ya construidas, y es la siguiente incógnita, entonces . Esto significa que para algún número entero , y es verdadero , por lo tanto y . Como debe estar lo más cerca posible de , entonces establecemos el denominador para que sea el máximo posible, es decir , a partir de aquí, teniendo en cuenta el hecho de que es un número entero, tenemos y ${\frac{a}{b}}$ ${\frac{c}{d))$ ${\frac{p}{q))$ $\frac{c}{d} = \frac{a + p}{b + q}$ $k$ $kc = a + p$ $kd = b + q$ $p = kc - un$ $q = kd - b$ ${\frac{p}{q))$ ${\frac{c}{d))$ $kd - b = norte$ $k$ $k = \lpiso\frac{n + b}{d}\rpiso$

p = \left\lpiso\frac{n+b}{d}\right\rpiso c - a

q = \left\lpiso\frac{n+b}{d}\right\rpiso d - b

Ejemplo de implementación en Python :

def farey ( n , asc = True ): if asc : a , b , c , d = 0 , 1 , 1 , n else : a , b , c , d = 1 , 1 , n - 1 , n print " % d / %d " % ( a , b ) while ( asc y c <= n ) o ( no asc y a > 0 ): k = int (( n + b ) / d ) a , b , c , d = c , d , k * c - a , k * d - b imprime " %d / %d " % ( a , b )

Ejemplo de implementación de JavaScript :

clase Fracción { constructor ( número , denominación ) { este . número = número ; esto _ denominador = denominativo ; } copiar () { devuelve una nueva fracción ( este . número , este . denominación ); } } función * farey ( n , asc = verdadero ) { let [ a , b ] = asc ? [ nueva Fracción ( 0 , 1 ), nueva Fracción ( 1 , n ) ] : [ nueva Fracción ( 1 , 1 ), nueva Fracción ( n - 1 , n ) ]; rendir un . copiar (); while ( asc && b . numer <= n || ! asc && a . numer > 0 ) { yield b . copiar (); const k = Matemáticas . piso (( n + a . denom ) / b . denom ), siguiente = nueva Fracción ( k * b . numer - a . numer , k * b . denom - a . denom ); un = segundo _ b = siguiente ; } }

Por lo tanto, es posible construir un conjunto arbitrariamente grande de todas las fracciones en forma abreviada, que puede usarse, por ejemplo, para resolver la ecuación diofántica mediante una búsqueda exhaustiva en números racionales.

Historia

John Farey es un famoso geólogo, uno de los pioneros de la geofísica . Su única contribución a las matemáticas fueron las fracciones que llevan su nombre. En 1816 se publicó el artículo de Farey "Sobre una curiosa propiedad de las fracciones vulgares", en el que definió la secuencia . Este artículo llegó a Cauchy , quien en el mismo año publicó una prueba de la conjetura de Farey de que cada nuevo término de la sucesión de orden Farey es la mediana de sus vecinos. La secuencia descrita por Farey en 1816 fue utilizada por Charles Haros en su artículo de 1802 sobre la aproximación de decimales por fracciones comunes. $F_{n}$ $n+1$

Véase también

Enlaces

Knop K. Sistema no binario // Computadora doméstica. - 2001. - Nº 8 . Archivado desde el original el 12 de marzo de 2007.
Weisstein, Eric W. Farey Sequence (inglés) en el sitio web de Wolfram MathWorld .
Numeradores y Denominadores de la Serie Farey: secuencia OEIS A006842 y secuencia OEIS A006843 .