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

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

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

Example

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.)

Prog

(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

Crossrefs

Cf. A005245, A025280, A091334, A348069, A362471, A362626.

Sequence in context: A200311 A007600 A195872 * A293771 A005245 A061373

Adjacent sequences: A091330 A091331 A091332 * A091334 A091335 A091336

Keyword

nonn

Author

Jens Voß, Dec 30 2003

Status

approved