|
%I #70 Feb 22 2021 12:43:26
%S 1,1,2,6,16,52,160,536,1796,6216,21752,77504,278720,1013184,3712128,
%T 13701204,50880808,190003808,712975648,2687114976,10167088608,
%U 38605365712,147060726688,561853414896,2152382687488,8265949250848,31817041756880,122728993889056
%N Number of formula representations of n using addition, multiplication and the constant 1.
%H Alois P. Heinz, <a href="/A214833/b214833.txt">Table of n, a(n) for n = 1..1000</a>
%H Shalosh B. Ekhad, <a href="http://www.math.rutgers.edu/~zeilberg/tokhniot/oArithFormulas1">Everything About Formulas Representing Integers Using Additions and Multiplication for integers from 1 to 8000</a>
%H Edinah K. Gnang, Maksym Radziwill, and Carlo Sanna, <a href="https://arxiv.org/abs/1406.1704">Counting arithmetic formulas</a>, arXiv:1406.1704 [math.CO], 2014.
%H Edinah K. Gnang, Maksym Radziwill, and Carlo Sanna, <a href="https://dx.doi.org/10.1016/j.ejc.2015.01.007">Counting arithmetic formulas</a>, European Journal of Combinatorics 47 (2015), pp. 40-53.
%H Edinah K. Ghang and Doron Zeilberger, <a href="https://arxiv.org/abs/1303.0885">Zeroless Arithmetic: Representing Integers ONLY using ONE</a>, arXiv:1303.0885 [math.CO], 2013.
%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Postfix_notation">Postfix notation</a>
%H <a href="/index/Com#complexity">Index to sequences related to the complexity of n</a>
%F 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.
%F a(n) ~ c * d^n / n^(3/2), where d = 4.076561785276... = A242970, c = 0.145691854699979... = A242955. - _Vaclav Kotesovec_, Sep 12 2014
%e a(1) = 1: 1.
%e a(2) = 1: 11+.
%e a(3) = 2: 111++, 11+1+.
%e a(4) = 6: 1111+++, 111+1++, 11+11++, 111++1+, 11+1+1+, 11+11+*.
%e 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+.
%e All formulas are given in postfix (reverse Polish) notation but other notations would give the same results.
%p with(numtheory):
%p a:= proc(n) option remember; `if`(n=1, 1,
%p add(a(i)*a(n-i), i=1..n-1)+
%p add(a(d)*a(n/d), d=divisors(n) minus {1, n}))
%p end:
%p seq(a(n), n=1..40);
%t 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_ *)
%o (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
%Y Cf. A213923 (minimal length of formula), A005408(n-1) (maximal length of formula), A214835 (total sum of lengths), A214836, A214843, A242970, A242955.
%K nonn
%O 1,3
%A _Alois P. Heinz_, Mar 07 2013
|
