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
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
KEYWORD
nonn
AUTHOR
Alois P. Heinz, Mar 16 2013
STATUS
approved