A347983 Smallest number requiring n 1's to build using +, -, *, and ^.

1, 2, 3, 4, 5, 7, 11, 13, 21, 39, 41, 43, 115, 173, 276, 413, 823, 1389, 1654

Offset: 1

Author

Glen Whitney, Sep 22 2021

Keywords

• nonn
• more

Comments

Until n = 10 the terms are equal to A003037(n) where subtraction is not allowed; that is the same value of n at which A255641 and A005520, which also differ only in allowing subtraction, diverge.

The values given are all of the exact ones available from the program posted with A091334, which ignores intermediate results over 2^65, but which nevertheless is provably exact for small values of n up to complexity 19. Running the same program with a larger complexity limit leads to the uncertain (but highly likely correct) values for a(20) through a(26): 3306, 3307, 8871, 22261, 31661, 69467, 155051. (These values were stable for different intermediate-result cutoffs from 2^33 through 2^65, supporting their likely correctness.)

Examples

			a(7) = 11 because 2=1+1, 3=1+1+1, 4=1+1+1+1, 5=1+1+1+1+1, 6=(1+1)(1+1+1), 7=(1+1)(1+1+1)+1, 8=(1+1)^(1+1+1), 9=(1+1+1)^(1+1), and 10=(1+1+1)^(1+1)+1, all requiring fewer than seven ones, whereas a minimal way of expressing 11 is (1+1+1)^(1+1)+1+1 with seven ones. (Subtraction does not actually play a necessary role in a minimal expression until 15=(1+1)^(1+1+1+1)-1, and does not affect the value of a(n) until n = 10 because 23=(1+1+1)(1+1)^(1+1+1)-1 would otherwise be the smallest number requiring ten ones.)
		

Crossrefs

Least inverse (or records) of A091334.

Cf. least inverses A003037, A005520, A255641 of other such "complexity" measures.