Secuencia de Farey

Diagrama de Farey a F ₉ representado con arcos circulares. En la imagen SVG , coloque el cursor sobre una curva para resaltarla y sus términos.

Diagrama de Farey a F ₉ .

Patrón simétrico realizado por los denominadores de la secuencia de Farey, F ₉ .

Patrón simétrico realizado por los denominadores de la secuencia de Farey, F ₂₅ .

En matemáticas , la secuencia de Farey de orden n es la secuencia de fracciones completamente reducidas , ya sea entre 0 y 1, o sin esta restricción, ^[a] que cuando en términos más bajos tienen denominadores menores o iguales an , ordenados en orden creciente Talla.

Con la definición restringida, cada secuencia de Farey comienza con el valor 0, denotado por la fracción 0 / 1 , y termina con el valor 1, denotado por la fracción 1 / 1 (aunque algunos autores omiten estos términos).

Una secuencia de Farey a veces se denomina serie de Farey , lo cual no es estrictamente correcto porque los términos no se suman. ^[2]

Ejemplos de

Las secuencias de Farey de los pedidos 1 a 8 son:

F ₁ = { 0 / 1 _, 1 / 1 }

F ₂ = { 0 / 1 _, 1 / 2 _, 1 / 1 }

F ₃ = { 0 / 1 _, 1 / 3 _, 1 / 2 _, 2 / 3 _, 1 / 1 }

F ₄ = { 0 / 1 _, 1 / 4 _, 1 / 3 _, 1 / 2 _, 2 / 3 _, 3 / 4 _, 1 / 1 }

F ₅ = { 0 / 1 _, 1 / 5 _, 1 / 4 _, 1 / 3 _, 2 / 5 _, 1 / 2 _, 3 / 5 _, 2 / 3 _, 3 / 4 _, 4 / 5 _, 1 / 1 }

F ₆ = { 0 / 1 _, 1 / 6 _, 1 / 5 _, 1 / 4 _, 1 / 3 _, 2 / 5 _, 1 / 2 _, 3 / 5 _, 2 / 3 _, 3 / 4 _, 4 / 5 _, 5 / 6 _, 1 / 1 }

F ₇ = { 0 / 1 _, 1 / 7 _, 1 / 6 _, 1 / 5 _, 1 / 4 _, 2 / 7 _, 1 / 3 _, 2 / 5 _, 3 / 7 _, 1 / 2 _, 4 / 7 _, 3 / 5 _, 2 / 3 _, 5 / 7 _, 3 / 4 _, 4 / 5 _, 5 / 6 _, 6 / 7 _, 1 / 1 }

F ₈ = { 0 / 1 _, 1 / 8 _, 1 / 7 _, 1 / 6 _, 1 / 5 _, 1 / 4 _, 2 / 7 _, 1 / 3 _, 3 / 8 _, 2 / 5 _, 3 / 7 _, 1 / 2 _, 4 / 7 _, 3 / 5 _, 5 / 8 _, 2 / 3 _, 5 / 7 _, 3 / 4 _, 4 / 5 _, 5 / 6 _, 6 / 7 _, 7 / 8 _, 1 / 1 }

Centrado
F 1 = { 0 / 1 , 1 / 1 }
F 2 = { 0 / 1 , 1 / 2 , 1 / 1 }
F 3 = { 0 / 1 , 1 / 3 , 1 / 2 , 2 / 3 , 1 / 1 }
F 4 = { 0 / 1 , 1 / 4 , 1 / 3 , 1 / 2 , 2 / 3 , 3 / 4 , 1 / 1 }
F 5 = { 0 / 1 , 1 / 5 , 1 / 4 , 1 / 3 , 2 / 5 , 1 / 2 , 3 / 5 , 2 / 3 , 3 / 4 , 4 / 5 , 1 / 1 }
F 6 = { 0 / 1 , 1 / 6 , 1 / 5 , 1 / 4 , 1 / 3 , 2 / 5 , 1 / 2 , 3 / 5 , 2 / 3 , 3 / 4 , 4 / 5 , 5 / 6 , 1 / 1 }
F 7 = { 0 / 1 , 1 / 7 , 1 / 6 , 1 / 5 , 1 / 4 , 2 / 7 , 1 / 3 , 2 / 5 , 3 / 7 , 1 / 2 , 4 / 7 , 3 / 5 , 2 / 3 , 5 / 7 , 3 / 4 , 4 / 5 , 5 / 6 , 6 / 7 , 1 / 1 }
F 8 = { 0 / 1 , 1 / 8 , 1 / 7 , 1 / 6 , 1 / 5 , 1 / 4 , 2 / 7 , 1 / 3 , 3 / 8 , 2 / 5 , 3 / 7 , 1 / 2 , 4 / 7 , 3 / 5 , 5 / 8 , 2 / 3 , 5 / 7 , 3 / 4 , 4 / 5 , 5 / 6 , 6 / 7 , 7 / 8 , 1 / 1 }

Ordenados

F1 = {0/1, 1/1} F2 = {0/1, 1/2, 1/1} F3 = {0/1, 1/3, 1/2, 2/3, 1/1} F4 = {0/1, 1/4, 1/3, 1/2, 2/3, 3/4, 1/1} F5 = {0/1, 1/5, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 4/5, 1/1} F6 = {0/1, 1/6, 1/5, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 4/5, 5/6 , 1/1} F7 = {0/1, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 2/5, 3/7, 1/2, 4/7, 3/5 , 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 1/1} F8 = {0/1, 1/8, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2 , 4/7, 3/5, 5/8, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 7/8, 1/1}

Graficar los numeradores frente a los denominadores de una secuencia de Farey da una forma como la de la derecha, que se muestra para F ₆ .

Reflejar esta forma alrededor de los ejes diagonal y principal genera el resplandor solar de Farey , que se muestra a continuación. El resplandor solar de Farey de orden n conecta los puntos de cuadrícula enteros visibles desde el origen en el cuadrado del lado 2 n , centrado en el origen. Usando el teorema de Pick, el área del resplandor solar es 4 (| F _n | −1), donde | F _n | es el número de fracciones en F _n .

Historia

La historia de la 'serie Farey' es muy curiosa - Hardy & Wright (1979) ^[3]

... una vez más, el hombre cuyo nombre fue dado a una relación matemática no fue el descubridor original hasta donde llegan los registros. - Beiler (1964) ^[4]

Secuencias de Farey llevan el nombre de la British geólogo John Farey, padre , cuya carta sobre estas secuencias fue publicado en el Philosophical Magazine en 1816. Farey conjeturó, sin ofrecer pruebas, que cada nuevo término en una secuencia de expansión Farey es el mediant de sus vecinos . La carta de Farey fue leída por Cauchy , quien proporcionó una prueba en sus Ejercicios de matemática y atribuyó este resultado a Farey. De hecho, otro matemático, Charles Haros , había publicado resultados similares en 1802 que ni Farey ni Cauchy conocían. ^[4]Por tanto, fue un accidente histórico el que vinculó el nombre de Farey con estas secuencias. Este es un ejemplo de la ley de la eponimia de Stigler .

Propiedades

Longitud de secuencia e índice de una fracción

La secuencia de Farey de orden n contiene todos los miembros de las secuencias de Farey de órdenes inferiores. En particular F _n contiene todos los miembros de F _{n -1} y también contiene una fracción adicional para cada número que es menor que n y primos entre sí a n . Por lo tanto F ₆ consta de F ₅ junto con las fracciones 1 / 6 y 5 / 6 .

El término medio de una secuencia de Farey F _n es siempre 1 / 2 , para n > 1. A partir de este, podemos relacionar las longitudes de F _n y F _{n -1} utilizando la función totient de Euler  : ${\displaystyle \varphi (n)}$

${\displaystyle |F_{n}|=|F_{n-1}|+\varphi (n).}$

Usando el hecho de que | F ₁ | = 2, podemos derivar una expresión para la longitud de F _n : ^[5]

${\displaystyle |F_{n}|=1+\sum _{m=1}^{n}\varphi (m)=1+\Phi (n),}$

donde está el totalizador totient .${\displaystyle \Phi (n)}$

También tenemos :

${\displaystyle |F_{n}|={\frac {1}{2}}\left(3+\sum _{d=1}^{n}\mu (d)\left\lfloor {\tfrac {n}{d}}\right\rfloor ^{2}\right),}$

y por una fórmula de inversión de Möbius  :

${\displaystyle |F_{n}|={\frac {1}{2}}(n+3)n-\sum _{d=2}^{n}|F_{\lfloor n/d\rfloor }|,}$

