Successió de Farey

En matemàtiques, la seqüència de Farey o successió de Farey d'ordre n és la seqüència de les fraccions irreductibles entre 0 i 1, o sense aquesta restricció, en la qual el denominador és inferior o igual a n i en ordre creixent.

• Diagrama de Farey a F9 representat amb arcs circulars. A la imatge SVG, passeu el cursor per sobre d'una corba per ressaltar-la i els seus termes.
  Diagrama de Farey a F₉ representat amb arcs circulars. A la imatge SVG, passeu el cursor per sobre d'una corba per ressaltar-la i els seus termes.
• Diagrama de Farey a F9
  Diagrama de Farey a F₉

Qualsevol successió comença amb el valor 0, representat per la fracció ⁰⁄₁, i finalitza amb el valor 1, representat per la fracció ¹⁄₁ (tot i que certs autors ometen aquest terme).

• Patró simètric fet pels denominadors de la seqüència de Farey, F9
  Patró simètric fet pels denominadors de la seqüència de Farey, F₉

De vegades aquesta successió rep el nom de sèrie de Farey, però això no és estrictament correcte atès que els termes no se sumen.

• 
  Patró simètric fet pels denominadors de la seqüència de Farey, F₂₅

Porta el nom del seu inventor, el geòleg anglès John Farey (1766-1826). El 1924, el matemàtic suís Jérôme Franel, va trobar una subtil relació entre la sèrie de Farey i la Hipòtesi de Riemann, cosa que va fer que Edmund Landau investigués aquesta relació, publicant un parell d'articles sobre el tema.Plantilla:SfnPlantilla:Sfn

Exemples

Les seqüències de Farey d'ordres de l'1 al 8 són:

F₁ = { Plantilla:Sfrac_, Plantilla:Sfrac }

F₂ = { Plantilla:Sfrac_, Plantilla:Sfrac_, Plantilla:Sfrac }

F₃ = { Plantilla:Sfrac_, Plantilla:Sfrac_, Plantilla:Sfrac_, Plantilla:Sfrac_, Plantilla:Sfrac }

F₄ = { Plantilla:Sfrac_, Plantilla:Sfrac_, Plantilla:Sfrac_, Plantilla:Sfrac_, Plantilla:Sfrac_, Plantilla:Sfrac_, Plantilla:Sfrac }

F₅ = { Plantilla:Sfrac_, Plantilla:Sfrac_, Plantilla:Sfrac_, Plantilla:Sfrac_, Plantilla:Sfrac_, Plantilla:Sfrac_, Plantilla:Sfrac_, Plantilla:Sfrac_, Plantilla:Sfrac_, Plantilla:Sfrac_, Plantilla:Sfrac }

F₆ = { Plantilla:Sfrac_, Plantilla:Sfrac_, Plantilla:Sfrac_, Plantilla:Sfrac_, Plantilla:Sfrac_, Plantilla:Sfrac_, Plantilla:Sfrac_, Plantilla:Sfrac_, Plantilla:Sfrac_, Plantilla:Sfrac_, Plantilla:Sfrac_, Plantilla:Sfrac_, Plantilla:Sfrac }

F₇ = { Plantilla:Sfrac_, Plantilla:Sfrac_, Plantilla:Sfrac_, Plantilla:Sfrac_, Plantilla:Sfrac_, Plantilla:Sfrac_, Plantilla:Sfrac_, Plantilla:Sfrac_, Plantilla:Sfrac_, Plantilla:Sfrac_, Plantilla:Sfrac_, Plantilla:Sfrac_, Plantilla:Sfrac_, Plantilla:Sfrac_, Plantilla:Sfrac_, Plantilla:Sfrac_, Plantilla:Sfrac_, Plantilla:Sfrac_, Plantilla:Sfrac }

F₈ = { Plantilla:Sfrac_, Plantilla:Sfrac_, Plantilla:Sfrac_, Plantilla:Sfrac_, Plantilla:Sfrac_, Plantilla:Sfrac_, Plantilla:Sfrac_, Plantilla:Sfrac_, Plantilla:Sfrac_, Plantilla:Sfrac_, Plantilla:Sfrac_, Plantilla:Sfrac_, Plantilla:Sfrac_, Plantilla:Sfrac_, Plantilla:Sfrac_, Plantilla:Sfrac_, Plantilla:Sfrac_, Plantilla:Sfrac_, Plantilla:Sfrac_, Plantilla:Sfrac_, Plantilla:Sfrac_, Plantilla:Sfrac_, Plantilla:Sfrac }

