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,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

Cf. A003037, A025280, A213923, A214843.

Sequence in context: A151916 A187687 A056617 * A082655 A050828 A329405

Adjacent sequences: A213921 A213922 A213923 * A213925 A213926 A213927

Keyword

nonn

Author

Jonathan Vos Post, Mar 06 2013

Status

approved