A091333 -id:A091333 - cp's OEIS frontend

A323727 Number of 1's required to build n using +, -, *, ^ and tetration.

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

Offset: 1

Robin Powell, Jan 25 2019

nonn

			a(14) = 7 because 14 = (1+1)^^(1+1+1)-1-1. (Note that 14 is also the smallest index at which this sequence differs from A091334.)

Wikipedia, Tetration
Index to sequences related to the complexity of n

Cf. A091333, A091334, A025280.

A378758 Number of 1's required to build n using +, -, and ^.

Original entry on oeis.org

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

Offset: 1

Jake Bird, Dec 06 2024

nonn

All intermediate steps in building the number should be integers as well, for consistency with related sequences.

A348262(n) >= a(n) >= A091334(n) for all n, as the available operators in A348262 are a subset of the available operators here, and the available operators here are a subset of the available operators in A091334.

			a(22) = 10 because 22 = (1+1+1+1+1)^(1+1)-(1+1+1), which has 10 occurrences of the symbol "1", and there is no way of making 22 with fewer using these rules.
Note that A348262(22) = 12 because 22 = (1+1)^(1+1)^(1+1)+(1+1)^(1+1)+1+1; subtraction allows for two fewer occurrences of the symbol "1" to be used here. Similarly, A091334(22) = 9 because 22 = ((1+1+1)^(1+1)+1+1)*(1+1); multiplication allows for one fewer occurrence of the symbol "1" to be used there. 22 is the least n such that A348262(n) > a(n) > A091334(n).

Jake Bird, Table of n, a(n) for n = 1..300

Cf. A000027 {1,+}, {1,+,-}
Cf. A005245 {1,+,*}
Cf. A348262 {1,+,^}
Cf. A091333 {1,+,-,*}
Cf. A025280 {1,+,*,^}
Cf. A378759 {1,+,/,^}
Cf. A091334 {1,+,-,*,^}
Cf. A348089 {1,+,-,*,/,^}

A378759 Number of 1's required to build n using +, /, and ^.

Original entry on oeis.org

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

Offset: 1

Jake Bird, Dec 06 2024

nonn

All intermediate steps in building the number should also be integers.

A348262(n) >= a(n) >= A348089(n) for all n, as the available operators in A348262 are a subset of the available operators here, and the available operators here are a subset of the available operators in A348089.

			a(14) = 9 because 14 = ((1+1+1)^(1+1+1)+1)/(1+1), which has 9 occurrences of the symbol "1", and there is no way of making 14 with fewer using these rules.
Note that A348262(14) = 10 because 14 = (1+1+1)^(1+1)+(1+1)^(1+1)+1; division allows for one fewer occurrence of the symbol "1" to be used here. Similarly, A348089(14) = 8, because 14 = (1+1)^(1+1)^(1+1)-(1+1); subtraction allows for one fewer occurrence of the symbol "1" to be used there. 14 is the least n such that A348262(n) > a(n) > A348089(n).

Jake Bird, Table of n, a(n) for n = 1..119

Cf. A000027 {1,+}, {1,+,-}
Cf. A005245 {1,+,*}
Cf. A348262 {1,+,^}
Cf. A091333 {1,+,-,*}
Cf. A378758 {1,+,-,^}
Cf. A025280 {1,+,*,^}
Cf. A091334 {1,+,-,*,^}
Cf. A348089 {1,+,-,*,/,^}

A348083 Number of positive numbers that can be built with n ones using +, -, and *, and require at least n ones.

Original entry on oeis.org

1, 1, 1, 1, 2, 3, 2, 6, 6, 8, 13, 18, 21, 35, 45, 61, 90, 121, 162, 241, 323, 450, 638, 865, 1233, 1698, 2349, 3315, 4592, 6382, 8970, 12421, 17351, 24320, 33714, 47218, 65978, 91784, 128177, 179807, 249689, 349549, 489341, 681468, 953769, 1334490, 1860641, 2606043, 3643618, 5086481, 7124229, 9960420

Offset: 1

Glen Whitney, Sep 27 2021

nonn

a(n+1)/a(n) appears from the values through n=63 to be oscillating in a narrowing range around 7/5.

			For n=5, there are two numbers whose minimal expression using 1,+,-, and * uses five ones: 5 = 1+1+1+1+1 and 6 = (1+1)*(1+1+1), so a(5) = 2.
For n=10, there are eight numbers whose minimal expression uses ten ones: 22 = 3(2*3+1)+1, 23 = 2*2*2*3-1, 25 = 5*5, 26 = 3*3*3-1, 28 = 3*3*3+1, 30 = 2*3*5, 32 = 2*2*2*2*2, and 36 = 2*2*3*3. We use numbers k=1..5 in these expressions because each takes k ones to express. Note that n=10 is also the least n for which a(n) differs from A005421(n), which counts the solutions to A005245(k) = n.

