Stern Tree - Broko

Stern-Brokaw-trädet är ett sätt att ordna alla icke-negativa irreducerbara fraktioner vid hörnen på ett ordnat oändligt binärt träd .

Vid varje nod av Stern-Brocko-trädet (ibland även kallat Farey-trädet ) finns en median av fraktioner och , som står i den vänstra och högra övre noden närmast denna nod. Den första biten av Stern-Broco-trädet ser i det här fallet ut så här: ${\frac {m+m'}{n+n'))$ ${\frac {m}{n}}$ ${\frac {m'}{n'}}$

Nära i konstruktionen till Stern-Brocko-trädet är Calkin-Wilf-trädet , där bråkdelen är roten, och alla andra noder är fyllda enligt följande algoritm: varje vertex har två avkomlingar: vänster och höger . ${\frac {1}{1))$ ${\frac {m}{n}}$ ${\frac {m}{m+n))$ ${\frac {m+n}{n))$

Historik

I boken Concrete Mathematics av R. Graham , D. Knuth , O. Patashnik förknippas upptäckten av "Stern-Broko-trädet" med namnen Moritz Stern (1858) och Achilles Broko (1860). Men en liknande konstruktion i form av ett "Calkin-Wilph-träd" var känd även för antika grekiska matematiker. Det beskrivs under namnet "genereringen av alla relationer från förhållandet av jämlikhet som från modern och roten" i två matematiska undersökningar av det 2: a århundradet. n. e. tillhörande Nicomachus av Geras och Theon av Smyrna . Theon rapporterar att denna design var känd för Eratosthenes från Cyrene , en berömd vetenskapsman som levde på 300-talet f.Kr. före Kristus e.

Egenskaper

Alla fraktioner i Culkin-Wilf- och Stern-Brokaw-träden är irreducerbara.
Varje irreducerbar fraktion visas exakt en gång i trädet.

För ett Culkin-Wilf-träd är dessa egenskaper lätt bevisade genom att notera att varje steg i trädet mot roten motsvarar ett elementärt steg att subtrahera ett mindre tal från ett större i Euklids algoritm för att hitta den största gemensamma divisorn.

För Stern-Brocko-trädet är beviset baserat på följande lemma: om är fraktioner vid två närliggande noder av trädet, då . $p_1/q_1<p_2/q_2$ $q_1p_2-q_2p_1=1$

Stern-Broko nummersystem

Du kan använda symbolerna L och R för att identifiera vänster och höger grenar när du flyttar ner i trädet från roten, bråkdelen 1/1, till någon specifik bråkdel. Sedan får varje positivt bråk en unik representation i form av en sträng som består av tecknen " R " och " L " ( bråket 1/1 motsvarar en tom sträng ). Vi kommer att kalla en sådan representation av positiva rationella tal för Stern-Broko-talsystemet . Till exempel motsvarar notationen LRRL bråket 5/7.

Se även

Litteratur

Aigner M. , Ziegler G. Bevis från boken. Det bästa beviset från Euklids tid till våra dagar . - M . : Mir, 2006. - S. 105 -109. — 256 sid. — ISBN 5-03-003690-3 . .
Graham R., Knut D., Patashnik O. Concrete Mathematics. Grunden för informatik. — M .: Mir, 1998. — 704 sid. — ISBN 5-03-001793-3 . .
Shchetnikov AI Algoritm för att utveckla alla numeriska relationer från likhetsrelationen och Platons idealtal // ΣΧΟΛΗ . - 2008. - T. 2 . - S. 55-74 . — ISSN 1995-4328 .
Brocot A. Calcul des rouages par approximation, nouvelle méthode // Revue Chonométrique. - 1861. - T. 3 . - S. 186-194 .
Stern M. Über eine zahlentheoretische Funktion // Journal für die reine und angewandte Mathematik. - 1858. - T. 55 . - S. 193-220 .

Länkar

The Stern - Brocot eller Farey Tree
Knop K. Icke-binärt system // Hemdator. - 2001. - Nr 8 . Arkiverad från originalet den 12 mars 2007.
Online demonstrator för att approximera rationella tal med hjälp av Stern-trädet - Brokaw