donde µ ( d ) es la función de Möbius en teoría numérica y es la función de piso .${\displaystyle \lfloor {\tfrac {n}{d}}\rfloor }$

El comportamiento asintótico de | F _n | es :

${\displaystyle |F_{n}|\sim {\frac {3n^{2}}{\pi ^{2}}}.}$

El índice de una fracción en la secuencia de Farey es simplemente la posición que ocupa en la secuencia. Esto es de especial relevancia ya que se usa en una formulación alternativa de la hipótesis de Riemann , ver más abajo . A continuación se muestran varias propiedades útiles:${\displaystyle I_{n}(a_{k,n})=k}$${\displaystyle a_{k,n}}$${\displaystyle F_{n}=\{a_{k,n}:k=0,1,\ldots ,m_{n}\}}$${\displaystyle a_{k,n}}$

${\displaystyle I_{n}(0/1)=0,}$

${\displaystyle I_{n}(1/n)=1,}$

${\displaystyle I_{n}(1/2)=(|F_{n}|-1)/2,}$

${\displaystyle I_{n}(1/1)=|F_{n}|-1,}$

${\displaystyle I_{n}(h/k)=|F_{n}|-1-I_{n}((k-h)/k).}$

El índice de dónde y es el mínimo común múltiplo de los primeros números , viene dado por: ^[6]${\displaystyle 1/k}$${\displaystyle n/(i+1)<k\leq n/i}$${\displaystyle n}$${\displaystyle i}$${\displaystyle n={\rm {lcm}}([2,i])}$

${\displaystyle I_{n}(1/k)=1+n\sum _{j=1}^{i}{\frac {\varphi (j)}{j}}-k\Phi (i).}$

Vecinos de Farey

Las fracciones que son términos vecinos en cualquier secuencia de Farey se conocen como par de Farey y tienen las siguientes propiedades.

Si a / b y c / d son vecinos en una secuencia de Farey, con a / b  <  c / d , entonces su diferencia c / d  -  a / b es igual a 1 / bd . Esto se debe a que cada par consecutivo de racionales de Farey tiene un área equivalente de 1. ^[7]

Si r1 = p / q y r2 = p '/ q' se interpretan como vectores (p, q) en el plano x, y, el área de A (p / q, p '/ q') está dada por qp ' - q'p. Como cualquier fracción agregada entre dos fracciones de secuencia de Farey consecutivas anteriores se calcula como el mediante (⊕)

A (r1, r1⊕r2) = A (r1, r1) + A (r1, r2) = A (r1, r2) = 1 (ya que r1 = 1/0 y r2 = 0/1 su área debe ser uno) .

Ya que:${\displaystyle {\frac {c}{d}}-{\frac {a}{b}}={\frac {bc-ad}{bd}},}$

esto es equivalente a decir que

${\displaystyle bc-ad=1}$.

Por lo tanto 1 / 3 y 2 / 5 son vecinos en F ₅ , y su diferencia es 1 / 15 .

Lo contrario también es cierto. Si

${\displaystyle bc-ad=1}$

para números enteros positivos a , b , c y d con un < b y c < d entonces un / b y c / d será vecinos en la secuencia de Farey de orden max ( b, d ).

Si p / q tiene vecinos a / b y c / d de alguna secuencia de Farey, con

${\displaystyle {\frac {a}{b}}<{\frac {p}{q}}<{\frac {c}{d}}}$

entonces p / q es el mediant de un / b y c / d - en otras palabras,

${\displaystyle {\frac {p}{q}}={\frac {a+c}{b+d}}.}$

Esto se sigue fácilmente de la propiedad anterior, ya que si bp - aq = qc - pd = 1 , entonces bp + pd = qc + aq , p ( b + d ) = q ( a + c ) , p / q = a + c / b + d .

Se deduce que si un / b y c / d es decir son vecinos en una secuencia de Farey entonces el primer término que aparece entre ellos como el orden de la secuencia de Farey se incrementa

${\displaystyle {\frac {a+c}{b+d}},}$

que aparece por primera vez en la secuencia de Farey de orden b + d .

Así, el primer término que aparezca entre 1 / 3 y 2 / 5 es 3 / 8 , que aparece en F ₈ .

El número total de pares de vecinos de Farey en F _n es 2 | F _n | -3.