Glen Whitney, Table of n, a(n) for n = 1..64 (This file produced with the same C code that generated A348069, simply with division eliminated from the loop over operators.)

Cf. A005421, A091333, A005245.

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 list(out)
def a(n): return len(f(n)) - len(f(n-1))
print([a(n) for n in range(1, 33)]) # Michael S. Branicky, Sep 27 2021

a(n) = |{k : A091333(k) = n}|.

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

A346742 Numbers that may be built from fewer ones using floor(j/k) in addition to +, -, and *.

Original entry on oeis.org

1860043, 3198487, 4782847, 5580129, 6111571, 9300217, 9566302, 9595461, 9595462, 9654511, 10678027, 12725059, 12843157, 13551745, 14349271, 14614627, 16740391, 17094685, 18334713, 18334714, 19220449, 27900651, 28698178, 28701094, 29494975, 31620739, 32034081, 33484063, 34100797, 35872267, 37998031

Offset: 1

Glen Whitney, Sep 28 2021

nonn

Consider an integer complexity measure c(n) which is the number of ones required to build n using +, -, *, and "floor division" which for convenience will be written in this entry (after Python notation) j//k = floor(j/k). In other words, c(n) is defined identically to A091333(n) except that this floor division is also allowed, and identically to the complexity b(n) described in A348069 except that division is extended to all pairs of natural numbers by taking the floor of the quotient. Clearly for all n, c(n) <= b(n) <= A091333(n). This sequence lists the integers k for which c(k) < A091333(k).
Because of the inequality c(n) <= b(n) <= A091333(n), every entry in A348069 will eventually appear in this sequence. For example, the first term of A348069 is 50221174 = (7*3^15)//2, so we have c(50221174) = 53, b(50221174) = 54, and A091333(50221174) = 55.
The extended domain of division means that terms of this sequence are much more frequent than A348069, but it's still quite rare for division to provide more compact expressions for natural numbers (except in the presence of exponentiation, see A348089).

			The smallest n for which c(n) as defined in the comments is strictly less than A091333(n) is 1860043, because 1860043 = (7*3^12)//2 which requires c(7) + 12*c(3) + c(2) = 6 + 12*3 + 2 = 44 ones to express with these operations, whereas A091333(1860043) = A005245(1860043) = 45 by virtue of the minimal expression 1860043 = 2(2^2*5*7(3^4(3^4+1)+1)+1)+1 requiring 2+2*2+5+6+3*4+3*4+1+1+1+1 = 45 ones. Hence, the first term in this sequence is 1860043.
The next three terms with their respective minimal expressions:
3198487 = (3^9(2^2*3^4+1))//2 [46 ones] = 2*3(3^2(2^2*3*5+1)(2^2*3^5-1)+2)+1 [47 ones] = 2*3(2(7(2^2*3+1)(2^2*3(3^5+1)+1)+1)+1)+1 [48 ones]. Thus n=319487 is the least n for which c(n) < A091333(n) < A005245(n).
4782847 = (3^5(2*3^9-1))//2 [47 ones] = 2*3(2*5(3^2(2^2*3^3(3^4+1)+1)+1)+1)+1 [48 ones]
5580129 = 3*1860043 = 3((7*3^12)//2) [47 ones] = 2^3(3*5*7(3^4(3^4+1)+1)+1)+1 [48 ones]. Note this example critically takes advantage of the fact that * and // are not associative.

Cf. A253177 and A348069.

Cf. A091333 and A005245 (other integer complexity measures).

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

Original entry on oeis.org

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

Offset: 1

Pontus von Brömssen, Jul 27 2023

nonn

Unary minus is not allowed, otherwise we would have a(n) = A091333(n).

			a(5) = 6 because -5 = 1 - (1+1) * (1+1+1).
a(10) = 8 because -10 = 2 * (-5) = (1+1) * (1 - (1+1) * (1+1+1)).

Index to sequences related to the complexity of n.

Cf. A091333.

A091333(n) <= a(n) <= 1 + A091333(n+1) <= 2 + A091333(n). Equality holds in the first inequality for n = 11, 17, 22, 23, 26, 29, ... .

cp's OEIS Frontend

A323727 Number of 1's required to build n using +, -, *, ^ and tetration.

Views

Author

Keywords

Examples

Links

Crossrefs

A378758 Number of 1's required to build n using +, -, and ^.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A378759 Number of 1's required to build n using +, /, and ^.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A348083 Number of positive numbers that can be built with n ones using +, -, and *, and require at least n ones.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Python

Formula

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

A346742 Numbers that may be built from fewer ones using floor(j/k) in addition to +, -, and *.

Views

Author

Keywords

Comments

Examples

Crossrefs

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula