eng
episciences.org
Discrete Mathematics & Theoretical Computer Science
1365-8050
2009-03-01
Vol. 11 no. 1
Analysis of Algorithms
10.46298/dmtcs.450
450
journal article
Diophantine Approximation, Ostrowski Numeration and the Double-Base Number System
Valerie Berthe
Laurent Imbert
Analysis of Algorithms
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.
https://dmtcs.episciences.org/450/pdf
[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]