A319975 Smallest number of complexity n with respect to the operations {1, shift, multiply}.
1, 2, 3, 4, 5, 6, 7, 10, 11, 14, 19, 22, 23, 38, 43, 58, 59, 89, 107, 134, 167, 179, 263, 347, 383, 537, 713, 719, 1103, 1319, 1439, 2099, 2879, 3833, 4283, 5939, 6299, 9059, 12239, 15118, 19079, 23039, 26459, 44879, 49559, 66239, 78839, 98999, 137339
Offset: 1
Keywords
Examples
1 = 1 has complexity 1 2 = S1 has complexity 2 3 = SS1 has complexity 3 4 = SSS1 has complexity 4 5 = SSSS1 has complexity 5 6 = SSSSS1 has complexity 6 7 = SSSSSS1 has complexity 7 10 = S*SS1SS1 = shift(product of (3 and 3)) has complexity 8 (Note that 8 = *S1SSS1 has complexity 7) 11 = SS*SS1SS1 has complexity 9 14 = SS*SS1SSS1 has complexity 10
Links
- Michael S. Branicky, Table of n, a(n) for n = 1..67
- Akshunna Shaurya Dogra, Minimal Representations of Natural Numbers Under a Set of Operators, arXiv preprint 1801.01360 [math.HO], Jan 2018.
- Index to sequences related to the complexity of n.
Crossrefs
Programs
-
Python
def aupton(nn): alst, R, allR = [1], {1: {1}}, {1} # R[n] is set reachable using n ops for n in range(2, nn+1): R[n] = set(a+1 for a in R[n-1]) 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]) alst.append(min(R[n] - allR)) allR |= R[n] return alst print(aupton(49)) # Michael S. Branicky, Oct 06 2021
Comments