A214843 Number of formula representations of n using addition, exponentiation and the constant 1.

1, 1, 2, 6, 16, 48, 152, 502, 1694, 5832, 20420, 72472, 260096, 942304, 3441584, 12658128, 46842920, 174289108, 651610504, 2446686568, 9222628592, 34886505168, 132387975040, 503857644160, 1922782984688, 7355686851696, 28203617340756, 108368274550664

Offset: 1

Author

Alois P. Heinz, Mar 08 2013

Keywords

• nonn

Examples

			a(1) = 1: 1.
a(2) = 1: 11+.
a(3) = 2: 111++, 11+1+.
a(4) = 6: 1111+++, 111+1++, 11+11++, 111++1+, 11+1+1+, 11+11+^.
a(5) = 16: 11111++++, 1111+1+++, 111+11+++, 1111++1++, 111+1+1++, 111+11+^+, 11+111+++, 11+11+1++, 111++11++, 11+1+11++, 1111+++1+, 111+1++1+, 11+11++1+, 111++1+1+, 11+1+1+1+, 11+11+^1+.
All formulas are given in postfix (reverse Polish) notation but other notations would give the same results.
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 1..1000
• Shalosh B. Ekhad, Everything About Formulas Representing Integers Using Additions and Exponentiation for integers from 1 to 8000
• Edinah K. Ghang and Doron Zeilberger, Zeroless Arithmetic: Representing Integers ONLY using ONE, arXiv:1303.0885 [math.CO], 2013.
• Wikipedia, Postfix notation
• Index to sequences related to the complexity of n

Crossrefs

Cf. A213924, A214833, A214836.

Programs

Maple

with(numtheory):
a:= proc(n) option remember; `if`(n=1, 1,
       add(a(i)*a(n-i), i=1..n-1)+
       add(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..40);

Mathematica

a[1] = 1; a[n_] := a[n] = Sum[a[i]*a[n-i], {i, 1, n-1}] + Sum[a[n^(1/p)] * a[p], {p, Divisors[GCD @@ FactorInteger[n][[All, 2]]] ~Complement~ {0, 1} } ];
Table[a[n], {n, 1, 40}] (* Jean-François Alcover, Nov 06 2017, after Alois P. Heinz *)