El árbol de Stern-Brocot es una estructura de datos que muestra cómo la secuencia se construye a partir de 0 (= 0 / 1 ) y 1 (= 1 / 1 ), mediante la adopción de mediants sucesivas.

Vecinos de Farey y fracciones continuas

Las fracciones que aparecen como vecinas en una secuencia de Farey tienen expansiones de fracciones continuas estrechamente relacionadas . Cada fracción tiene dos expansiones de fracciones continuas: en una, el término final es 1; en el otro, el término final es mayor que 1. Si p / q , que aparece por primera vez en la secuencia de Farey F _q , tiene expansiones de fracciones continuas

[0; a ₁ , a ₂ , ..., a _{n - 1} , a _n , 1]

[0; a ₁ , a ₂ , ..., a _{n - 1} , a _n + 1]

entonces el vecino más cercano de p / q en F _q (que será su vecino con el denominador más grande) tiene una expansión de fracción continua

[0; a ₁ , a ₂ , ..., a _n ]

y su otro vecino tiene una expansión de fracción continua

[0; a ₁ , a ₂ , ..., a _{n - 1} ]

Por ejemplo, 3 / 8 tiene las dos expansiones fracción continua [0; 2, 1, 1, 1] y [0; 2, 1, 2] , y sus vecinos en F ₈ están 2 / 5 , que se puede expandir como [0; 2, 1, 1] ; y 1 / 3 , que se puede ampliar como [0; 2, 1] .

Fracciones de Farey y el mínimo común múltiplo

El mcm se puede expresar como los productos de las fracciones de Farey como

${\displaystyle {\text{lcm}}[1,2,...,N]=e^{\psi (N)}={\frac {1}{2}}\left(\prod _{r\in F_{N},0<r\leq 1/2}2\sin(\pi r)\right)^{2}}$

donde es la segunda función de Chebyshev . ^{[8] [9]}${\displaystyle \psi (N)}$

Las fracciones de Farey y el máximo común divisor

Dado que la función totient de Euler está directamente relacionada con el mcd, también lo está el número de elementos en F _n ,

${\displaystyle |F_{n}|=1+\sum _{m=1}^{n}\varphi (m)=1+\sum \limits _{m=1}^{n}\sum \limits _{k=1}^{m}\gcd(k,m)\cos {2\pi {\frac {k}{m}}}.}$

Para cualquier 3 fracciones de Farey un / b , c / d y e / f la siguiente identidad entre el gcd 's de los 2x2 determinantes de matriz en valor absoluto sostiene: ^[6]

${\displaystyle \gcd \left({\begin{Vmatrix}a&c\\b&d\end{Vmatrix}},{\begin{Vmatrix}a&e\\b&f\end{Vmatrix}}\right)=\gcd \left({\begin{Vmatrix}a&c\\b&d\end{Vmatrix}},{\begin{Vmatrix}c&e\\d&f\end{Vmatrix}}\right)=\gcd \left({\begin{Vmatrix}a&e\\b&f\end{Vmatrix}},{\begin{Vmatrix}c&e\\d&f\end{Vmatrix}}\right)}$

Aplicaciones

Las secuencias de Farey son muy útiles para encontrar aproximaciones racionales de números irracionales. ^[10] Por ejemplo, la construcción por Eliahou ^[11] de un límite inferior en la duración de ciclos no triviales en el proceso 3 x +1 usa secuencias de Farey para calcular una expansión fraccionaria continua del número log ₂ (3).

En sistemas físicos con fenómenos de resonancia, las secuencias de Farey proporcionan un método muy elegante y eficiente para calcular las ubicaciones de resonancia en 1D ^[12] y 2D. ^[13]

Las secuencias de Farey son prominentes en los estudios de planificación de trayectorias en cualquier ángulo en cuadrículas de celdas cuadradas, por ejemplo en la caracterización de su complejidad computacional ^[14] u optimalidad. ^[15] La conexión se puede considerar en términos de rutas restringidas por r , es decir, rutas formadas por segmentos de línea que atraviesan en la mayoría de las filas y en la mayoría de las columnas de celdas. Vamos a ser el conjunto de vectores tal que , y , son primos entre sí. Sea el resultado de reflejar en la línea . Deja . Entonces, cualquier camino restringido por r puede describirse como una secuencia de vectores de${\displaystyle r}$${\displaystyle r}$${\displaystyle Q}$${\displaystyle (q,p)}$${\displaystyle 1\leq q\leq r}$${\displaystyle 0\leq p\leq q}$${\displaystyle p}$${\displaystyle q}$${\displaystyle Q*}$${\displaystyle Q}$${\displaystyle y=x}$${\displaystyle S=\{(\pm x,\pm y):(x,y)\in Q\cup Q*\}}$${\displaystyle S}$. Hay una biyección entre y la secuencia de orden de Farey dada por el mapeo de .${\displaystyle Q}$${\displaystyle r}$${\displaystyle (q,p)}$${\displaystyle {\tfrac {p}{q}}}$

