Endre søk
RefereraExporteraLink to record
Permanent link

Direct link
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annet format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annet 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 (engelsk)Rapport (Fagfellevurdert)
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.

sted, utgiver, år, opplag, sider
2006.
Serie
Blekinge Institute of Technology Research report, ISSN 1103-1581 ; 2
Emneord [en]
floor function, ceiling function, mediant, relative primality, Stern-Brocot tree
HSV kategori
Identifikatorer
URN: urn:nbn:se:bth-00318Lokal ID: oai:bth.se:forskinfo5703F14DE868B72DC1257141002EE53COAI: oai:DiVA.org:bth-00318DiVA, id: diva2:833712
Tilgjengelig fra: 2015-06-25 Laget: 2006-03-30 Sist oppdatert: 2025-09-30bibliografisk kontrollert

Open Access i DiVA

fulltekst(523 kB)3018 nedlastinger
Filinformasjon
Fil FULLTEXT01.pdfFilstørrelse 523 kBChecksum SHA-512
2db6bca73a496365293fc5ef313558b16dd791d0e139232d0f2f715b9557503fd591140b8b96449a50b8116d76c55ac1ea16e34befe7686291d56a40c2bafc8a
Type fulltextMimetype application/pdf

Person

Lennerstad, HåkanLundberg, Lars

Søk i DiVA

Av forfatter/redaktør
Lennerstad, HåkanLundberg, Lars
Av organisasjonen

Søk utenfor DiVA

GoogleGoogle Scholar
Totalt: 3018 nedlastinger
Antall nedlastinger er summen av alle nedlastinger av alle fulltekster. Det kan for eksempel være tidligere versjoner som er ikke lenger tilgjengelige

urn-nbn

Altmetric

urn-nbn
Totalt: 615 treff
RefereraExporteraLink to record
Permanent link

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