A217253 -id:A217253 - 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 *)

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

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

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica