A025280 -id:A025280 - cp's OEIS frontend

A214836 Number of formula representations of n using addition, multiplication, exponentiation and the constant 1.

1, 1, 2, 7, 18, 58, 180, 613, 2076, 7270, 25752, 92918, 338432, 1246092, 4624536, 17290646, 65047436, 246079536, 935484928, 3571960668, 13692523960, 52675401248, 203299385584, 786949008100, 3054440440486, 11884949139900, 46351113658232, 181153317512536

Offset: 1

Alois P. Heinz, Mar 07 2013

nonn

			a(1) = 1: 1.
a(2) = 1: 11+.
a(3) = 2: 111++, 11+1+.
a(4) = 7: 1111+++, 111+1++, 11+11++, 111++1+, 11+1+1+, 11+11+*, 11+11+^.
a(5) = 18: 11111++++, 1111+1+++, 111+11+++, 1111++1++, 111+1+1++, 111+11+*+, 111+11+^+, 11+111+++, 11+11+1++, 111++11++, 11+1+11++, 1111+++1+, 111+1++1+, 11+11++1+, 111++1+1+, 11+1+1+1+, 11+11+*1+, 11+11+^1+.
All formulas are given in postfix (reverse Polish) notation but other notations would give the same results.

Alois P. Heinz, Table of n, a(n) for n = 1..1000
Edinah K. Ghang and Doron Zeilberger, Zeroless Arithmetic: Representing Integers ONLY using ONE, arXiv:1303.0885 [math.CO], 2013.
Shalosh B. Ekhad, Everything About Formulas Representing Integers Using Additions, Multiplication and Exponentiation for integers from 1 to 8000
Wikipedia, Postfix notation
Index to sequences related to the complexity of n

Cf. A025280, A214833, A214843, A217250, A217253.

with(numtheory):
a:= proc(n) option remember; `if`(n=1, 1,
       add(a(i)*a(n-i), i=1..n-1)+
       add(a(d)*a(n/d), d=divisors(n) minus {1, n})+
       add(a(root(n, p))*a(p), p=divisors(igcd(seq(i[2],
           i=ifactors(n)[2]))) minus {0,1}))
    end:
seq(a(n), n=1..40);

a[n_] := a[n] = If[n==1, 1, Sum[a[i]*a[n-i], {i, 1, n-1}] + Sum[a[d]*a[n/d], {d, Divisors[n] ~Complement~ {1, n}}] + Sum[a[n^(1/p)] * a[p], {p, Divisors[GCD @@ Table[i[[2]], {i, FactorInteger[n]}]] ~Complement~ {0, 1}}]]; Array[a, 40] (* Jean-François Alcover, Apr 11 2017, translated from Maple *)

A213924 Minimal lengths of formulas representing n only using addition, exponentiation and the constant 1.

Original entry on oeis.org

1, 3, 5, 7, 9, 11, 13, 9, 9, 11, 13, 15, 17, 19, 21, 11, 13, 15, 17, 19, 21, 23, 25, 21, 13, 15, 11, 13, 15, 17, 19, 13, 15, 17, 19, 15, 17, 19, 21, 23, 23, 25, 23, 25, 25, 27, 29, 25, 17, 19, 21, 23, 25, 23, 25, 27, 27, 27, 25, 27, 29, 31, 27, 13, 15, 17, 19, 21, 23, 25, 27, 23, 23, 25, 27, 29, 31, 33

Offset: 1

Jonathan Vos Post, Mar 06 2013

nonn

			There are 502 different formulas for n=8. Two of them have shortest length 9: 11+111++^, 11+11+1+^. Thus a(8) = 9.

Alois P. Heinz, Table of n, a(n) for n = 1..10000
Shalosh B. Ekhad, Everything About Formulas Representing Integers Using Additions and Exponentiation for integers from 1 to 8000.
Edinah K. Ghang, Doron Zeilberger, Zeroless Arithmetic: Representing Integers ONLY using ONE, arXiv:1303.0885v1 [math.CO], 2013

Cf. A003037, A025280, A213923, A214843.

with(numtheory):
a:= proc(n) option remember; 1+ `if`(n=1, 0, min(
       seq(a(i)+a(n-i), i=1..n-1),
       seq(a(root(n, p))+a(p), p=divisors(igcd(seq(i[2],
           i=ifactors(n)[2]))) minus {0, 1})))
    end:
seq(a(n), n=1..100);  # Alois P. Heinz, Mar 12 2013