Ordenat

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}

Gràfica «esclat solar» de Farey

Traçant els numeradors en funció dels denominadors d'una seqüència de Farey s'obté una forma com els gràfics inferiors.

• Gràfica «esclat solar» de Farey d'ordre 6, amb 1 interior (vermell) i 96 punts de límit (verd) donant una àrea d'1 + 96/2 − 1 = 48, segons el teorema de Pick
  Gràfica «esclat solar» de Farey d'ordre 6, amb 1 interior (vermell) i 96 punts de límit (verd) donant una àrea d'1 + 96/2 − 1 = 48, segons el teorema de Pick
• Iteracions 1-10
  Iteracions 1-10

En reflectir aquesta forma al voltant dels eixos diagonal i principal es genera la gràfica «esclat solar» de Farey. L'esclat solar Farey d'ordre Plantilla:Mvar connecta els punts de la quadrícula d'enters visibles des de l'origen al quadrat del costat 2Plantilla:Mvar, centrats a l'origen. Utilitzant el teorema de Pick, l'àrea de l'esclat solar és 4(|Plantilla:Mvar_n|−1), on |Plantilla:Mvar_n| és el nombre de fraccions en Plantilla:Mvar_n.

Història

Les seqüències de Farey reben el nom del geòleg britànic John Farey, Sr., la carta del qual sobre aquestes seqüències es va publicar a la revista Philosophical Magazine el 1816. Farey va conjecturar, sense oferir proves, que cada nou terme en una expansió de la seqüència de Farey és el mediant dels seus veïns. Cauchy va llegir la carta de Farey, que va aportar una prova en els seus Exercices de mathématique, i va atribuir aquest resultat a Farey.

De fet, un altre matemàtic, Charles Haros, havia publicat resultats similars el 1802 que no eren coneguts ni per Farey ni per Cauchy.Plantilla:Sfn Així, va ser un accident històric el que va vincular el nom de Farey amb aquestes seqüències. Aquest és un exemple de la Llei de Stigler.

Propietats

• Diagrama de Farey amb cercles, ordre F4
  Diagrama de Farey amb cercles, ordre F₄
• Diagrama de Farey amb cercles, ordre F6
  Diagrama de Farey amb cercles, ordre F₆

Longitud de la seqüència i índex d'una fracció

La seqüència de Farey d'ordre n conté tots els membres de les seqüències de Farey d'ordre inferior. En particular F_n conté tots els membres de F_n−1 i també conté una fracció addicional per a cada nombre que sigui menor que n i coprimer a n. Així F₆ està format per F₅ juntament amb les fraccions Plantilla:Sfrac i Plantilla:Sfrac.

El terme mig d'una seqüència de Farey F_n és sempre Plantilla:Sfrac, per a n > 1. A partir d'això, podem relacionar les longituds de F_n i F_n−1 utilitzant la funció φ d'Euler $\phi (n)$:

$|F_n|=|F_{n-1}|+\phi (n).$

Utilitzant el fet que |F₁| = 2, podem derivar una expressió per a la longitud de F_n:

$|F_n|=1+\sum _{m=1}^n\phi (m)=1+\mathrm{\Phi }(n),$

on $\mathrm{\Phi }(n)$ és la suma indicatriu.

També tenim:

$|F_n|=\frac{1}{2}(3+\sum _{d=1}^n\mu (d){\lfloor \frac{n}{d}\rfloor }^2),$

i mitjançant una fórmula d'inversió de Möbius:

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

on µ(d) és el nombre teòric de la funció de Möbius, i $\lfloor \frac{n}{d}\rfloor$ és la funció de part entera.

El comportament asimptòtic de |F_n| és:

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

L'índex $I_n(a_{k,n})=k$ d'una fracció $a_{k,n}$ en la seqüència de Farey $F_n=\{a_{k,n}:k=0,1,\dots ,m_n\}$ és simplement la posició que $a_{k,n}$ ocupa en la seqüència. Això és d'especial rellevància, ja que s'utilitza en una formulació alternativa de la hipòtesi de Riemann (vegeu més avall). A continuació es mostren diverses propietats útils:

$I_n(0/1)=0,$

$I_n(1/n)=1,$

$I_n(1/2)=(|F_n|-1)/2,$

$I_n(1/1)=|F_n|-1,$

$I_n(h/k)=|F_n|-1-I_n((k-h)/k).$

L'índex d' $1/k$ on $n/(i+1)<k\le n/i$ i $n$ és el mínim comú múltiple del primer $i$ nombre, $n=\mathrm{m}\mathrm{c}\mathrm{m}([2,i])$, ve donat per:Plantilla:Sfn

$I_n(1/k)=1+n\sum _{j=1}^i\frac{\phi (j)}{j}-k\mathrm{\Phi }(i).$

Termes veïns de Farey

Les fraccions que són termes veïns en qualsevol seqüència de Farey es coneixen com a parell de Farey i tenen les propietats següents:

Si Plantilla:Sfrac i Plantilla:Sfrac són veïns en una seqüència de Farey, amb Plantilla:Sfrac < Plantilla:Sfrac, llavors la seva diferència Plantilla:Sfrac − Plantilla:Sfrac és igual a Plantilla:Sfrac. Això es deu al fet que cada parell consecutiu de racionals de Farey té una àrea equivalent a 1.Plantilla:Sfn

Si r₁=p/q i r₂=p'/q' s'interpreten com a vectors (p,q) en el pla x,y, l'àrea de A(p/q,p'/q') està donat per qp' - q'p. Com que qualsevol fracció afegida entre dues fraccions de seqüències de Farey consecutives anteriors es calcula com a mediant (⊕)

A(r₁,r₁⊕r₂) = A(r₁,r₁) + A(r₁,r₂) = A(r₁,r₂) = 1 (a partir de r₁=1/0 i r₂=0/1 la seva àrea ha de ser 1).

Des de:$\frac{c}{d}-\frac{a}{b}=\frac{bc-ad}{bd},$

això equival a dir això

$bc-ad=1$.

Així Plantilla:Sfrac i Plantilla:Sfrac són veïns F₅, i la seva diferència és Plantilla:Sfrac.

El contrari també és cert. Si

$bc-ad=1$

per a nombres enters positius a,b,c i d amb a < b i c < d llavors Plantilla:Sfrac i Plantilla:Sfrac seran els veïns de la seqüència d'ordre Farey max(b,d).

Si Plantilla:Sfrac és veí de Plantilla:Sfrac i Plantilla:Sfrac en alguna seqüència de Farey, amb

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

llavors Plantilla:Sfrac és la fracció mediant de Plantilla:Sfrac i Plantilla:Sfrac ; en altres paraules,

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

Això es desprèn fàcilment de la propietat anterior, ja que si Plantilla:Nowrap, llavors Plantilla:Nowrap, Plantilla:Nowrap, Plantilla:Nowrap.

Es dedueix que si Plantilla:Sfrac i Plantilla:Sfrac són veïns d'una seqüència de Farey, llavors el primer terme que apareix entre ells a mesura que s'incrementa l'ordre de la seqüència de Farey és

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

que apareix per primera vegada a la seqüència de Farey d'ordre Plantilla:Nowrap.

Així el primer terme que apareix entre Plantilla:Sfrac i Plantilla:Sfrac és Plantilla:Sfrac, que apareix a F₈.

El nombre total de parelles de veïns de Farey F_n és 2|F_n|-3.

L'arbre Stern-Brocot és una estructura de dades que mostra com es construeix la seqüència 0 (= Plantilla:Sfrac) i 1 (= Plantilla:Sfrac), prenent mediants successius.

Veïns de Farey i fraccions contínues

Les fraccions que apareixen com a veïnes en una seqüència de Farey tenen expansions de fraccions contínues estretament relacionades. Cada fracció té dues expansions de fraccions contínues: en una, el terme final és 1; en l'altre el termini final és superior a 1. Si Plantilla:Sfrac, que apareix per primera vegada a la seqüència de Farey F_q, té expansions de fraccions contínues

[0; a₁, a₂, ..., a_{n − 1}, a_n, 1]

[0; a₁, a₂, ..., a_{n − 1}, a_n + 1]

llavors el veí més proper de Plantilla:Sfrac en F_q (que serà el seu veí amb el denominador més gran) té una expansió de fracció contínua

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

