Diophantine Approximation, Ostrowski Numeration and the Double-Base Number System - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Journal Articles Discrete Mathematics and Theoretical Computer Science Year : 2009

Diophantine Approximation, Ostrowski Numeration and the Double-Base Number System

Abstract

A partition of $x > 0$ of the form $x = \sum_i 2^{a_i}3^{b_i}$ with distinct parts is called a double-base expansion of $x$. Such a representation can be obtained using a greedy approach, assuming one can efficiently compute the largest \mbox{$\{2,3\}$-integer}, i.e., a number of the form $2^a3^b$, less than or equal to $x$. In order to solve this problem, we propose an algorithm based on continued fractions in the vein of the Ostrowski number system, we prove its correctness and we analyse its complexity. In a second part, we present some experimental results on the length of double-base expansions when only a few iterations of our algorithm are performed.
Fichier principal
Vignette du fichier
1011-4184-2-PB.pdf (200.05 Ko) Télécharger le fichier
Origin Explicit agreement for this submission
Loading...

Dates and versions

lirmm-00374066 , version 1 (03-06-2014)

Identifiers

Cite

Valerie Berthe, Laurent Imbert. Diophantine Approximation, Ostrowski Numeration and the Double-Base Number System. Discrete Mathematics and Theoretical Computer Science, 2009, Vol. 11 no. 1 (1), pp.153-172. ⟨10.46298/dmtcs.450⟩. ⟨lirmm-00374066⟩
191 View
2514 Download

Altmetric

Share

Gmail Mastodon Facebook X LinkedIn More