Sequência de Farey

Uma seqüência de Farey (no Brasil) ou sucessão de Farey (em Portugal) é uma sucessão matemática de frações irredutíveis entre 0 e 1 que tem um denominador menor ou igual a n em ordem crescente.

Cada seqüência de Farey começa no 0, representado pela fração ⁰⁄₁, e termina no 1, representado pela fração ¹⁄₁, ainda que alguns autores só podem omitir ambos os términos.

Construção

Uma boa maneira algorítmica de construir a seqüência de Farey para um número n (por exemplo, o 4):

• Construímos umas frações com todas as combinações possíveis dos números do 1 ao 4:

¹⁄₁, ¹⁄₂, ¹⁄₃, ¹⁄₄; ²⁄₁, ²⁄₂, ²⁄₃, ²⁄₄; ³⁄₁, ³⁄₂, ³⁄₃, ³⁄₄; ⁴⁄₁, ⁴⁄₂, ⁴⁄₃, ⁴⁄₄

• Eliminamos aquelas frações superiores a 1 (ou em outras palavras, nas que o numerador seja maior que o denominador):

¹⁄₁, ¹⁄₂, ¹⁄₃, ¹⁄₄; ²⁄₂, ²⁄₃, ²⁄₄; ³⁄₃, ³⁄₄; ⁴⁄₄;

• Simplificamos todas as frações, descartando as repetidas:

¹⁄₁, ¹⁄₂, ¹⁄₃, ¹⁄₄; ²⁄₃; ³⁄₄;

• Ordenamos o resultado de menor ao maior, agregando o 0 (⁰⁄₁) ao princípio:

⁰⁄₁, ¹⁄₄, ¹⁄₃, ¹⁄₂, ²⁄₃, ³⁄₄, ¹⁄₁

Nesse sentido, a sequência de Farey mostra-se interessante e bastante conhecida por matemáticos e cientistas da computação, sendo que é comum ela ser implementada por meio de algoritmos nas mais diversas linguagens de programação.

Exemplos

As sequências de Farey de ordem 1 até 8 são:

F₁ = { 01_, 11 }

F₂ = { 01_, 12_, 11 }

F₃ = { 01_, 13_, 12_, 23_, 11 }

F₄ = { 01_, 14_, 13_, 12_, 23_, 34_, 11 }

F₅ = { 01_, 15_, 14_, 13_, 25_, 12_, 35_, 23_, 34_, 45_, 11 }

F₆ = { 01_, 16_, 15_, 14_, 13_, 25_, 12_, 35_, 23_, 34_, 45_, 56_, 11 }

F₇ = { 01_, 17_, 16_, 15_, 14_, 27_, 13_, 25_, 37_, 12_, 47_, 35_, 23_, 57_, 34_, 45_, 56_, 67_, 11 }

F₈ = { 01_, 18_, 17_, 16_, 15_, 14_, 27_, 13_, 38_, 25_, 37_, 12_, 47_, 35_, 58_, 23_, 57_, 34_, 45_, 56_, 67_, 78_, 11 }

História

A história da "série de Farey" é muito curiosa — Hardy & Wright (1979) Capítulo III

... mais uma vez o homem cujo nome foi dado a uma relação matemática não era o descobridor até onde nos mostram os registros. — Beiler (1964) Capítulo XVI

As sequências de Farey são nomeadas a partir do geólogo Britânico John Farey, que teve suas cartas sobre essas sequências publicadas na revista Philosophical Magazine em 1816. Farey conjecturou, sem apresentar provas, que cada novo termo na expansão de uma sequência de Farey é a mediante de seus vizinhos. A carta de Farey foi lida por Cauchy, que forneceu uma prova em seus Exercices de mathématique, e atribuiu este resultado a Farey. Na realidade, outro matemático, Charles Haros, havia publicado resultados similares em 1802 que não eram conhecidos nem por Farey ou por Cauchy. Portanto foi um acidente histórico que ligou o nome de Farey a essas sequências. Este é um exemplo da Lei de Stigler.