OFFSET
1,2
LINKS
Alois P. Heinz, Table of n, a(n) for n = 1..10000
Shalosh B. Ekhad, Everything About Formulas Representing Integers Using Additions and Exponentiation for integers from 1 to 8000.
Edinah K. Ghang, Doron Zeilberger, Zeroless Arithmetic: Representing Integers ONLY using ONE, arXiv:1303.0885v1 [math.CO], 2013
EXAMPLE
There are 502 different formulas for n=8. Two of them have shortest length 9: 11+111++^, 11+11+1+^. Thus a(8) = 9.
MAPLE
with(numtheory):
a:= proc(n) option remember; 1+ `if`(n=1, 0, min(
seq(a(i)+a(n-i), i=1..n-1),
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..100); # Alois P. Heinz, Mar 12 2013
MATHEMATICA
a[n_] := a[n] = 1 + If[n==1, 0, Min[Table[a[i]+a[n-i], {i, 1, n-1}], Table[ a[Floor[n^(1/p)]] + a[p], {p, Divisors[GCD @@ FactorInteger[n][[All, 2]]] ~Complement~ {0, 1}}]]]; Array[a, 100] (* Jean-François Alcover, Mar 22 2017, after Alois P. Heinz *)
CROSSREFS
KEYWORD
nonn
AUTHOR
Jonathan Vos Post, Mar 06 2013
STATUS
approved