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
Keywords
Examples
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.
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
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(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 *)