

A217250


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


3



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
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,2


LINKS

Alois P. Heinz, Table of n, a(n) for n = 1..10000
Edinah K. Ghang, 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(ni), 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[ni], {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] (* JeanFranç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



