License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ISAAC.2022.29
URN: urn:nbn:de:0030-drops-173146
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/17314/
Amano, Kazuyuki
Integer Complexity and Mixed Binary-Ternary Representation
Abstract
The integer complexity of a natural number n, denoted by ‖n‖, is the smallest number of 1’s needed to express n using an arbitrary combination of addition and multiplication (and parentheses). For example, ‖6‖ = 5 since the expression 6 = (1+1)⋅ (1+1+1) contains five 1’s and there are no such expressions containing at most four 1’s. The investigation of this cute complexity measure was originated by Mahler and Popken in the 1950s. It is easy to see that ‖n‖/(log₃ n) ∈ [3, 3 log₂ 3] (∼ [3,4.755]) for every n, but the distribution of ‖n‖ is largely unknown.
In this work, we focus on the restricted expressions obtained by applying Horner’s schema to a mixed binary-ternary representation of a given number in which we can arrange base-two and base-three digits in an arbitrary order. Let f(n) denote the minimum number of 1’s needed to express n in this way. Apparently, f(n) ≥ ‖n‖ for every n. We extensively investigate on f(n) via the combination of computer experiments and theoretical analysis and obtain the following set of results: (i) Computer experiments supporting the hypothesis that f(n)/log₃ n < 3.483 on average and f(n)/log₃ n < 4.212 for all n, (ii) For almost all natural numbers n, 3.120 < f(n)/log₃ n < 3.587, and (iii) There are infinitely many n’s such that f(n)/log₃ n > 3.934. Several new bounds on the original integer complexity are also presented in the paper.
BibTeX - Entry
@InProceedings{amano:LIPIcs.ISAAC.2022.29,
author = {Amano, Kazuyuki},
title = {{Integer Complexity and Mixed Binary-Ternary Representation}},
booktitle = {33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
pages = {29:1--29:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-258-7},
ISSN = {1868-8969},
year = {2022},
volume = {248},
editor = {Bae, Sang Won and Park, Heejin},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/17314},
URN = {urn:nbn:de:0030-drops-173146},
doi = {10.4230/LIPIcs.ISAAC.2022.29},
annote = {Keywords: Integer complexity, Lower bounds, Upper bounds, Horner’s schema, Computer assisted proof}
}
