OFFSET
1,2
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
FORMULA
a(n) = 2*A025280(n)-1.
EXAMPLE
a(6) = 9: there are 58 formulas representing 6 only using addition, multiplication, exponentiation and the constant 1. The formulas with minimal length 9 are: 11+111++*, 11+11+1+*, 111++11+*, 11+1+11+*.
a(8) = 9: 11+111++^, 11+11+1+^.
a(9) = 9: 111++11+^, 11+1+11+^.
a(10) = 11: 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):
a:= proc(n) option remember; 1+ `if`(n=1, 0, min(
seq(a(i)+a(n-i), i=1..n/2),
seq(a(d)+a(n/d), d=divisors(n) minus {1, n}),
seq(a(root(n, p))+a(p), p=divisors(igcd(seq(i[2],
i=ifactors(n)[2]))) minus {0, 1})))
end:
seq(a(n), n=1..120);
MATHEMATICA
a[n_] := a[n] = 1 + If[n==1, 0, Min[Table[a[i] + a[n-i], {i, 1, n/2}] ~Join~ Table[a[d] + a[n/d], {d, Divisors[n] ~Complement~ {1, n}}] ~Join~ Table[a[Floor[n^(1/p)]] + a[p], {p, Divisors[GCD @@ FactorInteger[n][[ All, 2]]] ~Complement~ {0, 1}}]]];
Array[a, 120] (* Jean-François Alcover, Mar 22 2017, translated from Maple *)
CROSSREFS
KEYWORD
nonn
AUTHOR
Alois P. Heinz, Mar 16 2013
STATUS
approved