Círculos de Ford

Comparación de los círculos de Ford y un diagrama de Farey con arcos circulares para n de 1 a 9. Cada arco interseca sus círculos correspondientes en ángulos rectos. En la imagen SVG , coloque el cursor sobre un círculo o curva para resaltarlo y sus términos.

Existe una conexión entre la secuencia de Farey y los círculos de Ford .

Por cada fracción p / q (en sus términos más bajos) hay un Ford círculo C [ p / q ], que es el círculo de radio 1 / (2 q ² ) y centro en ( p / q , 1 /  2 q ²  ). Dos círculos de Ford para diferentes fracciones están separados o son tangentes entre sí; dos círculos de Ford nunca se cruzan. Si 0 < p / q <1, entonces los círculos de Ford que son tangentes a C [ p / q ] son ​​precisamente los círculos de Ford para las fracciones vecinas dep / q en alguna secuencia de Farey.

Así C [ 2 / 5 ] es tangente a C [ 1 / 2 ], C [ 1 / 3 ], C [ 3 / 7 ], C [ 3 / 8 ] etc.

Los círculos de Ford también aparecen en la junta apolínea (0,0,1,1). La siguiente imagen ilustra esto junto con las líneas de resonancia de Farey. ^[dieciséis]

Junta apolínea (0,0,1,1) y el diagrama de resonancia de Farey.

Hipótesis de Riemann

Las secuencias de Farey se utilizan en dos formulaciones equivalentes de la hipótesis de Riemann . Suponga que los términos de son . Definir , en otras palabras, es la diferencia entre el k- ésimo término de la n- ésima secuencia de Farey y el k- ésimo miembro de un conjunto del mismo número de puntos, distribuidos uniformemente en el intervalo unitario. En 1924 Jérôme Franel ^[17] demostró que la declaración${\displaystyle F_{n}}$${\displaystyle \{a_{k,n}:k=0,1,\ldots ,m_{n}\}}$${\displaystyle d_{k,n}=a_{k,n}-k/m_{n}}$${\displaystyle d_{k,n}}$

${\displaystyle \sum _{k=1}^{m_{n}}d_{k,n}^{2}=O(n^{r})\quad \forall r>-1}$

es equivalente a la hipótesis de Riemann, y luego Edmund Landau ^[18] comentó (justo después del artículo de Franel) que la afirmación

${\displaystyle \sum _{k=1}^{m_{n}}|d_{k,n}|=O(n^{r})\quad \forall r>1/2}$

también es equivalente a la hipótesis de Riemann.

Otras sumas que involucran fracciones de Farey

La suma de todas las fracciones de Farey de orden n es la mitad del número de elementos:

${\displaystyle \sum _{r\in F_{n}}r={\frac {1}{2}}|F_{n}|.}$

La suma de los denominadores en la secuencia de Farey es el doble de la suma de los numeradores y se relaciona con la función totient de Euler:

${\displaystyle \sum _{a/b\in F_{n}}b=2\sum _{a/b\in F_{n}}a=1+\sum _{i=1}^{n}i\varphi (i),}$

que fue conjeturada por Harold L. Aaron en 1962 y demostrada por Jean A. Blake en 1966. Una prueba de una línea de la conjetura de Harold L. Aaron es la siguiente. La suma de los numeradores es . La suma de denominadores es . El cociente de la primera suma por la segunda suma es .${\displaystyle {\displaystyle 1+\sum _{2\leq b\leq n}\sum _{(a,b)=1}a=1+\sum _{2\leq b\leq n}b{\frac {\varphi (b)}{2}}}}$${\displaystyle {\displaystyle 2+\sum _{2\leq b\leq n}\sum _{(a,b)=1}b=2+\sum _{2\leq b\leq n}b\varphi (b)}}$${\displaystyle {\frac {1}{2}}}$

