Abstract
We consider representing natural numbers by expressions using only 1’s, addition, multiplication and parentheses. Let \( \left\| n \right\| \) denote the minimum number of 1’s in the expressions representing \(n\). The logarithmic complexity \( \left\| n \right\| _{\log } \) is defined to be \({ \left\| n \right\| }/{\log _3 n}\). The values of \( \left\| n \right\| _{\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 \(2^n\).
We also consider representing natural numbers by expressions that include subtraction.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Allouche, J.P., Shallit, J.: Automatic Sequences: Theory, Applications, Generalizations. Cambridge University Press, Cambridge (2003)
Altman, H.: Integer complexity and well-ordering. ArXiv e-prints, October 2013. http://arxiv.org/abs/1310.2894
Altman, H.: Integer complexity, addition chains, and well-ordering. Ph.D. thesis, University of Michigan (2014). http://www-personal.umich.edu/~haltman/thesis-FIXED.pdf
Altman, H., Zelinsky, J.: Numbers with integer complexity close to the lower bound. INTEGERS 12(6), 1093–1125 (2012)
Aragón Artacho, F.J., Bailey, D.H., Borwein, J.M., Borwein, P.B.: Walking on real numbers. Math. Intell. 35(1), 42–60 (2013). doi:10.1007/s00283-012-9340-x
Arias de Reyna, J., van de Lune, J.: Algorithms for determining integer complexity. ArXiv e-prints, April 2014. http://arxiv.org/abs/1404.2183
Arias de Reyna, J., van de Lune, J.: How many \(1\)’s are needed? revisited. ArXiv e-prints, April 2014. http://arxiv.org/abs/1404.1850
Belshaw, A., Borwein, P.: Champernowne’s number, strong normality, and the X chromosome. In: Bailey, D.H., Bauschke, H.H., Borwein, P., Garvan, F., Théra, M., Vanderwerff, J.D., Wolkowicz, H. (eds.) Computational and Analytical Mathematics, Springer Proceedings in Mathematics & Statistics, vol. 50, pp. 29–44. Springer, New York (2013). doi:10.1007/978-1-4614-7621-4_3
Gnang, E.K., Radziwill, M., Sanna, C.: Counting arithmetic formulas. ArXiv e-prints (2014). http://arxiv.org/abs/1406.1704
Guy, R.K.: Some suspiciously simple sequences. Am. Math. Mon. 93(3), 186–190 (1986)
Iraids, J.: The On-Line Encyclopedia of Integer Sequences, Smallest number requiring \(n\) 1’s to build using \(+\), \(\cdot \) and \(-\). http://oeis.org/A255641
Iraids, J.: Online calculator of integer complexity. http://expmath.lumii.lv/wiki/index.php/Special:Complexity. Accessed on 28 February 2015
Iraids, J., Balodis, K., Čerņenoks, J., Opmanis, M., Opmanis, R., Podnieks, K.: Integer complexity: Experimental and analytical results. Scientific Papers University of Latvia, Computer Science and Information Technologies 787, 153–179 (2012), arXiv preprint: http://arxiv.org/abs/1203.6462
Rawsthorne, D.A.: How many 1’s are needed? Fibonacci Q. 27(1), 14–17 (1989). http://www.fq.math.ca/Scanned/27-1/rawsthorne.pdf
Sloane, N.J.A.: The On-Line Encyclopedia of Integer Sequences, Complexity of \(n\): number of 1’s required to build \(n\) using \(+\) and \(\cdot \). http://oeis.org/A005245
Steinerberger, S.: A short note on integer complexity. Contributions to Discrete Mathematics 9(1) (2014). http://cdm.ucalgary.ca/cdm/index.php/cdm/article/view/361
Stewart, C.: On the representation of an integer in two different bases. Journal für die reine und angewandte Mathematik 319, 63–72 (1980). http://eudml.org/doc/152278
Vatter, V.: Maximal independent sets and separating covers. Am. Math. Mon. 118(5), 418–423 (2011). http://www.jstor.org/stable/pdfplus/10.4169/amer.math.monthly.118.05.418.pdf
Voß, J.: The On-Line Encyclopedia of Integer Sequences, Number of 1’s required to build \(n\) using \(+\), \(-\), \(\cdot \) and parentheses. http://oeis.org/A091333
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this paper
Cite this paper
Čerņenoks, J., Iraids, J., Opmanis, M., Opmanis, R., Podnieks, K. (2015). Integer Complexity: Experimental and Analytical Results II. In: Shallit, J., Okhotin, A. (eds) Descriptional Complexity of Formal Systems. DCFS 2015. Lecture Notes in Computer Science(), vol 9118. Springer, Cham. https://doi.org/10.1007/978-3-319-19225-3_5
Download citation
DOI: https://doi.org/10.1007/978-3-319-19225-3_5
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-19224-6
Online ISBN: 978-3-319-19225-3
eBook Packages: Computer ScienceComputer Science (R0)