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

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

Example

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.

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

Crossrefs

Cf. A213924, A214833, A214836.

Sequence in context: A230929 A367042 A291189 * A272411 A151528 A132803

Adjacent sequences: A214840 A214841 A214842 * A214844 A214845 A214846

Keyword

nonn

Author

Alois P. Heinz, Mar 08 2013

Status

approved