A091334 Number of 1's required to build n using +, -, *, ^, and parentheses.

1, 2, 3, 4, 5, 5, 6, 5, 5, 6, 7, 7, 8, 8, 7, 6, 7, 7, 8, 8, 9, 9, 9, 8, 7, 7, 6, 7, 8, 9, 8, 7, 8, 9, 8, 7, 8, 9, 10, 10, 11, 11, 12, 11, 10, 11, 10, 9, 8, 9, 10, 9, 9, 8, 9, 9, 10, 10, 11, 11, 10, 9, 8, 7, 8, 9, 10, 11, 11, 10, 10, 9, 10, 10, 10, 11, 11, 10, 9, 8, 7, 8, 9, 10, 11, 12, 11, 12, 12

Offset: 1

Author

Jens Voß, Dec 30 2003

Keywords

• nonn

Comments

One strategy for computing integer complexities like a(n) is to proceed in rounds, successively determining all n for which a(n) = 2, 3, 4, 5, and so on. In each round one takes all operations of pairs of numbers whose already known lesser complexities sum to the current value. The difficulty with this particular a(n) is that exponentiation quickly produces very large values, which conceivably could be near each other and yield a value of a(n) for small n by taking their difference in a later round. However, one can safely compute small values up to 19 by ignoring intermediate results larger than 2^65: this doesn't ignore anything except 2^81, 2^256, and 2^512 in the ninth round, and those values will not become involved in differences that could affect arguments n less than 2^65 until at least round 19, so all small values up to 19 produced in this way will be correct. Doing so gives values for all n from a(1)=1 up to a(3305)=19. It is possible based on the above that a(3306) might be 19, if some large result from round 10 differs from one of the three ignored values in round 9 by exactly 3306. That just about surely doesn't happen, but more careful reasoning would be needed to prove the correct value a(3306) = 20. - Glen Whitney, Sep 22 2021

Examples

			A091334(15) = 7 because 15 = (1+1+1+1)^(1+1) - 1. (Note that 15 is also the smallest index at which A091334 differs from A025280.)
		

Links

• Glen Whitney, Table of n, a(n) for n = 1..3305
• J. Iraids, K. Balodis, J. Cernenoks, M. Opmanis, R. Opmanis and K. Podnieks, Integer Complexity: Experimental and Analytical Results. arXiv preprint arXiv:1203.6462, 2012. - From _N. J. A. Sloane_, Sep 22 2012
• Index to sequences related to the complexity of n
• Glen Whitney, Python3.8 program computing up to a(3305)

Crossrefs

Cf. A005245 (variant using + and *), A025280 (using +, *, and ^), A091333 (using +, -, and *), A348089 (using +, -, *, /, and ^), A348262 (using + and ^).