A362471 -id:A362471 - cp's OEIS frontend

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

Jens Voß, Dec 30 2003

nonn

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

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

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

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

Cf. A348069, A362471, A362626.

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

A362626 a(n) is the smallest number of 1's used in expressing n as a calculation containing only decimal repunits and operators +, -, * and /, where fractions are allowed as intermediate results.

Original entry on oeis.org

1, 2, 3, 4, 5, 5, 6, 5, 4, 3, 2, 3, 4, 5, 6, 7, 7, 6, 6, 5, 5, 4, 5, 5, 6, 6, 7, 7, 7, 6, 7, 6, 5, 6, 7, 6, 6, 7, 7, 7, 8, 7, 7, 6, 7, 7, 8, 7, 8, 7, 8, 8, 8, 7, 6, 6, 7, 8, 8, 7, 7, 8, 8, 8, 8, 7, 8, 8, 8, 9, 9, 8, 8, 7, 8, 9, 8, 8, 9, 8, 8, 9, 10, 9, 9, 9, 8, 7, 7

Offset: 1

Yifan Xie, Haochen Mi and Michael S. Branicky, Apr 28 2023

a(n+1) <= a(n) + 1.

a(n) <= a(i) + a(j), for all i O j = n, for O = +, -, *, /.

			a(74) = 7, since 74 = 111/(1+(1/(1+1))).
a(111) = 3.

Michael S. Branicky, Table of n, a(n) for n = 1..10000

Cf. A002275, A005245, A362471.

A363968 Least number of 1's needed to represent n using only additions +, subtractions -, multiplications *, divisions /, concatenations # and parentheses ().

Original entry on oeis.org

2, 1, 2, 3, 4, 5, 5, 6, 5, 4, 3, 2, 3, 4, 5, 6, 6, 7, 6, 5, 4, 3, 4, 5, 5, 6, 6, 7, 7, 6, 5, 4, 5, 5, 6, 7, 6, 6, 7, 7, 6, 5, 5, 6, 6, 7, 7, 8, 7, 8, 7, 6, 7, 7, 7, 6, 6, 7, 8, 8, 7, 6, 6, 6, 7, 8, 7, 8, 8, 8, 8, 7, 8, 8, 8, 9, 9, 8, 8, 8, 7, 6, 7, 8, 7, 8, 8, 8, 7, 7, 6, 5, 6, 7, 8, 9, 8, 8, 7, 6, 5

Offset: 0

Bernard Schott, Jun 30 2023

Fractions are not allowed as intermediate results.
The unique difference with A362471 is that concatenation is here allowed; in fact, in A362471, concatenation is only allowed for getting repunits as 111 = 1#1#1 but not for getting other integers.
Also, for example, the concatenation of 5 and -3 is not possible, so it should not be interpreted as 5-3 = 2.
The first differences with A362471 in the data appear at n = 16, 19, 20, 21, 29, ... see Example section.

			For n = 16, 16 = 1 # ((1+1)*(1+1+1)), so a(16) = 6 while A362471(16) = 7.
For n = 19, 19 = 1 # (11-1-1), so a(19) = 5 while A362471(19) = 6.
For n = 20, 20 = (1+1) # (1-1), so a(20) = 4 while A362471(20) = 5.
For n = 31, 31 = (1+1+1) # (1), so a(31) = 4 while A362471(31) = 7.
For n = 43, 43 = (1+1)*((1+1) # (1)) + 1, so a(43) = 6 while A362471(43) = 7.

Michael S. Branicky, Table of n, a(n) for n = 0..10000.
Index to sequences related to the complexity of n.

Cf. A002275, A005245, A091333, A133344, A362471, A362626.

|a(n+1) - a(n)| <= 1; improved by Pontus von Brömssen, Jun 30 2023
a(n) <= A362471(n).
a(n) <= Sum_{k=1..m} a(dk), where d1d2..dm are the decimal digits of n. - Michael S. Branicky, Jun 30 2023

a(72) and beyond from Michael S. Branicky, Jun 30 2023

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Python

A362626 a(n) is the smallest number of 1's used in expressing n as a calculation containing only decimal repunits and operators +, -, * and /, where fractions are allowed as intermediate results.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A363968 Least number of 1's needed to represent n using only additions +, subtractions -, multiplications *, divisions /, concatenations # and parentheses ().

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions