A217250 Minimal length of formulas representing n only using addition, multiplication, exponentiation and the constant 1.

1, 3, 5, 7, 9, 9, 11, 9, 9, 11, 13, 13, 15, 15, 15, 11, 13, 13, 15, 15, 17, 17, 19, 15, 13, 15, 11, 13, 15, 17, 19, 13, 15, 17, 19, 13, 15, 17, 19, 19, 21, 21, 23, 21, 19, 21, 23, 17, 15, 17, 19, 19, 21, 15, 17, 17, 19, 19, 21, 21, 23, 23, 21, 13, 15, 17, 19

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

Index to sequences related to the complexity of n

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

Cf. A025280, A213923, A213924, A214836, A217253.

Sequence in context: A274988 A265509 A265527 * A213923 A218452 A007731

Adjacent sequences: A217247 A217248 A217249 * A217251 A217252 A217253

Keyword

nonn

Author

Alois P. Heinz, Mar 16 2013

Status

approved