Discrete Mathematics & Theoretical Computer Science, Vol 11, No 1 (2009)

Font Size:  Small  Medium  Large

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

Valérie Berthé, Laurent Imbert


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 an representation can be obtained using a greedy approach, assuming one can efficiently compute the largest $\{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 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.

Full Text: PDF PostScript