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

1, 1, 2, 6, 16, 52, 160, 536, 1796, 6216, 21752, 77504, 278720, 1013184, 3712128, 13701204, 50880808, 190003808, 712975648, 2687114976, 10167088608, 38605365712, 147060726688, 561853414896, 2152382687488, 8265949250848, 31817041756880, 122728993889056

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

Index to sequences related to the complexity of n

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

(PARI) A214833_vec=[1]; alias(A, A214833_vec); A214833(n)={n>#A&&A=concat(A, vector(n-#A)); if(A[n], A[n], A[n]=sum(i=1, n-1, A214833(i)*A214833(n-i))+sumdiv(n, d, if(d>1&&d<n, A214833(d)*A214833(n/d))))} \\ M. F. Hasler, May 04 2017

Crossrefs

Cf. A213923 (minimal length of formula), A005408(n-1) (maximal length of formula), A214835 (total sum of lengths), A214836, A214843, A242970, A242955.

Sequence in context: A360232 A214983 A367389 * A263593 A003446 A300668

Adjacent sequences: A214830 A214831 A214832 * A214834 A214835 A214836

Keyword

nonn

Author

Alois P. Heinz, Mar 07 2013

Status

approved