A213924 Minimal lengths of formulas representing n only using addition, exponentiation and the constant 1.

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

Author

Jonathan Vos Post, Mar 06 2013

Keywords

• nonn

Examples

			There are 502 different formulas for n=8. Two of them have shortest length 9: 11+111++^, 11+11+1+^. Thus a(8) = 9.
		

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

Crossrefs

Cf. A003037, A025280, A213923, A214843.

Programs

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 *)