Sean b _j los denominadores ordenados de F _n , entonces: ^[19]

${\displaystyle \sum _{j=0}^{|F_{n}|-1}{\frac {b_{j}}{b_{j+1}}}={\frac {3|F_{n}|-4}{2}}}$

y

${\displaystyle \sum _{j=0}^{|F_{n}|-1}{\frac {1}{b_{j+1}b_{j}}}=1.}$

Sea a _j / b _j la _j -ésima fracción de Farey en F _n , entonces

${\displaystyle \sum _{j=1}^{|F_{n}|-1}(a_{j-1}b_{j+1}-a_{j+1}b_{j-1})=\sum _{j=1}^{|F_{n}|-1}{\begin{Vmatrix}a_{j-1}&a_{j+1}\\b_{j-1}&b_{j+1}\end{Vmatrix}}=3(|F_{n}|-1)-2n-1,}$

que se demuestra en. ^[20] También de acuerdo con esta referencia, el término dentro de la suma se puede expresar de muchas maneras diferentes:

${\displaystyle a_{j-1}b_{j+1}-a_{j+1}b_{j-1}={\frac {b_{j-1}+b_{j+1}}{b_{j}}}={\frac {a_{j-1}+a_{j+1}}{a_{j}}}=\left\lfloor {\frac {n+b_{j-1}}{b_{j}}}\right\rfloor ,}$

obteniendo así muchas sumas diferentes sobre los elementos de Farey con el mismo resultado. Usando la simetría alrededor de 1/2, la suma anterior se puede limitar a la mitad de la secuencia como

${\displaystyle \sum _{j=1}^{\lfloor |F_{n}|/2\rfloor }(a_{j-1}b_{j+1}-a_{j+1}b_{j-1})=3(|F_{n}|-1)/2-n-\lceil n/2\rceil ,}$

La función de Mertens se puede expresar como una suma de fracciones de Farey como

${\displaystyle M(n)=-1+\sum _{a\in {\mathcal {F}}_{n}}e^{2\pi ia}}$   donde     es la secuencia de Farey de orden n .${\displaystyle {\mathcal {F}}_{n}}$

Esta fórmula se utiliza en la demostración del teorema de Franel-Landau . ^[21]

Siguiente término

Existe un algoritmo sorprendentemente simple para generar los términos de F _n en orden tradicional (ascendente) o en orden no tradicional (descendente). El algoritmo calcula cada entrada sucesiva en términos de las dos entradas anteriores utilizando la propiedad mediante dada anteriormente. Si a / b y c / d son las dos entradas dadas, y p / q es la siguiente entrada desconocida, entonces c / d  =  a  +  p / b  +  q . Dado que c / d está en términos mínimos, debe haber un número entero kde tal manera que kc  =  un  +  p y kd  =  b  +  q , dando p  =  kc  -  una y q  =  kd  -  b . Si tenemos en cuenta p y q son funciones de k , entonces

${\displaystyle {\frac {p(k)}{q(k)}}-{\frac {c}{d}}={\frac {cb-da}{d(kd-b)}}}$

así que cuanto más grande se vuelve k , más se acerca p / q a c / d .

Para dar el siguiente término en la secuencia, k debe ser lo más grande posible, sujeto a kd  -  b  ≤  n (ya que solo estamos considerando números con denominadores no mayores que n ), por lo que k es el mayor número entero ≤  n  +  b / d . Poniendo este valor de k de nuevo en las ecuaciones para p y q da

${\displaystyle p=\left\lfloor {\frac {n+b}{d}}\right\rfloor c-a}$

${\displaystyle q=\left\lfloor {\frac {n+b}{d}}\right\rfloor d-b}$

Esto se implementa en Python de la siguiente manera:

def  farey_sequence ( n :  int ,  descendente :  bool  =  False )  ->  Ninguno :  "" "Imprime la enésima secuencia de Farey. Permite ascender o descender." ""  ( a ,  b ,  c ,  d )  =  ( 0 ,  1 ,  1 ,  n )  si  desciende :  ( a ,  c )  =  ( 1 ,  n  -  1 ) print ( " {0} / {1} " . format ( a ,  b ))  while  ( c  <=  n  y  no  descendente )  o  ( a  >  0  y  descendente ):  k  =  ( n  +  b )  //  d  ( a ,  b ,  c ,  d )  =  ( c ,  d ,  k  *  c -  a ,  k  *  d  -  b )  print ( " {0} / {1} " . formato ( a ,  b ))

