Stern Tree - Broko

Stern-Brokaw-træet er en måde at arrangere alle ikke-negative irreducerbare brøker på hjørnerne af et ordnet uendeligt binært træ .

Ved hver knude på Stern-Brocko-træet (nogle gange også kaldet Farey-træet ) er der en median af fraktioner og , der står i venstre og højre øvre knude tættest på denne knude. Det første stykke af Stern-Broco-træet ser i dette tilfælde sådan ud: ${\frac {m+m'}{n+n'))$ ${\frac {m}{n}}$ ${\frac {m'}{n'}}$

Tæt på Stern-Brocko-træet er Calkin-Wilf-træet , hvor brøken er roden, og alle andre noder er udfyldt i henhold til følgende algoritme: hver toppunkt har to efterkommere: venstre og højre . ${\frac {1}{1))$ ${\frac {m}{n}}$ ${\frac {m}{m+n))$ ${\frac {m+n}{n))$

Historie

I bogen Concrete Mathematics af R. Graham , D. Knuth , O. Patashnik er opdagelsen af "Stern-Broko-træet" forbundet med navnene på Moritz Stern (1858) og Achilles Broko (1860). Imidlertid var en lignende konstruktion i form af et "Calkin-Wilph-træ" kendt selv for gamle græske matematikere. Det er beskrevet under navnet "genereringen af alle relationer fra forholdet af lighed som fra moderen og roden" i to matematiske undersøgelser af det 2. århundrede. n. e. tilhørende Nicomachus af Geras og Theon af Smyrna . Theon rapporterer, at dette design var kendt af Eratosthenes fra Cyrene , en berømt videnskabsmand, der levede i det 3. århundrede f.Kr. f.Kr e.

Egenskaber

Alle fraktioner i Culkin-Wilf og Stern-Brokaw træer er irreducerbare.
Hver irreducerbar fraktion optræder nøjagtigt én gang i træet.

For et Culkin-Wilf-træ er disse egenskaber let bevist ved at bemærke, at hvert trin i træet mod roden svarer til et elementært trin med at trække et mindre tal fra et større i Euklids algoritme for at finde den største fælles divisor.

For Stern-Brocko-træet er beviset baseret på følgende lemma: hvis er fraktioner ved to naboknuder af træet, så . $p_1/q_1<p_2/q_2$ $q_1p_2-q_2p_1=1$

Stern-Broko nummersystemet

Du kan bruge symbolerne L og R til at identificere venstre og højre gren, når du bevæger dig ned i træet fra roden, brøken 1/1, til en bestemt brøk. Så får hver positiv brøk en unik repræsentation i form af en streng bestående af tegnene " R " og " L " ( brøken 1/1 svarer til en tom streng ). Vi vil kalde en sådan repræsentation af positive rationelle tal for Stern-Broko-talsystemet . For eksempel svarer notationen LRRL til brøken 5/7.

Se også

Litteratur

Aigner M. , Ziegler G. Beviser fra bogen. Det bedste bevis fra Euklids tid til i dag . - M . : Mir, 2006. - S. 105 -109. — 256 s. — ISBN 5-03-003690-3 . .
Graham R., Knut D., Patashnik O. Concrete Mathematics. Grundlaget for informatik. — M .: Mir, 1998. — 704 s. — ISBN 5-03-001793-3 . .
Shchetnikov AI Algoritme til at udfolde alle numeriske relationer fra lighedsrelationen og Platons ideelle tal // ΣΧΟΛΗ . - 2008. - T. 2 . - S. 55-74 . — ISSN 1995-4328 .
Brocot A. Calcul des rouages par tilnærmelse, 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 .