Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Generalizations of the floor and ceiling functions using the Stern-Brocot tree
Blekinge Institute of Technology, School of Engineering, Department of Mathematics and Natural Sciences.
Blekinge Institute of Technology, School of Engineering, Department of Systems and Software Engineering.
2006 (English)Report (Refereed)
Abstract [en]

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.

Abstract [sv]

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.

Place, publisher, year, edition, pages
2006.
Series
Blekinge Tekniska Högskola Forskningsrapport, ISSN 1103-1581 ; 2
Keyword [en]
floor function, ceiling function, mediant, relative primality, Stern-Brocot tree
National Category
Mathematical Analysis
Identifiers
URN: urn:nbn:se:bth-00318Local ID: oai:bth.se:forskinfo5703F14DE868B72DC1257141002EE53COAI: oai:DiVA.org:bth-00318DiVA: diva2:833712
Available from: 2015-06-25 Created: 2006-03-30 Last updated: 2015-06-30Bibliographically approved

Open Access in DiVA

fulltext(523 kB)142 downloads
File information
File name FULLTEXT01.pdfFile size 523 kBChecksum SHA-512
2db6bca73a496365293fc5ef313558b16dd791d0e139232d0f2f715b9557503fd591140b8b96449a50b8116d76c55ac1ea16e34befe7686291d56a40c2bafc8a
Type fulltextMimetype application/pdf

Search in DiVA

By author/editor
Lennerstad, HåkanLundberg, Lars
By organisation
Department of Mathematics and Natural SciencesDepartment of Systems and Software Engineering
Mathematical Analysis

Search outside of DiVA

GoogleGoogle Scholar
Total: 142 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 65 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf