IEICE TRANSACTIONS on Fundamentals
Two Lower Bounds for Shortest Double-Base Number System
Summary :
In this letter, we derive two lower bounds for the number of terms in a double-base number system (DBNS), when the digit set is {1}. For a positive integer n, we show that the number of terms obtained from the greedy algorithm proposed by Dimitrov, Imbert, and Mishra [1] is $Thetaleft( rac{log n}{log log n} ight)$. Also, we show that the number of terms in the shortest double-base chain is Θ(log n).
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E98-A No.6 pp.1310-1312
- Publication Date
- 2015/06/01
- Publicized
- Online ISSN
- 1745-1337
- DOI
- 10.1587/transfun.E98.A.1310
- Type of Manuscript
- LETTER
- Category
- Algorithms and Data Structures
Authors
Parinya CHALERMSOOK
Max-Planck-Institut für Informatik
Hiroshi IMAI
The University of Tokyo
Vorapong SUPPAKITPAISARN
National Institute of Informatics,JST, ERATO Kawarabayashi Large Graph Project
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Parinya CHALERMSOOK, Hiroshi IMAI, Vorapong SUPPAKITPAISARN, "Two Lower Bounds for Shortest Double-Base Number System" in IEICE TRANSACTIONS on Fundamentals,
vol. E98-A, no. 6, pp. 1310-1312, June 2015, doi: 10.1587/transfun.E98.A.1310.
Abstract: In this letter, we derive two lower bounds for the number of terms in a double-base number system (DBNS), when the digit set is {1}. For a positive integer n, we show that the number of terms obtained from the greedy algorithm proposed by Dimitrov, Imbert, and Mishra [1] is $Thetaleft( rac{log n}{log log n}
ight)$. Also, we show that the number of terms in the shortest double-base chain is Θ(log n).
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E98.A.1310/_p
Copy
@ARTICLE{e98-a_6_1310,
author={Parinya CHALERMSOOK, Hiroshi IMAI, Vorapong SUPPAKITPAISARN, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Two Lower Bounds for Shortest Double-Base Number System},
year={2015},
volume={E98-A},
number={6},
pages={1310-1312},
abstract={In this letter, we derive two lower bounds for the number of terms in a double-base number system (DBNS), when the digit set is {1}. For a positive integer n, we show that the number of terms obtained from the greedy algorithm proposed by Dimitrov, Imbert, and Mishra [1] is $Thetaleft( rac{log n}{log log n}
ight)$. Also, we show that the number of terms in the shortest double-base chain is Θ(log n).},
keywords={},
doi={10.1587/transfun.E98.A.1310},
ISSN={1745-1337},
month={June},}
Copy
TY - JOUR
TI - Two Lower Bounds for Shortest Double-Base Number System
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1310
EP - 1312
AU - Parinya CHALERMSOOK
AU - Hiroshi IMAI
AU - Vorapong SUPPAKITPAISARN
PY - 2015
DO - 10.1587/transfun.E98.A.1310
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E98-A
IS - 6
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - June 2015
AB - In this letter, we derive two lower bounds for the number of terms in a double-base number system (DBNS), when the digit set is {1}. For a positive integer n, we show that the number of terms obtained from the greedy algorithm proposed by Dimitrov, Imbert, and Mishra [1] is $Thetaleft( rac{log n}{log log n}
ight)$. Also, we show that the number of terms in the shortest double-base chain is Θ(log n).
ER -
English
