login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A214833 Number of formula representations of n using addition, multiplication and the constant 1. 7
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 (list; graph; refs; listen; history; text; internal format)
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: A339844 A258797 A214983 * A263593 A003446 A300668

Adjacent sequences:  A214830 A214831 A214832 * A214834 A214835 A214836

KEYWORD

nonn

AUTHOR

Alois P. Heinz, Mar 07 2013

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified July 30 15:29 EDT 2021. Contains 346359 sequences. (Running on oeis4.)