login
A213924
Minimal lengths of formulas representing n only using addition, exponentiation and the constant 1.
4
1, 3, 5, 7, 9, 11, 13, 9, 9, 11, 13, 15, 17, 19, 21, 11, 13, 15, 17, 19, 21, 23, 25, 21, 13, 15, 11, 13, 15, 17, 19, 13, 15, 17, 19, 15, 17, 19, 21, 23, 23, 25, 23, 25, 25, 27, 29, 25, 17, 19, 21, 23, 25, 23, 25, 27, 27, 27, 25, 27, 29, 31, 27, 13, 15, 17, 19, 21, 23, 25, 27, 23, 23, 25, 27, 29, 31, 33
OFFSET
1,2
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