Service interruption on Monday 11 July from 12:30 to 13:00: all the sites of the CCSD (HAL, EpiSciences, SciencesConf, AureHAL) will be inaccessible (network hardware connection).
Skip to Main content Skip to Navigation
Journal articles

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

Valerie Berthe 1 Laurent Imbert 2, 1, * 
* Corresponding author
1 ARITH - Arithmétique informatique
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
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.
Document type :
Journal articles
Complete list of metadata

Cited literature [27 references]  Display  Hide  Download
Contributor : Laurent Imbert Connect in order to contact the contributor
Submitted on : Tuesday, June 3, 2014 - 3:25:06 PM
Last modification on : Thursday, May 12, 2022 - 8:42:10 AM
Long-term archiving on: : Wednesday, September 3, 2014 - 10:35:45 AM


Explicit agreement for this submission




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



Record views


Files downloads