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