i el seu altre veí té una expansió continuada de fraccions

[0; a₁, a₂, ..., a_{n − 1}]

Per exemple, Plantilla:Sfrac té les dues expansions de fraccions contínues Plantilla:Nowrap i Plantilla:Nowrap, i els seus veí en F₈ és Plantilla:Sfrac, que es pot ampliar com Plantilla:Nowrap; i Plantilla:Sfrac, que es pot ampliar com Plantilla:Nowrap.

Fraccions de Farey i el mínim comú múltiple

El mcm es pot expressar com els productes de les fraccions de Farey com

$\text{mcm}[1,2,...,N]=e^{\psi (N)}=\frac{1}{2}{(\prod _{r\in F_N,0<r\le 1/2}2\sin (\pi r))}^2$

on $\psi (N)$ és la segona funció de Txebixov.Plantilla:SfnPlantilla:Sfn

Fraccions de Farey i màxim comú divisor

Com que la funció φ d'Euler està directament connectada amb el mcd, també ho és el nombre d'elements a F_n.

$|F_n|=1+\sum _{m=1}^n\phi (m)=1+\sum _{m=1}^n\sum _{k=1}^m\text{mcd}(k,m)\cos 2\pi \frac{k}{m}.$

Per a tres fraccions de Farey qualsevol Plantilla:Sfrac, Plantilla:Sfrac i Plantilla:Sfrac la següent identitat entre els mcd dels determinants de la matriu 2x2 en valor absolut es compleix:Plantilla:Sfn

$\text{mcd}(\Vert \begin{array}{cc}a& c\\ b& d\end{array}\Vert ,\Vert \begin{array}{cc}a& e\\ b& f\end{array}\Vert )=\text{mcd}(\Vert \begin{array}{cc}a& c\\ b& d\end{array}\Vert ,\Vert \begin{array}{cc}c& e\\ d& f\end{array}\Vert )=\text{mcd}(\Vert \begin{array}{cc}a& e\\ b& f\end{array}\Vert ,\Vert \begin{array}{cc}c& e\\ d& f\end{array}\Vert )$Plantilla:Sfn

Aplicacions

Les seqüències de Farey són molt útils per trobar aproximacions racionals de nombres irracionals. Per exemple, la construcció per EliahouPlantilla:Sfn d'un límit inferior de la durada dels cicles no trivials en el procés 3x+1 utilitza seqüències de Farey per calcular una expansió de fracció contínua del nombre log₂(3).

En sistemes físics amb fenòmens de ressonància, les seqüències de Farey proporcionen un mètode molt elegant i eficient per calcular ubicacions de ressonància en 1DPlantilla:Sfn i 2D.Plantilla:Sfn

Les seqüències de Farey són destacades en els estudis de planificació de camins de qualsevol angle en quadrícules de cel·les quadrades, per exemple en caracteritzar la seva complexitat computacional o optimitat. La connexió es pot considerar en termes de camins r-restringits, és a dir, camins formats per segments de línia que travessen cadascun com a màxim $r$ files i com a màxim $r$ columnes de cel·les. Sigui $Q$ el conjunt de vectors $(q,p)$ tal que $1\le q\le r$, $0\le p\le q$, i $p$, $q$ són coprimers. Sigui $Q*$ el resultat del reflex $Q$ en la línea $y=x$. Sigui $S=\{(\pm x,\pm y):(x,y)\in Q\cup Q*\}$. Aleshores, qualsevol camí r-restringit per r es pot descriure com una seqüència de vectors a partir de $S$. Hi ha una bijecció entre $Q$ i la seqüència de Farey d'ordre $r$ donat per $(q,p)$ mapejat a $\frac{p}{q}$.

Per a cercles de Ford

Hi ha una connexió entre la seqüència de Farey i els cercles de Ford.

Per cada fracció Plantilla:Sfrac (en els seus termes més baixos) hi ha un cercle de Ford C[[[:Plantilla:Sfrac]]], que és el cercle amb radi 1/(2q²) i el centre a (Plantilla:Sfrac, Plantilla:Sfrac). Dos cercles de Ford per a diferents fraccions són disjunts o tangents entre si; dos cercles de Ford mai es tallen. Si 0 < Plantilla:Sfrac < 1 llavors els cercles de Ford que són tangents a C[[[:Plantilla:Sfrac]]] són precisament els cercles de Ford per a les fraccions que són veïnes de Plantilla:Sfrac en alguna seqüència de Farey.

