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 Multiplication for integers from 1 to 8000
Edinah K. Gnang, Maksym Radziwill, and Carlo Sanna, Counting arithmetic formulas, arXiv:1406.1704 [math.CO], 2014.
Edinah K. Gnang, Maksym Radziwill, and Carlo Sanna, Counting arithmetic formulas, European Journal of Combinatorics 47 (2015), pp. 40-53.
Edinah K. Ghang and Doron Zeilberger, Zeroless Arithmetic: Representing Integers ONLY using ONE, arXiv:1303.0885 [math.CO], 2013.
Wikipedia, Postfix notation
FORMULA
a(n) = Sum_{i=1..n-1} a(i)*a(n-i) + Sum_{d|n, 1<d<n} a(d)*a(n/d) for n>1, a(1)=1.
a(n) ~ c * d^n / n^(3/2), where d = 4.076561785276... = A242970, c = 0.145691854699979... = A242955. - Vaclav Kotesovec, Sep 12 2014
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(d)*a(n/d), d=divisors(n) minus {1, n}))
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][[2 ;; -2]]}]]; Table[a[n], {n, 1, 40}] (* Jean-François Alcover, Feb 05 2015, after Alois P. Heinz *)
PROG
CROSSREFS
KEYWORD
nonn
AUTHOR
Alois P. Heinz, Mar 07 2013
STATUS
approved