Valerie Berthe ; Laurent Imbert - Diophantine Approximation, Ostrowski Numeration and the Double-Base Number System

dmtcs:450 - Discrete Mathematics & Theoretical Computer Science, March 1, 2009, Vol. 11 no. 1 -
Diophantine Approximation, Ostrowski Numeration and the Double-Base Number System

Authors: Valerie Berthe 1; Laurent Imbert ORCID-iD2,1

  • 1 Arithmétique informatique
  • 2 Pacific Institute for the Mathematical Sciences

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.

Volume: Vol. 11 no. 1
Section: Analysis of Algorithms
Published on: March 1, 2009
Imported on: March 26, 2015
Keywords: [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]

Linked publications - datasets - softwares

Source : ScholeXplorer IsRelatedTo ARXIV 1205.4833
Source : ScholeXplorer IsRelatedTo DOI 10.1007/s00605-012-0443-4
Source : ScholeXplorer IsRelatedTo DOI 10.48550/arxiv.1205.4833
Source : ScholeXplorer IsRelatedTo PMC PMC4370826
Source : ScholeXplorer IsRelatedTo PMID 25814773
  • PMC4370826
  • 25814773
  • 25814773
  • PMC4370826
  • 10.1007/s00605-012-0443-4
  • 10.1007/s00605-012-0443-4
  • 10.48550/arxiv.1205.4833
  • 1205.4833
On linear combinations of units with bounded coefficients and double-base digit expansions.

Consultation statistics

This page has been seen 722 times.
This article's PDF has been downloaded 609 times.