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,2

Comments

The shift operation here is also sometimes called successor, see A263283.

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

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.

Example

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

Prog

(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

Crossrefs

Smallest number of complexity n (other definitions): A003037, A005520, A244743, A259466, and A265360.

Other definitions of the complexity of n: A005208, A005245, A025280, and A099053.

Sequence in context: A050725 A080571 A165805 * A307625 A165722 A082400

Adjacent sequences: A319972 A319973 A319974 * A319976 A319977 A319978

Keyword

nonn

Author

N. J. A. Sloane, Oct 11 2018

Status

approved