• Comparació de cercles de Ford i un diagrama de Farey amb arcs circulars per a n d'1 a 9. Cada arc talla els seus cercles corresponents en angle recte. A la imatge SVG, passeu el cursor per sobre d'un cercle o una corba per ressaltar-lo i els seus termes
  Comparació de cercles de Ford i un diagrama de Farey amb arcs circulars per a n d'1 a 9. Cada arc talla els seus cercles corresponents en angle recte. A la imatge SVG, passeu el cursor per sobre d'un cercle o una corba per ressaltar-lo i els seus termes
• Tamís d'Apol·loni (0,0,1,1) i el diagrama de ressonància de Farey
  Tamís d'Apol·loni (0,0,1,1) i el diagrama de ressonància de Farey

Així C[[[:Plantilla:Sfrac]]] és tangent a C[[[:Plantilla:Sfrac]]], C[[[:Plantilla:Sfrac]]], C[[[:Plantilla:Sfrac]]], C[[[:Plantilla:Sfrac]]] etc.

Els cercles de Ford també apareixen al tamís d'Apol·loni (0,0,1,1). La imatge superior ho il·lustra juntament amb les línies de ressonància de Farey.Plantilla:Sfn

Hipòtesi de Riemann

Les seqüències de Farey s'utilitzen en dues formulacions equivalents de la hipòtesi de Riemann. Suposem els termes de $F_n$ són $\{a_{k,n}:k=0,1,\dots ,m_n\}$. Definim $d_{k,n}=a_{k,n}-k/m_n$, el altres paraules $d_{k,n}$ és la diferència entre el terme k-èssim de l'enèsima seqüència de Farey i el k-è membre d'un conjunt del mateix nombre de punts, distribuïts uniformement en l'interval unitari. El 1924 Jérôme Franel va demostrar que la declaració.Plantilla:Sfn

$\sum _{k=1}^{m_n}{d}_{k,n}^2=O(n^r)\mathrm{\forall }r>-1$

és equivalent a la hipòtesi de Riemann, i llavors Edmund Landau va remarcar (just després de l'article de Franel) que l'afirmacióPlantilla:Sfn

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

també és equivalent a la hipòtesi de Riemann.

Altres sumes que impliquen fraccions de Farey

La suma de totes les fraccions de Farey d'ordre n és la meitat del nombre d'elements:

$\sum _{r\in F_n}r=\frac{1}{2}|F_n|.$

La suma dels denominadors de la seqüència de Farey és el doble de la suma dels numeradors i es relaciona amb la funció φ d'Euler:

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

que va ser conjecturada per Harold L. Aaron el 1962 i demostrada per Jean A. Blake el 1966. Una prova d'una línia de la conjectura de Harold L. Aaron és la següent.

La suma dels numeradors és $1+\sum _{2\le b\le n}\sum _{(a,b)=1}a=1+\sum _{2\le b\le n}b\frac{\phi (b)}{2}$. La suma dels denominadors és $2+\sum _{2\le b\le n}\sum _{(a,b)=1}b=2+\sum _{2\le b\le n}b\phi (b)$. El quocient de la primera suma per la segona suma és $\frac{1}{2}$.

Siguin b_j els denominadors ordenats de F_n, llavors:Plantilla:Sfn

$\sum _{j=0}^{|F_n|-1}\frac{b_j}{b_{j+1}}=\frac{3|F_n|-4}{2}$

i

$\sum _{j=0}^{|F_n|-1}\frac{1}{b_{j+1}{b}_j}=1.$

Siguin a_j/b_j la j-ena fraccion de Farey en F_n, llavors

$\sum _{j=1}^{|F_n|-1}(a_{j-1}{b}_{j+1}-a_{j+1}{b}_{j-1})=\sum _{j=1}^{|F_n|-1}\Vert \begin{array}{cc}{a}_{j-1}& a_{j+1}\\ b_{j-1}& b_{j+1}\end{array}\Vert =3(|F_n|-1)-2n-1,$

que es demostra a [Hall, Shiu 2003, p. 2009-223].Plantilla:Sfn També segons aquesta referència el terme dins de la suma es pot expressar de moltes maneres diferents:

$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}=\lfloor \frac{n+b_{j-1}}{b_j}\rfloor ,$