Las búsquedas por fuerza bruta de soluciones a las ecuaciones diofánticas en racionales a menudo pueden aprovechar la serie de Farey (para buscar solo formas reducidas). Las líneas marcadas (*) también se pueden modificar para incluir dos términos adyacentes cualesquiera de modo que generen términos solo más grandes (o más pequeños) que un término dado. ^[22]

Ver también

• Patrón ABACABA
• Árbol de popa-brocot
• Función totient de Euler

Notas al pie

1. “ La secuencia de todas las fracciones reducidas con denominadores que no exceden n, enumeradas en orden de su tamaño, se llama secuencia de Farey de orden n. Con el comentario: “ Esta definición de las secuencias de Farey parece la más conveniente. Sin embargo, algunos autores prefieren restringir las fracciones al intervalo de 0 a 1. ”- Niven & Zuckerman (1972) ^[1]

Referencias

1. Niven, Ivan M .; Zuckerman, Herbert S. (1972). Introducción a la teoría de los números (tercera edición). John Wiley e hijos. Definición 6.1.
2. Guthery, Scott B. (2011). "1. El Mediante" . Un motivo de las matemáticas: historia y aplicación del mediante y la secuencia de Farey . Boston: Docent Press. pag. 7. ISBN 978-1-4538-1057-6. OCLC  1031694495 . Consultado el 28 de septiembre de 2020 .
3. Hardy, GH ; Wright, EM (1979). Introducción a la teoría de los números (Quinta ed.). Prensa de la Universidad de Oxford. Capítulo III . ISBN 0-19-853171-0.
4. Beiler, Albert H. (1964). Recreaciones en la teoría de los números (Segunda ed.). Dover. Capítulo XVI. ISBN 0-486-21096-0.Citado en "Farey Series, A Story" . Corta el nudo .
5. Sloane, N. J. A. (ed.). "Secuencia A005728" . La enciclopedia en línea de secuencias de enteros . Fundación OEIS.
6. Tomas, Rogelio (2018). "Sumas parciales de Franel". arXiv : 1802.07792 [ math.NT ].
7. Austin, David (diciembre de 2008). "Árboles, dientes y tiempo: las matemáticas de la fabricación de relojes" . Sociedad Matemática Estadounidense . Rhode Island. Archivado desde el original el 4 de febrero de 2020 . Consultado el 28 de septiembre de 2020 .
8. Martin, Greg (2009). "Un producto de los valores de la función Gamma en fracciones con el mismo denominador". arXiv : 0907.4384 [ matemáticas.CA ].
9. Wehmeier, Stefan (2009). "El LCM (1,2, ..., n) como un producto de los valores del seno muestreados sobre los puntos en las secuencias de Farey". arXiv : 0909.1838 [ matemáticas.CA ].
10. "Aproximación de Farey" . NRICH.maths.org . Archivado desde el original el 19 de noviembre de 2018 . Consultado el 18 de noviembre de 2018 .
11. Eliahou, Shalom (agosto de 1993). "El problema 3x + 1: nuevos límites inferiores en longitudes de ciclo no triviales" . Matemáticas discretas . 118 (1-3): 45-56. doi : 10.1016 / 0012-365X (93) 90052-U .
12. Zhenhua Li, A .; Harter, GT (2015). "Renacimientos cuánticos de osciladores Morse y geometría de Farey-Ford". Chem. Phys. Lett . 633 : 208–213. arXiv : 1308.4470 . doi : 10.1016 / j.cplett.2015.05.035 . S2CID 66213897 . 
13. Tomás, R. (2014). "De las secuencias de Farey a los diagramas de resonancia" . Phys. Rev. ST Accel. Vigas . 17 : 014001. doi : 10.1103 / PhysRevSTAB.17.014001 .
14. Harabor, Daniel Damir; Grastien, Alban; Öz, Dindar; Aksakalli, Vural (26 de mayo de 2016). "Pathfinding óptimo en cualquier ángulo en la práctica" . Revista de Investigación en Inteligencia Artificial . 56 : 89-118. doi : 10.1613 / jair.5007 .
15. Hew, Patrick Chisan (19 de agosto de 2017). "La longitud de las rutas de vértice más cortas en las cuadrículas de ocupación binaria en comparación con las más cortas restringidas por r" . Revista de Investigación en Inteligencia Artificial . 59 : 543–563. doi : 10.1613 / jair.5442 .
16. Tomas, Rogelio (2020). "Imperfecciones y correcciones". arXiv : 2006.10661 [ física ].
17. Franel, Jérôme (1924). "Les suites de Farey et le problème des nombres premiers" . Nachrichten von der Gesellschaft der Wissenschaften zu Göttingen . Mathematisch-Physikalische Klasse (en francés): 198-201.
18. Landau, Edmund (1924). "Bemerkungen zu der vorstehenden Abhandlung von Herrn Franel" . Nachrichten von der Gesellschaft der Wissenschaften zu Göttingen . Mathematisch-Physikalische Klasse (en alemán): 202-206.
19. Kurt Girstmair; Girstmair, Kurt (2010). "Sumas de Farey y Sumas de Dedekind". The American Mathematical Monthly . 117 (1): 72–78. doi : 10.4169 / 000298910X475005 . JSTOR 10.4169 / 000298910X475005 . S2CID 31933470 .  
20. Hall, RR; Shiu, P. (2003). "El índice de una secuencia de Farey" . Michigan Math. J . 51 (1): 209-223. doi : 10.1307 / mmj / 1049832901 .
21. Edwards, Harold M. (1974). "12.2 Miscelánea. La hipótesis de Riemann y la serie de Farey" . En Smith, Paul A .; Ellenberg, Samuel (eds.). Función Zeta de Riemann . Matemática pura y aplicada. Nueva York: Academic Press . págs. 263-267. ISBN 978-0-08-087373-2. OCLC  316553016 . Consultado el 30 de septiembre de 2020 .
22. Routledge, Norman (marzo de 2008). "Computación de la serie Farey". La Gaceta Matemática . Vol. 92 no. 523. págs. 55–62.

