A347983 - OEIS

%I #18 Jul 27 2024 23:15:48

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

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

%C 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.

%C 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.)

%e 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.)

%Y Least inverse (or records) of A091334.

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

%K nonn,more

%O 1,2

%A _Glen Whitney_, Sep 22 2021