%I #25 Feb 22 2021 13:21:18
%S 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,
%T 24,96,328,18,36,164,472,4,8,24,80,144,288,224,560,216,72,144,432,56,
%U 8,52,232,72,144,8,16,16,32,48,96,256,512,656,32,20,40,120
%N Number of minimal length formulas representing n only using addition, multiplication, exponentiation and the constant 1.
%H Alois P. Heinz, <a href="/A217253/b217253.txt">Table of n, a(n) for n = 1..10000</a>
%H Edinah K. Ghang and Doron Zeilberger, <a href="https://arxiv.org/abs/1303.0885">Zeroless Arithmetic: Representing Integers ONLY using ONE</a>, arXiv:1303.0885 [math.CO], 2013
%H Shalosh B. Ekhad, <a href="http://www.math.rutgers.edu/~zeilberg/tokhniot/oArithFormulas2">Everything About Formulas Representing Integers Using Additions, Multiplication and Exponentiation for integers from 1 to 8000</a>
%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Postfix_notation">Postfix notation</a>
%H <a href="/index/Com#complexity">Index to sequences related to the complexity of n</a>
%e 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+*.
%e a(8) = 2: 11+111++^, 11+11+1+^.
%e a(9) = 2: 111++11+^, 11+1+11+^.
%e a(10) = 4: 1111++11+^+, 111+1+11+^+, 111++11+^1+, 11+1+11+^1+.
%e All formulas are given in postfix (reverse Polish) notation but other notations would give the same results.
%p with(numtheory):
%p b:= proc(n) option remember; local d, i, l, m, p, t;
%p if n=1 then [1, 1] else l, m:= infinity, 0;
%p for i to n-1 do t:= 1+b(i)[1]+b(n-i)[1];
%p if t=l then m:= m +b(i)[2]*b(n-i)[2]
%p elif t<l then l, m:= t, b(i)[2]*b(n-i)[2] fi od;
%p for d in divisors(n) minus {1, n} do t:= 1+b(d)[1]+b(n/d)[1];
%p if t=l then m:= m +b(d)[2]*b(n/d)[2]
%p elif t<l then l, m:= t, b(d)[2]*b(n/d)[2] fi od;
%p for p in divisors(igcd(seq(i[2], i=ifactors(n)[2])))
%p minus {0, 1} do t:= 1+b(p)[1]+b(root(n, p))[1];
%p if t=l then m:= m +b(p)[2]*b(root(n, p))[2]
%p elif t<l then l, m:= t, b(p)[2]*b(root(n, p))[2] fi od; [l, m]
%p fi
%p end:
%p a:= n-> b(n)[2]:
%p seq(a(n), n=1..100);
%t 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}];
%t a[n_] := b[n][[2]];
%t Array[a, 100] (* _Jean-François Alcover_, Mar 22 2017, translated from Maple *)
%Y Cf. A214836, A217250.
%K nonn
%O 1,3
%A _Alois P. Heinz_, Mar 16 2013