Farey opeenvolging

In wiskunde, de Farey reeks van orde n is de reeks volledig gereduceerd fracties tussen 0 en 1, die bij in de laagste termen hebben delers kleiner dan of gelijk aan n, gerangschikt in volgorde van toenemende grootte.

Elke Farey reeks begint met de waarde 0, aangeduid met de fractie /1 en eindigt met de waarde 1, aangeduid met de fractie /1.

Een Farey reeks wordt ook wel een Farey reeks, die niet strikt correct, omdat de termen niet worden gesommeerd.

Voorbeelden

De Farey sequenties van orders 1-8 zijn:

Geschiedenis

Farey sequenties zijn vernoemd naar de Britse geoloog John Farey, Sr., wiens brief over deze sequenties werd gepubliceerd in het Philosophical Magazine in 1816. Farey vermoed, zonder het aanbieden van het bewijs, dat elke nieuwe term in een Farey volgorde uitbreiding is de mediant van zijn buren . Brief Farey werd voorgelezen door Cauchy, die een bewijs geleverd in zijn Oefeningen de mathématique en toegeschreven dit resultaat naar Farey. In feite, een andere wiskundige, Charles Haros, had vergelijkbare resultaten gepubliceerd in 1802, die niet bekend waren ofwel Farey of Cauchy. Dus het was een historisch toeval dat de naam van Farey's verbonden met deze sequenties. Dit is een voorbeeld van de wet van Stigler eponymy.

Properties

Sequentielengte en de index van een fractie

De Farey opeenvolging van orde n bevat alle leden van de Farey sequenties van lagere orders. Met name bevat Fn alle leden van Fn-1 en bevat ook een extra fractie voor elk getal dat kleiner is dan n en coprime n. Aldus F6 bestaat uit F5 met de fracties 06/01 en 06/05.

De middellange termijn van een Farey reeks Fn is altijd 02/01, voor n & gt; 1.

Hieruit kunnen we de lengtes van Fn-1 en Fn betrekking Euler's totient functie:

De omstandigheid dat | F1 | = 2, kunnen we een uitdrukking voor de duur van Fn leiden:

We hebben ook :

en een Möbius inversie formule:

waarbij μ is de nummer-theoretische Möbius functie, en is de vloer functie.

De asymptotische gedrag van | Fn | is:

De index van een breuk in de Farey reeks is eenvoudig de positie inneemt die in de sequentie. Dit is van bijzonder belang omdat het wordt gebruikt in een alternatieve formulering van de Riemann hypothese zie hieronder. Diverse nuttige eigenschappen te volgen:

Farey buren

Fracties die naburige termen in een Farey sequentie bekend als een Farey pair en hebben de volgende eigenschappen.

Als a / b en c / d buren in een Farey reeks, met a / b & lt; c / d, dan is hun tijdsverschil c / d - a / b gelijk aan 1 / bd. Sinds

Dit is als zeggen dat

Dus 1/3 en 2/5 zijn buren in F5, en hun verschil is 1/15.

Het omgekeerde is ook waar. Als

voor positieve gehele getallen a, b, c en d met een & lt; b en c & lt; d dan a / b en c / d zijn buren in de Farey reeks van orde max.

Indien p / q buren a / b en c / d in sommige Farey reeks, met

dan p / q de mediant van a / b en c / d in andere woorden,

Dit volgt eenvoudig uit het vorige pand, want als BP-AQ = qc-pd = 1, dan bp + pd = QC + aq, p = q, p / q = a + c / b + d

Hieruit volgt dat als a / b en c / d zijn buren in een Farey volgorde dan is de eerste term die verschijnt tussen hen als de volgorde van de Farey sequentie wordt verhoogd is

die voor het eerst verschijnt in het Farey volgorde van de orde b + d.

Dus de eerste termijn te verschijnen tussen 1/3 en 2/5 is 08/03, die op F8 verschijnt.

Het Stern-Brocot boom is een datastructuur toont hoe de sequentie is opgebouwd uit 0 en 1, door middel van opeenvolgende mediants.

Fracties die als buren in een Farey volgorde verschijnen hebben nauw verwant voortdurende fractie uitbreidingen. Elke fractie heeft twee verdere fractie uitbreidingen in een van de laatste termijn is 1; in het andere de laatste termijn groter dan 1. Indien p / q, die eerst verschijnt in Farey reeks Fq is kettingbreuk expansies

dan is de naaste buur van de p / q in Fq heeft een voortdurende fractie expansie

en de andere buurman heeft een voortdurende fractie expansie

Aldus 3/8 heeft twee kettingbreuk en uitbreidingen, en zijn buren in F8 worden 05/02, die kan worden uitgebreid; en 1/3, die kan worden uitgebreid.

Toepassingen

Farey sequenties zijn zeer nuttig om een ​​rationele benadering van irrationele getallen.

In physics systemen die resonantiefenomenen Farey sequenties geven een zeer elegante en efficiënte methode om resonantie te plaatsen in 1D en 2D berekenen

Ford cirkels

Er is een verband tussen Farey sequentie en Ford cirkels.

Voor elke fractie p / q is er een Ford cirkel C, die de cirkel met straal 1 en / center aan (p / q, 1 /). Twee Ford kringen voor verschillende fracties ofwel disjunct of zij raken aan elkaar twee Ford cirkels nooit kruisen. Als 0 & lt; p / q & lt; 1 dan is de Ford cirkels die rakend zijn aan C zijn precies de Ford kringen voor fracties die zijn buren van p / q in sommige Farey volgorde.

Aldus C raakt aan C, C, C, C etc.

Riemann-hypothese

Farey sequenties worden in twee equivalente formuleringen van de Riemann hypothese. Stel dat de voorwaarden van zijn. Definieer, met andere woorden het verschil tussen de term k van de n Farey sequentie en de k lid van een set hetzelfde aantal punten, gelijkmatig verdeeld eenheidsinterval. In 1924 bewees Jérôme Franel dat de verklaring

is gelijk aan de Riemann hypothese en Edmund Landau opgemerkt dat de verklaring

is gelijk aan de Riemann hypothese.

Volgende termijn

Een verrassend eenvoudig algoritme bestaat om de voorwaarden van Fn in een traditionele orde of niet-traditionele orde te genereren. Het algoritme berekent elke volgende invoer in termen van de vorige twee items die mediant eigenschap hierboven. Als a / b en c / d zijn de twee gegeven items en p / q de onbekende volgende invoer, dan c / d = a + p / b + q. Sinds c / d is in de laagste termen, moet er een integer k zodanig zijn dat kc = a + p en kd = b + q, waardoor p = kc - een en q = kd - b. Als we kijken naar p en q zijn functies van k, dan

zodat de grotere k krijgt, hoe dichter p / q krijgt c / d.

Geven de volgende in de reeks k moet zo groot mogelijk, onder kd zijn - b ≤ n, dus k is het grootste gehele getal ≤ n + b / d. Putting deze waarde van k terug in de vergelijkingen voor p en q geeft

Dit is geïmplementeerd in Python als:

Brute-force zoekopdrachten naar oplossingen voor Diophantische vergelijkingen in rationals kunnen vaak profiteren van de Farey serie. De lijnen gemarkeerd kan ook worden aangepast om twee aangrenzende termen omvatten teneinde termen alleen groter is dan een bepaalde periode te genereren.

(0)
(0)
Commentaren - 0
Geen commentaar

Voeg een reactie

smile smile smile smile smile smile smile smile
smile smile smile smile smile smile smile smile
smile smile smile smile smile smile smile smile
smile smile smile smile
Tekens over: 3000
captcha