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,3

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

Example

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.

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<l then l, m:= t, b(i)[2]*b(n-i)[2] fi od;
        for d in divisors(n) minus {1, n} do t:= 1+b(d)[1]+b(n/d)[1];
          if t=l then    m:= m +b(d)[2]*b(n/d)[2]
        elif t<l then l, m:= t, b(d)[2]*b(n/d)[2] fi od;
        for p in divisors(igcd(seq(i[2], i=ifactors(n)[2])))
          minus {0, 1} do t:= 1+b(p)[1]+b(root(n, p))[1];
          if t=l then    m:= m +b(p)[2]*b(root(n, p))[2]
        elif t<l then l, m:= t, b(p)[2]*b(root(n, p))[2] fi od; [l, m]
      fi
    end:
a:= n-> 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]], t<l, {l, m} = {t, b[i][[2]] * b[n-i][[2]]}]]; Do[t = 1 + b[d][[1]] + b[n/d][[1]]; Which[t==l, m = m + b[d][[2]]*b[n/d][[2]], t<l, {l, m} = {t, b[d][[2]]*b[n/d][[2]] }], {d, Divisors[n] ~Complement~ {1, n}}]; Do[t = 1 + b[p][[1]] + b[Floor[ n^(1/p)]][[1]]; Which[t==l, m = m + b[p][[2]]*b[Floor[n^(1/p)]][[2]], t<l, {l, m} = {t, b[p][[2]]*b[Floor[n^(1/p)]][[2]]}], {p, Divisors[ GCD @@ FactorInteger[n][[ All, 2]]] ~Complement~ {0, 1}}]; {l, m}];
a[n_] := b[n][[2]];
Array[a, 100] (* Jean-François Alcover, Mar 22 2017, translated from Maple *)

Crossrefs

Cf. A214836, A217250.

Sequence in context: A013092 A174311 A220396 * A268837 A104310 A301325

Adjacent sequences: A217250 A217251 A217252 * A217254 A217255 A217256

Keyword

nonn

Author

Alois P. Heinz, Mar 16 2013

Status

approved