A217253 Number of minimal length formulas representing n only using addition, multiplication, exponentiation and the constant 1.

1, 1, 2, 7, 18, 4, 8, 2, 2, 4, 12, 36, 72, 16, 72, 14, 28, 4, 8, 8, 48, 24, 48, 8, 18, 36, 4, 8, 24, 96, 328, 18, 36, 164, 472, 4, 8, 24, 80, 144, 288, 224, 560, 216, 72, 144, 432, 56, 8, 52, 232, 72, 144, 8, 16, 16, 32, 48, 96, 256, 512, 656, 32, 20, 40, 120

Offset: 1

Author

Alois P. Heinz, Mar 16 2013

Keywords

• nonn

Examples

			a(6) = 4: there are 58 formulas representing 6 only using addition, multiplication, exponentiation and the constant 1. The 4 formulas with minimal length 9 are: 11+111++*, 11+11+1+*, 111++11+*, 11+1+11+*.
a(8) = 2: 11+111++^, 11+11+1+^.
a(9) = 2: 111++11+^, 11+1+11+^.
a(10) = 4: 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.
		

Links

• 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

Crossrefs

Cf. A214836, A217250.

Programs

Maple

with(numtheory):
b:= proc(n) option remember; local d, i, l, m, p, t;
      if n=1 then [1, 1] else l, m:= infinity, 0;
        for i to n-1 do  t:=  1+b(i)[1]+b(n-i)[1];
          if t=l then    m:= m +b(i)[2]*b(n-i)[2]
        elif t b(n)[2]:
seq(a(n), n=1..100);

Mathematica

b[1] = {1, 1}; b[n_] := b[n] = Module[{d, i, l, m, p, t}, {l, m} = { Infinity, 0}; For[i=1, i <= n-1, i++, t = 1 + b[i][[1]] + b[n - i][[1]]; Which[t==l, m = m + b[i][[2]]*b[n-i][[2]], tJean-François Alcover, Mar 22 2017, translated from Maple *)