OFFSET
1,2
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
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
Glen Whitney, Python3.8 program computing up to a(3305)
EXAMPLE
CROSSREFS
KEYWORD
nonn,changed
AUTHOR
Jens Voß, Dec 30 2003
STATUS
approved