a[n_] := a[n] = 1 + If[n==1, 0, Min[Table[a[i]+a[n-i], {i, 1, n-1}], Table[ a[Floor[n^(1/p)]] + a[p], {p, Divisors[GCD @@ FactorInteger[n][[All, 2]]] ~Complement~ {0, 1}}]]]; Array[a, 100] (* Jean-François Alcover, Mar 22 2017, after Alois P. Heinz *)

A117618 Least number with complexity height of n, under integer complexity A005245.

Original entry on oeis.org

1, 6, 7, 10, 22, 683

Offset: 1

Jonathan Vos Post, Apr 07 2006

Consider the recursion: A005245(n), A005245(A005245(n)), A005245(A005245(A005245(n))), ... which we know is finite before reaching a fixed point, as A005245(n) <= n. The number of steps needed to reach such a fixed point is the complexity height of n (with respect to the A005245 measure of complexity, there being others in the OEIS).

a(7) >= 872573642639 = A005520(89). - David A. Corneth, May 06 2024

			a(1) = 1 because the A005245 complexity of 1 is 1, already giving a fixed point.
a(2) = 6 because it is the smallest x such that A005245(x) =/= x and A005245(x) = A005245(A005245(x)).
a(3) = 7 because 7 is the least number x with complexity 6, thus taking a further step of recursion to reach a fixed point.
a(4) = 10 because 10 is the least number with complexity 7.
a(5) = 22 because 22 is the least number with complexity 10.
a(6) = 683 because 683 is the least number with complexity 22.
a(7) = the least number with complexity 683.

W. A. Beyer, M. L. Stein and S. M. Ulam, The Notion of Complexity. Report LA-4822, Los Alamos Scientific Laboratory of the University of California, Los Alamos, NM, December 1971.
R. K. Guy, Unsolved Problems in Number Theory, Sect. F26.

W. A. Beyer, M. L. Stein and S. M. Ulam, The Notion of Complexity. Report LA-4822, Los Alamos Scientific Laboratory of the University of California, Los Alamos, NM, December 1971. [Annotated scanned copy]
R. K. Guy, Some suspiciously simple sequences, Amer. Math. Monthly 93 (1986), 186-190; 94 (1987), 965; 96 (1989), 905.
E. Pegg, Jr., Integer Complexity.
Eric Weisstein's World of Mathematics, Integer Complexity.
Index to sequences related to the complexity of n

Cf. A003037, A003313, A005245, A005421, A005520, A025280, A061373, A064097, A076091, A076142.

a(n) = least k such that A005245^(n)(k) = A005245^(n-1)(k) but (if n>1) A005245^(n-1)(k) != A005245^(n-2)(k), where ^ denotes repeated application.

For n >= 3, a(n) = A005520(a(n-1)). - Max Alekseyev, May 06 2024

a(2)=6 inserted by Giovanni Resta, Jun 15 2016

Edited by Max Alekseyev, May 06 2024

A217250 Minimal length of formulas representing n only using addition, multiplication, exponentiation and the constant 1.

Original entry on oeis.org

1, 3, 5, 7, 9, 9, 11, 9, 9, 11, 13, 13, 15, 15, 15, 11, 13, 13, 15, 15, 17, 17, 19, 15, 13, 15, 11, 13, 15, 17, 19, 13, 15, 17, 19, 13, 15, 17, 19, 19, 21, 21, 23, 21, 19, 21, 23, 17, 15, 17, 19, 19, 21, 15, 17, 17, 19, 19, 21, 21, 23, 23, 21, 13, 15, 17, 19

Offset: 1

Alois P. Heinz, Mar 16 2013

nonn

			a(6) = 9: there are 58 formulas representing 6 only using addition, multiplication, exponentiation and the constant 1. The formulas with minimal length 9 are: 11+111++*, 11+11+1+*, 111++11+*, 11+1+11+*.
a(8) = 9: 11+111++^, 11+11+1+^.
a(9) = 9: 111++11+^, 11+1+11+^.
a(10) = 11: 1111++11+^+, 111+1+11+^+, 111++11+^1+, 11+1+11+^1+.
All formulas are given in postfix (reverse Polish) notation but other notations would give the same results.

