cp's OEIS Frontend

A319975 Smallest number of complexity n with respect to the operations {1, shift, multiply}.

%I A319975 #21 Oct 06 2021 12:16:50
%S A319975 1,2,3,4,5,6,7,10,11,14,19,22,23,38,43,58,59,89,107,134,167,179,263,
%T A319975 347,383,537,713,719,1103,1319,1439,2099,2879,3833,4283,5939,6299,
%U A319975 9059,12239,15118,19079,23039,26459,44879,49559,66239,78839,98999,137339
%N A319975 Smallest number of complexity n with respect to the operations {1, shift, multiply}.
%C A319975 The shift operation here is also sometimes called successor, see A263283.
%C A319975 Note this complexity measure counts both operands (the ones) and operators (the shifts and multiplications), whereas most of the complexity measures in the crossrefs count only operands. However, in the presence of successor it would not make sense to count only operands, since any number can be expressed with a single occurrence of 1. - _Glen Whitney_, Oct 06 2021
%H A319975 Michael S. Branicky, <a href="/A319975/b319975.txt">Table of n, a(n) for n = 1..67</a>
%H A319975 Akshunna Shaurya Dogra, <a href="https://arxiv.org/abs/1801.01360">Minimal Representations of Natural Numbers Under a Set of Operators</a>, arXiv preprint 1801.01360 [math.HO], Jan 2018.
%H A319975 <a href="/index/Com#complexity">Index to sequences related to the complexity of n.</a>
%e A319975 1 = 1 has complexity 1
%e A319975 2 = S1 has complexity 2
%e A319975 3 = SS1 has complexity 3
%e A319975 4 = SSS1 has complexity 4
%e A319975 5 = SSSS1 has complexity 5
%e A319975 6 = SSSSS1 has complexity 6
%e A319975 7 = SSSSSS1 has complexity 7
%e A319975 10 = S*SS1SS1 = shift(product of (3 and 3)) has complexity 8
%e A319975 (Note that 8 = *S1SSS1 has complexity 7)
%e A319975 11 = SS*SS1SS1 has complexity 9
%e A319975 14 = SS*SS1SSS1 has complexity 10
%o A319975 (Python)
%o A319975 def aupton(nn):
%o A319975     alst, R, allR = [1], {1: {1}}, {1} # R[n] is set reachable using n ops
%o A319975     for n in range(2, nn+1):
%o A319975         R[n]  = set(a+1 for a in R[n-1])
%o A319975         R[n] |= set(a*b for i in range(1, (n+1)//2) for a in R[i] for b in R[n-1-i])
%o A319975         alst.append(min(R[n] - allR))
%o A319975         allR |= R[n]
%o A319975     return alst
%o A319975 print(aupton(49)) # _Michael S. Branicky_, Oct 06 2021
%Y A319975 Smallest number of complexity n (other definitions): A003037, A005520, A244743, A259466, and A265360.
%Y A319975 Other definitions of the complexity of n: A005208, A005245, A025280, and A099053.
%K A319975 nonn
%O A319975 1,2
%A A319975 _N. J. A. Sloane_, Oct 11 2018