Otras lecturas

• Hatcher, Allen . "Topología de números" . Matemáticas. Ithaca, Nueva York: Cornell U.
• Graham, Ronald L .; Knuth, Donald E .; Patashnik, Oren (1989). Matemáticas concretas: una base para la informática (2ª ed.). Boston, MA: Addison-Wesley. págs. 115-123, 133-139, 150, 462-463, 523-524. ISBN 0-201-55802-5. - en particular, véase §4.5 (págs. 115-123), problema adicional 4.61 (págs. 150, 523–524), §4.9 (págs. 133-139), §9.3, problema 9.3.6 (págs. 462– 463).
• Vepstas, Linas. "El signo de interrogación de Minkowski, GL (2, Z) y el grupo modular" (PDF) . - revisa los isomorfismos del árbol Stern-Brocot.
• Vepstas, Linas. "Simetrías de mapas de duplicación de períodos" (PDF) . - revisa las conexiones entre las fracciones de Farey y los fractales.
• Cobeli, Cristian; Zaharescu, Alexandru (2003). "La secuencia Haros-Farey a los doscientos años. Una encuesta". Acta Univ. Apulensis Math. Informar. (5): 1–38. "págs. 1–20" (PDF) . Acta Univ. Apulensis . "págs. 21–38" (PDF) . Acta Univ. Apulensis .
• Matveev, Andrey O. (2017). Secuencias de Farey: dualidad y mapas entre subsecuencias . Berlín, DE: De Gruyter. ISBN 978-3-11-054662-0.

enlaces externos

• Bogomolny, Alexander . "Serie Farey" . Corta el nudo .
• Bogomolny, Alexander . "Árbol Stern-Brocot" . Corta el nudo .
• Pennestri, Ettore. "Una mesa Brocot de base 120" .
• "Serie de Farey" , Encyclopedia of Mathematics , EMS Press , 2001 [1994]
• Weisstein, Eric W. "Stern-Brocot Tree" . MathWorld .
• Secuencia OEIS A005728 (Número de fracciones en la serie de Farey de orden n)
• Secuencia OEIS A006842 (Numeradores de la serie de Farey de orden n)
• Secuencia OEIS A006843 (Denominadores de la serie de Farey de orden n)
• Bonahon, Francis . Fracciones divertidas y círculos de Ford (video). Brady Haran . Consultado el 9 de junio de 2015 , a través de YouTube.