obtenint així moltes sumes diferents sobre els elements de Farey amb el mateix resultat. Utilitzant la simetria al voltant de 1/2, la suma anterior es pot limitar a la meitat de la seqüència com

$\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ó de Mertens es pot expressar com una suma sobre fraccions de Farey com

$M(n)=-1+\sum _{a\in {ℱ}_n}{e}^{2\pi ia}$ on ${ℱ}_n$ és la seqüència de Farey d'ordre n.

Aquesta fórmula s'utilitza en la demostració del teorema de Franel-Landau.Plantilla:Sfn

El terme següent

Existeix un algorisme sorprenentment senzill per generar els termes de F_n en ordre tradicional (creixent) o en ordre no tradicional (descendent). L'algorisme calcula cada entrada successiva en termes de les dues entrades anteriors utilitzant la propietat mediant donada anteriorment. Si Plantilla:Sfrac i Plantilla:Sfrac  són les dues entrades donades, i Plantilla:Sfrac és la següent entrada desconeguda, llavors Plantilla:Sfrac = Plantilla:Sfrac. A partir de Plantilla:Sfrac  és en termes més baixos, ha d'haver un nombre enter k tal que kc = a + p i kd = b + q, donant p = kc − a i q = kd − b. Si considerem que p i q són funcions de k, aleshores

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

per tant, com més gran és k, més a prop Plantilla:Sfrac arriba a Plantilla:Sfrac.

Per donar el següent terme de la seqüència, k ha de ser el més gran possible, subjecte a kd − b ≤ n (ja que només estem considerant nombres amb denominadors no superiors a n), de manera que k és el nombre enter més gran ≤Plantilla:Sfrac. Si tornem a posar aquest valor de k a les equacions de p i q, s'obté

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

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

Això s'implementa a Python de la següent manera:

def farey_sequence(n: int, descending: bool = False) -> None:
 """Imprimeix la seqüència enèima de Farey. Permet pujar o baixar."""
 (a, b, c, d) = (0, 1, 1, n)
 if descending:
 (a, c) = (1, n - 1)
 print("{0}/{1}".format(a, b))
 while (c <= n and not descending) or (a > 0 and descending):
 k = (n + b) // d
 (a, b, c, d) = (c, d, k * c - a, k * d - b)
 print("{0}/{1}".format(a, b))

Les cerques de força bruta per a solucions d'equacions diofàntiques en racionals sovint poden aprofitar la sèrie de Farey (per cercar només formes reduïdes). Les línies marcades amb (*) també es poden modificar per incloure dos termes adjacents qualsevol per generar termes només més grans (o més petits) que un terme determinat.Plantilla:Sfn

Bibliografia

• Plantilla:Ref-llibre
• Plantilla:Ref-publicació
• Plantilla:Ref-llibre
• Plantilla:Ref-publicació (pàgina 1-20 Plantilla:PDF), (pàgina 21-38 Plantilla:PDF)
• Plantilla:Ref-llibre
• Plantilla:Ref-publicació
• Plantilla:Ref-publicació
• Plantilla:Ref-publicació
• Plantilla:Ref-llibre En particular, vegeu §4.5 (p. 115-123), Problema extra 4.61 (p. 150, 523-524), §4.9 (p. 133-139), §9.3, Problema 9.3.6 (p. 462-463).
• Plantilla:Ref-llibre
• Plantilla:Ref-publicació
• Plantilla:Ref-llibre
• Plantilla:Ref-publicació
• Plantilla:Ref-llibre
• Plantilla:Ref-llibre
• Plantilla:Ref-llibre
• Plantilla:Ref-publicació
• Plantilla:Ref-publicació
• Plantilla:Ref-publicació
• Plantilla:Ref-llibre
• Plantilla:Ref-publicació
• Plantilla:Ref-llibre
• Plantilla:Ref-publicació

Vegeu també

• Arbre de Stern-Brocot
• Funció φ d'Euler
• Funció signe d'interrogació

Enllaços externs

• Plantilla:Ref-publicació
• Plantilla:OEIS el
• Plantilla:Ref-web Revisa els isomorfismes de l'arbre de Stern-Brocot.