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 01, e termina no 1, representado pela fração ¹⁄1, ainda que alguns autores só podem omitir ambos os términos.

Construção

editar

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

11, 12, 13, 14; 21, 22, 23, 24; 31, 32, 33, 34; 41, 42, 43, 44
  • Eliminamos aquelas frações superiores a 1 (ou em outras palavras, nas que o numerador seja maior que o denominador):
11, 12, 13, 14; 22, 23, 24; 33, 34; 44;
  • Simplificamos todas as frações, descartando as repetidas:
11, 12, 13, 14; 23; 34;
  • Ordenamos o resultado de menor ao maior, agregando o 0 (01) ao princípio:
01, 14, 13, 12, 23, 34, 11

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

editar

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

F1 = { 01, 11 }
F2 = { 01, 12, 11 }
F3 = { 01, 13, 12, 23, 11 }
F4 = { 01, 14, 13, 12, 23, 34, 11 }
F5 = { 01, 15, 14, 13, 25, 12, 35, 23, 34, 45, 11 }
F6 = { 01, 16, 15, 14, 13, 25, 12, 35, 23, 34, 45, 56, 11 }
F7 = { 01, 17, 16, 15, 14, 27, 13, 25, 37, 12, 47, 35, 23, 57, 34, 45, 56, 67, 11 }
F8 = { 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

editar
A história da "série de Farey" é muito curiosa — Hardy & Wright (1979) Capítulo III[1]
... 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[2]

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.[2] Portanto foi um acidente histórico que ligou o nome de Farey a essas sequências. Este é um exemplo da Lei de Stigler.

Referências

editar
  1. Hardy, G.H. & Wright, E.M. (1979) An Introduction to the Theory of Numbers (Fifth Edition). Oxford University Press. ISBN 0-19-853171-0
  2. a b Beiler, Albert H. (1964) Recreations in the Theory of Numbers (Second Edition). Dover. ISBN 0-486-21096-0. Cited in Farey Series, A Story at Cut-the-Knot
  Este artigo sobre matemática é um esboço. Você pode ajudar a Wikipédia expandindo-o.