A213924 -id:A213924 - cp's OEIS frontend

A348262 Number of 1's required to build n using + and ^.

1, 2, 3, 4, 5, 6, 7, 5, 5, 6, 7, 8, 9, 10, 11, 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, 12, 13, 12, 13, 13, 14, 15, 13, 9, 10, 11, 12, 13, 12, 13, 14, 14, 14, 13, 14, 15, 16, 14, 7, 8, 9, 10, 11, 12, 13, 14, 12, 12, 13, 14, 15, 16, 17

Offset: 1

Glen Whitney, Oct 09 2021

nonn

			11+111++^ is a minimal-length RPN formula with value 8, using just these operators. It contains five occurrences of the symbol "1". Hence, a(8) = 5.

Glen Whitney, 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.
Glen Whitney, Python3.8 program to compute a(n)
Index to sequences related to the complexity of n

Cf. A213924 (expression-length complexity with the same set {1,+,^}).

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

a(n) = (A213924(n) + 1)/2.

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

Original entry on oeis.org

1, 1, 2, 6, 16, 48, 152, 502, 1694, 5832, 20420, 72472, 260096, 942304, 3441584, 12658128, 46842920, 174289108, 651610504, 2446686568, 9222628592, 34886505168, 132387975040, 503857644160, 1922782984688, 7355686851696, 28203617340756, 108368274550664

Offset: 1

Alois P. Heinz, Mar 08 2013

nonn

			a(1) = 1: 1.
a(2) = 1: 11+.
a(3) = 2: 111++, 11+1+.
a(4) = 6: 1111+++, 111+1++, 11+11++, 111++1+, 11+1+1+, 11+11+^.
a(5) = 16: 11111++++, 1111+1+++, 111+11+++, 1111++1++, 111+1+1++, 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+.
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
Shalosh B. Ekhad, Everything About Formulas Representing Integers Using Additions and Exponentiation for integers from 1 to 8000
Edinah K. Ghang and Doron Zeilberger, Zeroless Arithmetic: Representing Integers ONLY using ONE, arXiv:1303.0885 [math.CO], 2013.
Wikipedia, Postfix notation
Index to sequences related to the complexity of n

Cf. A213924, A214833, A214836.

with(numtheory):
a:= proc(n) option remember; `if`(n=1, 1,
       add(a(i)*a(n-i), i=1..n-1)+
       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[1] = 1; a[n_] := a[n] = Sum[a[i]*a[n-i], {i, 1, n-1}] + Sum[a[n^(1/p)] * a[p], {p, Divisors[GCD @@ FactorInteger[n][[All, 2]]] ~Complement~ {0, 1} } ];
Table[a[n], {n, 1, 40}] (* Jean-François Alcover, Nov 06 2017, after Alois P. Heinz *)

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.

cp's OEIS Frontend

A348262 Number of 1's required to build n using + and ^.

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

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

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

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