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

1, 1, 2, 7, 18, 58, 180, 613, 2076, 7270, 25752, 92918, 338432, 1246092, 4624536, 17290646, 65047436, 246079536, 935484928, 3571960668, 13692523960, 52675401248, 203299385584, 786949008100, 3054440440486, 11884949139900, 46351113658232, 181153317512536

Offset

1,3

Links

Alois P. Heinz, Table of n, a(n) for n = 1..1000

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

Example

a(1) = 1: 1.
a(2) = 1: 11+.
a(3) = 2: 111++, 11+1+.
a(4) = 7: 1111+++, 111+1++, 11+11++, 111++1+, 11+1+1+, 11+11+*, 11+11+^.
a(5) = 18: 11111++++, 1111+1+++, 111+11+++, 1111++1++, 111+1+1++, 111+11+*+, 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+, 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(d)*a(n/d), d=divisors(n) minus {1, n})+
       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[n_] := a[n] = If[n==1, 1, Sum[a[i]*a[n-i], {i, 1, n-1}] + Sum[a[d]*a[n/d], {d, Divisors[n] ~Complement~ {1, n}}] + Sum[a[n^(1/p)] * a[p], {p, Divisors[GCD @@ Table[i[[2]], {i, FactorInteger[n]}]] ~Complement~ {0, 1}}]]; Array[a, 40] (* Jean-François Alcover, Apr 11 2017, translated from Maple *)

Crossrefs

Cf. A025280, A214833, A214843, A217250, A217253.

Sequence in context: A046866 A291255 A294004 * A176813 A000988 A185308

Adjacent sequences: A214833 A214834 A214835 * A214837 A214838 A214839

Keyword

nonn

Author

Alois P. Heinz, Mar 07 2013

Status

approved