Generalizations of the floor and ceiling functions using the Stern-Brocot tree
| Document type: | Researchreports |
|---|---|
| Full text: | |
| Author(s): | Håkan Lennerstad, Lars Lundberg |
| Title: | Generalizations of the floor and ceiling functions using the Stern-Brocot tree |
| Series: | Research Report |
| Year: | 2006 |
| Issue: | 2 |
| ISSN: | 1103-1581 |
| Organization: | Blekinge Institute of Technology |
| Department: | School of Engineering - Dept. Mathematics and Science (Sektionen för teknik – avd. för matematik och naturvetenskap) School of Engineering S- 371 79 Karlskrona +46 455 38 50 00 http://www.tek.bth.se/ |
| Authors e-mail: | hln@bth.se, llu@bth.se |
| Language: | English |
| Abstract: | We consider a fundamental number theoretic problem where practial applications abound. We decompose any rational number a/b in c ratios as evenly as possible while maintaining the sum of numerators and the sum of denominators. The minimum and maximum of the ratios give rational estimates of a/b from below and from above. The case c=b gives the usual floor and ceiling functions. We furthermore define the max-min-difference, which is zero iff c≤GCD(a,b), quantifying the distance to relative primality. A main tool for investigating the properties of these quantities is the Stern-Brocot tree, where all positive rational numbers occur in lowest terms and in size order. We prove basic properties such that there is a unique decomposition that gives both the minimum and the maximum. It turns out that this decomposition contains at most three distinct ratios. The problem has arisen in a generalization of the 4/3-conjecture in computer science. |
| Summary in Swedish: | Vi studerar ett fundamentalt talteoretiskt problem med många tillämpningar. Ett bråk a/b delas upp så jämnt som möjligt i en mängd av c delbråk där summan av nämnarna är a och summan av täljarna är b. Minimum av bråken generaliserar golvfunktionen av a/b och maximum generaliserar analogt takfunktionen. Vi definerar även max-min-skillnaden, som är noll om och endast om c är högst största gemensamam delaren av a och b. För större c kvantifierar denna funktion avståndet till delbarhet. Stern-Brocots träd används för att bevisa grundläggande egenskaper för de tre storheterna. Problemet har uppkommit vid en generalisering av 4/3-satsen i datorsystemteori. |
| Subject: | Mathematics\Discrete Mathematics |
| Keywords: | floor function, ceiling function, mediant, relative primality, Stern-Brocot tree |
| URN: | urn:nbn:se:bth-00318 |