Alois P. Heinz, Table of n, a(n) for n = 1..10000
Edinah K. Ghang and Doron Zeilberger, Zeroless Arithmetic: Representing Integers ONLY using ONE, arXiv:1303.0885 [math.CO], 2013.
Shalosh B. Ekhad, Everything About Formulas Representing Integers Using Additions, Multiplication and Exponentiation for integers from 1 to 8000
Wikipedia, Postfix notation
Index to sequences related to the complexity of n

Cf. A025280, A213923, A213924, A214836, A217253.

with(numtheory):
a:= proc(n) option remember; 1+ `if`(n=1, 0, min(
      seq(a(i)+a(n-i), i=1..n/2),
      seq(a(d)+a(n/d), d=divisors(n) minus {1, n}),
      seq(a(root(n, p))+a(p), p=divisors(igcd(seq(i[2],
          i=ifactors(n)[2]))) minus {0, 1})))
    end:
seq(a(n), n=1..120);

a[n_] := a[n] = 1 + If[n==1, 0, Min[Table[a[i] + a[n-i], {i, 1, n/2}] ~Join~ Table[a[d] + a[n/d], {d, Divisors[n] ~Complement~ {1, n}}] ~Join~ Table[a[Floor[n^(1/p)]] + a[p], {p, Divisors[GCD @@ FactorInteger[n][[ All, 2]]] ~Complement~ {0, 1}}]]];
Array[a, 120] (* Jean-François Alcover, Mar 22 2017, translated from Maple *)

a(n) = 2*A025280(n)-1.

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

Original entry on oeis.org

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.

A361838 a(n) is the number of 2s in the binary hereditary representation of 2n.

Original entry on oeis.org

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

Offset: 1

Jodi Spitz, Mar 26 2023

See comments on A266201 for the definition of hereditary representation.

			A table of n, the binary hereditary representation of 2n, and the number of 2s in the representation:
 n | hereditary rep. of 2n   | number of 2s
---+-------------------------+--------------
 1 | 2                       |      1
 2 | 2^2                     |      2
 3 | 2^2+2                   |      3
 4 | 2^(2+1)                 |      2
 5 | 2^(2+1)+2               |      3
 6 | 2^(2+1)+2^2             |      4
 7 | 2^(2+1)+2^2+2           |      5
 8 | 2^2^2                   |      3
 9 | 2^2^2+2                 |      4
10 | 2^2^2+2^2               |      5
11 | 2^2^2+2^2+2             |      6
12 | 2^2^2+2^(2+1)           |      5
13 | 2^2^2+2^(2+1)+2         |      6
14 | 2^2^2+2^(2+1)+2^2       |      7
15 | 2^2^2+2^(2+1)+2^2+2     |      8
16 | 2^(2^2+1)               |      3
17 | 2^(2^2+1)+2             |      4
18 | 2^(2^2+1)+2^2           |      5
19 | 2^(2^2+1)+2^2+2         |      6
20 | 2^(2^2+1)+2^(2+1)       |      5
21 | 2^(2^2+1)+2^(2+1)+2     |      6
22 | 2^(2^2+1)+2^(2+1)+2^2   |      7
23 | 2^(2^2+1)+2^(2+1)+2^2+2 |      8
24 | 2^(2^2+1)+2^2^2         |      6
25 | 2^(2^2+1)+2^2^2+2       |      7
26 | 2^(2^2+1)+2^2^2+2^2     |      8
27 | 2^(2^2+1)+2^2^2+2^2+2   |      9
28 | 2^(2^2+1)+2^2^2+2^(2+1) |      8

Antti Karttunen, Table of n, a(n) for n = 1..65537

Cf. A005245, A025280.

a(n)=if(n==0, 0, sum(k=0, logint(n,2), if(bittest(n,k), 1 + a((k+1)\2)))) \\ Andrew Howroyd, Apr 07 2023

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,+,-,*,/,^}

A117632 Number of 1's required to build n using {+,T} and parentheses, where T(i) = i*(i+1)/2.

Original entry on oeis.org

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

Offset: 1

Jonathan Vos Post, Apr 08 2006

nonn

This problem has the optimal substructure property.

			a(1) = 1 because "1" has a single 1.
a(2) = 2 because "1+1" has two 1's.
a(3) = 2 because 3 = T(1+1) has two 1's.
a(6) = 2 because 6 = T(T(1+1)).
a(10) = 3 because 10 = T(T(1+1)+1).
a(12) = 4 because 12 = T(T(1+1)) + T(T(1+1)).
a(15) = 4 because 15 = T(T(1+1)+1+1).
a(21) = 2 because 21 = T(T(T(1+1))).
a(28) = 3 because 28 = T(T(T(1+1))+1).
a(55) = 3 because 55 = T(T(T(1+1)+1)).

