cp's OEIS Frontend

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

%I A347983 #18 Jul 27 2024 23:15:48
%S A347983 1,2,3,4,5,7,11,13,21,39,41,43,115,173,276,413,823,1389,1654
%N A347983 Smallest number requiring n 1's to build using +, -, *, and ^.
%C A347983 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 A347983 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 A347983 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 A347983 Least inverse (or records) of A091334.
%Y A347983 Cf. least inverses A003037, A005520, A255641 of other such "complexity" measures.
%K A347983 nonn,more
%O A347983 1,2
%A A347983 _Glen Whitney_, Sep 22 2021