Integer Complexity: Experimental and Analytical Results II

Abstract. We consider representing of natural numbers by expressions using 1’s, addition, multiplication and parentheses. ‖n ‖ denotes the min-imum number of 1’s in the expressions representing n. The logarith-mic complexity ‖n‖log is defined as ‖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 representations of the numbers 2n. We consider also representing of natural numbers by expressions that include subtraction, and the so-called P-algorithms- a family of “deter-ministic ” algorithms for building representations of numbers