login
A217253
Number of minimal length formulas representing n only using addition, multiplication, exponentiation and the constant 1.
3
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
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
Sequence in context: A013092 A174311 A220396 * A268837 A104310 A301325
KEYWORD
nonn
AUTHOR
Alois P. Heinz, Mar 16 2013
STATUS
approved