A242955 -id:A242955 - cp's OEIS frontend

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

Alois P. Heinz, Mar 07 2013

nonn

			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.

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

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

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);

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 *)

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&&dA214833(d)*A214833(n/d))))} \\ M. F. Hasler, May 04 2017

a(n) = Sum_{i=1..n-1} a(i)*a(n-i) + Sum_{d|n, 11, 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

A242970 Decimal expansion of the constant rho = lim f(n)^(1/n), where f(n) = A214833(n) is the number of arithmetic formulas for n (cf. comments).

Original entry on oeis.org

4, 0, 7, 6, 5, 6, 1, 7, 8, 5, 2, 7, 6, 0, 4, 6, 1, 9, 8, 6, 0, 4, 0, 2, 2, 8, 5, 2, 8, 1, 5, 0, 2, 0, 2, 6

Offset: 1

Jonathan Vos Post, Jun 09 2014

This is the constant ρ, given on page 2 of E. K. Gnang and others. From the abstract: "An arithmetic formula is an expression involving only the constant 1, and the binary operations of addition and multiplication, with multiplication by 1 not allowed. We obtain an asymptotic formula for the number of arithmetic formulas evaluating to n as n goes to infinity, solving a conjecture of E. K. Gnang and D. Zeilberger."

More precisely: Let f(n) = A214833(n) be the number of arithmetic formulas for n. Then there exist constants c > 0 and ρ > 4 such that f(n) ~ c*ρ^n/n^(3/2) as n -> oo where ρ = 4.076561785276046... given in this sequence, and c = 0.145691854699979... given in A242955. - M. F. Hasler, May 04 2017

			ρ = 4.07656178527604619860402285281502026...

Edinah K. Gnang, Maksym Radziwill, Carlo Sanna, Counting arithmetic formulas, arXiv:1406.1704 [math.CO], (6 June 2014).
Edinah K. Gnang, Maksym Radziwill, Carlo Sanna, Counting arithmetic formulas, European Journal of Combinatorics 47 (2015), pp. 40-53.

The constant c = lim f(n)*n^(3/2)/rho^n is given in A242955.

Cf. A214833.

f(n) = A214833(n) ~ c*ρ^n/n^(3/2) = A242955*A242970^n/n^(3/2) as n -> oo, thus rho = A242970 = lim f(n)^(1/n) = lim f(n+1)/f(n) = lim (1+1/n)^(3/2)*f(n+1)/f(n), the latter expression being the most accurate/rapidly converging of the three. The values for n = 999, however, yield only 6 correct decimals (4.076559...). - M. F. Hasler, May 04 2017

Edited by M. F. Hasler, May 03 2017

cp's OEIS Frontend

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

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula