A091333 Number of 1's required to build n using +, -, *, and parentheses.

1, 2, 3, 4, 5, 5, 6, 6, 6, 7, 8, 7, 8, 8, 8, 8, 9, 8, 9, 9, 9, 10, 10, 9, 10, 10, 9, 10, 11, 10, 11, 10, 11, 11, 11, 10, 11, 11, 11, 11, 12, 11, 12, 12, 11, 12, 12, 11, 12, 12, 12, 12, 12, 11, 12, 12, 12, 13, 13, 12, 13, 13, 12, 12, 13, 13, 14, 13, 13, 13, 13, 12, 13, 13, 13, 13, 14

Offset: 1

Author

Jens Voß, Dec 30 2003

Keywords

• nonn

Comments

Consider an alternate complexity measure b(n) which gives the minimum number of 1's necessary to build n using +, -, *, and / (where this additional operation is strict integer division, defined only for n/d where d|n). It turns out that b(n) coincides with a(n) for all n up to 50221174, see A348069. - Glen Whitney, Sep 23 2021

In respect of the previous comment: when creating A362471, where repunits are allowed, we found a difference if we allowed n/d with noninteger (intermediate) results. So, see also A362626. - Peter Munn, Apr 29 2023

Examples

			A091333(23) = 10 because 23 = (1+1+1+1) * (1+1+1) * (1+1) - 1. (Note that 23 is also the smallest index at which A091333 differs from A005245.)
		

Links

• Janis Iraids, Table of n, a(n) for n = 1..10000
• Juris Cernenoks, Janis Iraids, Martins Opmanis, Rihards Opmanis and Karlis Podnieks, Integer Complexity: Experimental and Analytical Results II, arXiv:1409.0446 [math.NT], 2014.
• Janis Iraids, A C program to compute the sequence
• J. Iraids, K. Balodis, J. Cernenoks, M. Opmanis, R. Opmanis and K. Podnieks, Integer Complexity: Experimental and Analytical Results. arXiv preprint arXiv:1203.6462 [math.NT], 2012. - From _N. J. A. Sloane_, Sep 22 2012
• Index to sequences related to the complexity of n

Crossrefs

Cf. A005245 (variant using + and *), A025280 (using +, *, and ^), A091334 (using +, -, *, and ^), A348089 (using +, -, *, /, and ^), A348262 (using + and ^).

Cf. A348069, A362471, A362626.

Programs

Python

from functools import cache
@cache
def f(m):
    if m == 0: return set()
    if m == 1: return {1}
    out = set()
    for j in range(1, m//2+1):
        for x in f(j):
            for y in f(m-j):
                out.update([x + y, x * y])
                if x != y: out.add(abs(x-y))
    return out
def aupton(terms):
    tocover, alst, n = set(range(1, terms+1)), [0 for i in range(terms)], 1
    while len(tocover) > 0:
        for k in f(n) - f(n-1):
            if k <= terms:
                alst[k-1] = n
                tocover.discard(k)
        n += 1
    return alst
print(aupton(77)) # Michael S. Branicky, Sep 28 2021