W. A. Beyer, M. L. Stein and S. M. Ulam, The Notion of Complexity. Report LA-4822, Los Alamos Scientific Laboratory of the University of California, Los Alamos, NM, 1971.
R. K. Guy, Unsolved Problems Number Theory, Sect. F26.

Alois P. Heinz, Table of n, a(n) for n = 1..10000
W. A. Beyer, M. L. Stein and S. M. Ulam, The Notion of Complexity. Report LA-4822, Los Alamos Scientific Laboratory of the University of California, Los Alamos, NM, December 1971. [Annotated scanned copy]
R. K. Guy, Some suspiciously simple sequences, Amer. Math. Monthly 93 (1986), 186-190; 94 (1987), 965; 96 (1989), 905.
Ed Pegg, Jr., Integer Complexity.
Eric Weisstein's World of Mathematics, Integer Complexity.
Wikipedia, Optimal substructure.

See also A023361 = number of compositions into sums of triangular numbers, A053614 = numbers that are not the sum of triangular numbers. Iterated triangular numbers: A050536, A050542, A050548, A050909, A007501.

Cf. A000217, A005245, A005520, A003313, A076142, A076091, A061373, A005421, A023361, A053614, A064097, A025280, A003037, A099129, A050536, A050542, A050548, A050909, A007501.

a:= proc(n) option remember; local m; m:= floor (sqrt (n*2));
      if n<3 then n
    elif n=m*(m+1)/2 then a(m)
    else min (seq (a(i)+a(n-i), i=1..floor(n/2)))
      fi
    end:
seq (a(n), n=1..110);  # Alois P. Heinz, Jan 05 2011

a[n_] := a[n] = Module[{m = Floor[Sqrt[n*2]]}, If[n < 3, n, If[n == m*(m + 1)/2, a[m], Min[Table[a[i] + a[n - i], {i, 1, Floor[n/2]}]]]]];
Array[a, 110] (* Jean-François Alcover, Jun 02 2018, from Maple *)

I do not know how many of these entries have been proved to be minimal. - N. J. A. Sloane, Apr 15 2006

Corrected and extended by Alois P. Heinz, Jan 05 2011

A306560 Smallest number of 1's required to build n using +, *, ^ and tetration.

Original entry on oeis.org

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

Offset: 1

Robin Powell, Feb 23 2019

nonn

			a(16) = 5 because 16 = (1+1)^^(1+1+1). (Note that 16 is also the smallest index at which this sequence differs from A025280.)
a(34) = 8 because 34 = ((1+1)^^(1+1+1)+1)*(1+1). - _Jens Ahlström_, Jan 11 2023

Index to sequences related to the complexity of n

Cf. A005245, A025280, A323727.

from functools import lru_cache
from sympy import factorint, divisors
tetration = {2**2**2: 5, 2**2**2**2: 6, 3**3: 5, 4**4: 6, 5**5: 7}
@lru_cache(maxsize=None)
def a(n):
    res = n
    if n < 6:
        return res
    if n in tetration:
        return tetration[n]
    for i in range(1, n):
        res = min(res, a(i) + a(n-i))
    for d in [i for i in divisors(n) if i not in {1, n}]:
        res = min(res, a(d) + a(n//d))
    factors = factorint(n)
    exponents = set(factors.values())
    if len(exponents) == 1:
        e = exponents.pop()
        if e > 1:
            res = min(res, a(sum(factors.keys())) + a(e))
    return res
# Jens Ahlström, Jan 11 2023

a(34) onward corrected by Jens Ahlström, Jan 11 2023

cp's OEIS Frontend

A214836 Number of formula representations of n using addition, multiplication, exponentiation and the constant 1.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A213924 Minimal lengths of formulas representing n only using addition, exponentiation and the constant 1.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A117618 Least number with complexity height of n, under integer complexity A005245.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Formula

Extensions

A217250 Minimal length of formulas representing n only using addition, multiplication, exponentiation and the constant 1.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

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

Views

Author

Keywords

Examples

Links

Crossrefs

A361838 a(n) is the number of 2s in the binary hereditary representation of 2n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

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

A117632 Number of 1's required to build n using {+,T} and parentheses, where T(i) = i*(i+1)/2.

Views

Author

Keywords