Ändra sökning
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
Generalizations of the floor and ceiling functions using the Stern-Brocot tree
Blekinge Tekniska Högskola, Sektionen för ingenjörsvetenskap, Avdelningen för matematik och naturvetenskap.
Blekinge Tekniska Högskola, Sektionen för teknik, Avdelningen för programvarusystem.
2006 (Engelska)Rapport (Refereegranskat)
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.

Ort, förlag, år, upplaga, sidor
2006.
Serie
Blekinge Institute of Technology Research report, ISSN 1103-1581 ; 2
Nyckelord [en]
floor function, ceiling function, mediant, relative primality, Stern-Brocot tree
Nationell ämneskategori
Matematisk analys
Identifikatorer
URN: urn:nbn:se:bth-00318Lokalt ID: oai:bth.se:forskinfo5703F14DE868B72DC1257141002EE53COAI: oai:DiVA.org:bth-00318DiVA, id: diva2:833712
Tillgänglig från: 2015-06-25 Skapad: 2006-03-30 Senast uppdaterad: 2025-09-30Bibliografiskt granskad

Open Access i DiVA

fulltext(523 kB)3018 nedladdningar
Filinformation
Filnamn FULLTEXT01.pdfFilstorlek 523 kBChecksumma SHA-512
2db6bca73a496365293fc5ef313558b16dd791d0e139232d0f2f715b9557503fd591140b8b96449a50b8116d76c55ac1ea16e34befe7686291d56a40c2bafc8a
Typ fulltextMimetyp application/pdf

Person

Lennerstad, HåkanLundberg, Lars

Sök vidare i DiVA

Av författaren/redaktören
Lennerstad, HåkanLundberg, Lars
Av organisationen
Avdelningen för matematik och naturvetenskapAvdelningen för programvarusystem
Matematisk analys

Sök vidare utanför DiVA

GoogleGoogle Scholar
Totalt: 3018 nedladdningar
Antalet nedladdningar är summan av nedladdningar för alla fulltexter. Det kan inkludera t.ex tidigare versioner som nu inte längre är tillgängliga.

urn-nbn

Altmetricpoäng

urn-nbn
Totalt: 615 träffar
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf