@inproceedings{eb0c27caeb8b4cc082eb0d005862bf28,
title = "Integer complexity: Experimental and analytical results II",
abstract = "We consider representing natural numbers by expressions using only 1{\textquoteright}s, addition, multiplication and parentheses. Let ||n|| denote the minimum number of 1{\textquoteright}s in the expressions representing n. The logarithmic complexity ||n||log is defined to be ||n||/log3 n. The values of ||n||log are located in the segment [3, 4.755], but almost nothing is known with certainty about the structure of this “spectrum” (are the values dense somewhere in the segment?, etc.).We establish a connection between this problem and another difficult problem: the seemingly “almost random” behaviour of digits in the base-3 representation of the numbers 2n. We also consider representing natural numbers by expressions that include subtraction.",
keywords = "Integer complexity, Logarithmic complexity, Powers of two, Spectrum, Ternary representations",
author = "Juris {\v C}erņenoks and Jānis Iraids and Mārtiņ{\v s} Opmanis and Rihards Opmanis and Kārlis Podnieks",
note = "Publisher Copyright: {\textcopyright} Springer International Publishing Switzerland 2015.; 17th International Workshop on Descriptional Complexity of Formal Systems, DCFS 2015 ; Conference date: 25-06-2015 Through 27-06-2015",
year = "2015",
doi = "10.1007/978-3-319-19225-3\_5",
language = "English",
isbn = "9783319192246",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "58--69",
editor = "Alexander Okhotin and Jeffrey Shallit",
booktitle = "Descriptional Complexity of Formal Systems - 17th International Workshop, DCFS 2015, Proceedings",
address = "Germany",
}