A214833 -id:A214833 - cp's OEIS frontend

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

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

A242955 Decimal expansion of the constant c = lim f(n)*n^(3/2)/rho^n where f(n) = A214833(n) is the number of arithmetic formulas for n, and rho = A242970.

Original entry on oeis.org

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

Offset: 0

Jonathan Vos Post, Jun 09 2014

This is the constant c given on page 2 of E. K. Gnang and others.

Gnang et al. find f(n) = A214833(n) ~ c*rho^n/n^(3/2) as n -> oo, with rho given in A242970, and c given by the present sequence. - M. F. Hasler, May 04 2017

			c = 0.1456918546999792945604248360579...

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 rho is given in A242970.

Cf. A214833.

Offset corrected, definition improved, more terms from M. F. Hasler, May 04 2017

A213923 Minimal lengths of formulas representing n only using addition, multiplication and the constant 1.

Original entry on oeis.org

1, 3, 5, 7, 9, 9, 11, 11, 11, 13, 15, 13, 15, 15, 15, 15, 17, 15, 17, 17, 17, 19, 21, 17, 19, 19, 17, 19, 21, 19, 21, 19, 21, 21, 21, 19, 21, 21, 21, 21, 23, 21, 23, 23, 21, 23, 25, 21, 23, 23, 23, 23, 25, 21, 23, 23, 23, 25, 27, 23, 25, 25, 23, 23, 25, 25, 27, 25, 27, 25, 27, 23, 25, 25, 25, 25, 27, 25

Offset: 1

Jonathan Vos Post, Mar 06 2013

nonn

			a(3) = 5 because for n = 3, the minimum is length = 5, formula = "11+1+" or "111++".

Alois P. Heinz, Table of n, a(n) for n = 1..10000
Shalosh B. Ekhad, Everything About Formulas Representing Integers Using Additions and Multiplication for integers from 1 to 8000.
Edinah K. Ghang, Doron Zeilberger, Zeroless Arithmetic: Representing Integers ONLY using ONE, arXiv:1303.0885 [math.CO], 2013

Cf. A005245, A214833.

with(numtheory):
a:= proc(n) option remember;
       1+ `if`(n=1, 0, min(seq(a(i)+a(n-i), i=1..n/2),
       seq(a(d)+a(n/d), d=divisors(n) minus {1, n})))
    end:
seq(a(n), n=1..100);  # Alois P. Heinz, Mar 07 2013

a[n_] := a[n] = 1 + If[n == 1, 0, Min[Join[Table[a[i] + a[n-i], {i, 1, n/2}], Table[a[d] + a[n/d], {d, Divisors[n] ~Complement~ {1, n}}]]]]; Table[a[n], {n, 1, 100}] (* Jean-François Alcover, Feb 01 2017, after Alois P. Heinz *)

a(n) = 2*A005245(n)-1.

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

Original entry on oeis.org

1, 1, 2, 7, 18, 58, 180, 613, 2076, 7270, 25752, 92918, 338432, 1246092, 4624536, 17290646, 65047436, 246079536, 935484928, 3571960668, 13692523960, 52675401248, 203299385584, 786949008100, 3054440440486, 11884949139900, 46351113658232, 181153317512536

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) = 7: 1111+++, 111+1++, 11+11++, 111++1+, 11+1+1+, 11+11+*, 11+11+^.
a(5) = 18: 11111++++, 1111+1+++, 111+11+++, 1111++1++, 111+1+1++, 111+11+*+, 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+, 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
Edinah K. Ghang and Doron Zeilberger, Zeroless Arithmetic: Representing Integers ONLY using ONE, arXiv:1303.0885 [math.CO], 2013.
Shalosh B. Ekhad, Everything About Formulas Representing Integers Using Additions, Multiplication and Exponentiation for integers from 1 to 8000
Wikipedia, Postfix notation
Index to sequences related to the complexity of n

Cf. A025280, A214833, A214843, A217250, A217253.

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})+
       add(a(root(n, p))*a(p), p=divisors(igcd(seq(i[2],
           i=ifactors(n)[2]))) minus {0,1}))
    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] ~Complement~ {1, n}}] + Sum[a[n^(1/p)] * a[p], {p, Divisors[GCD @@ Table[i[[2]], {i, FactorInteger[n]}]] ~Complement~ {0, 1}}]]; Array[a, 40] (* Jean-François Alcover, Apr 11 2017, translated from Maple *)

A214843 Number of formula representations of n using addition, exponentiation and the constant 1.

Original entry on oeis.org

1, 1, 2, 6, 16, 48, 152, 502, 1694, 5832, 20420, 72472, 260096, 942304, 3441584, 12658128, 46842920, 174289108, 651610504, 2446686568, 9222628592, 34886505168, 132387975040, 503857644160, 1922782984688, 7355686851696, 28203617340756, 108368274550664

Offset: 1

Alois P. Heinz, Mar 08 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 Exponentiation for integers from 1 to 8000
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. A213924, A214833, A214836.

with(numtheory):
a:= proc(n) option remember; `if`(n=1, 1,
       add(a(i)*a(n-i), i=1..n-1)+
       add(a(root(n, p))*a(p), p=divisors(igcd(seq(i[2],
           i=ifactors(n)[2]))) minus {0, 1}))
    end:
seq(a(n), n=1..40);

a[1] = 1; a[n_] := a[n] = Sum[a[i]*a[n-i], {i, 1, n-1}] + Sum[a[n^(1/p)] * a[p], {p, Divisors[GCD @@ FactorInteger[n][[All, 2]]] ~Complement~ {0, 1} } ];
Table[a[n], {n, 1, 40}] (* Jean-François Alcover, Nov 06 2017, after Alois P. Heinz *)

A214835 Total sum of lengths of formula representations of n using addition, multiplication and the constant 1.

Original entry on oeis.org

1, 3, 10, 42, 144, 564, 2064, 7944, 30252, 117000, 453192, 1768480, 6917504, 27163232, 106923648, 421931308, 1668250408, 6608054656, 26215991648, 104154492224, 414324786144, 1650080158832, 6578448714144, 26251704924528, 104850927048448, 419119282453408

Offset: 1

Alois P. Heinz, Mar 07 2013

nonn

			a(1) = 1: 1.
a(2) = 3: 11+.
a(3) = 10: 111++, 11+1+.
a(4) = 42: 1111+++, 111+1++, 11+11++, 111++1+, 11+1+1+, 11+11+*.
a(5) = 144: 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+.

Alois P. Heinz, Table of n, a(n) for n = 1..100
Edinah K. Ghang, Doron Zeilberger, Zeroless Arithmetic: Representing Integers ONLY using ONE, arXiv:1303.0885v1 [math.CO], 2013
Shalosh B. Ekhad, Everything About Formulas Representing Integers Using Additions and Multiplication for integers from 1 to 8000
Wikipedia, Postfix notation
Index to sequences related to the complexity of n

Cf. A005245, A214833 (number of formula representations), A213923 (minimal length of formula), A005408(n-1) (maximal length of formula).

A373446 Number of distinct ways of expressing n using only addition, multiplication (with all factors greater than 1), necessary parentheses, and the number 1.

Original entry on oeis.org

1, 1, 1, 2, 2, 3, 3, 6, 7, 10, 10, 18, 19, 27, 30, 50, 53, 80, 85, 133, 146, 209, 223, 350, 382, 544, 597, 886, 962, 1385, 1507, 2197, 2426, 3422, 3740, 5413, 5941, 8295, 9159, 12994, 14298, 19947, 21982, 30763, 34111, 47005, 51895, 72202, 79974, 109468, 121545, 167032, 185276, 252534, 280427, 382274, 425703, 575650, 640243, 867942

Offset: 1

Daniel W. Grace, Jun 05 2024

Expressions that are the same after commuting their terms are not considered distinct from one another.

Parentheses are used around a sum which is being multiplied, but not otherwise.

			a(10)=10, as 10 can be expressed in the following ways:
  1+1+1+1+1+1+1+1+1+1
  (1+1)*(1+1)+1+1+1+1+1+1
  (1+1)*(1+1)+(1+1)*(1+1)+1+1
  (1+1)*(1+1)*(1+1)+1+1
  (1+1)*(1+1+1)+1+1+1+1
  (1+1)*(1+1+1)+(1+1)*(1+1)
  (1+1)*(1+1+1+1)+1+1
  (1+1+1)*(1+1+1)+1
  (1+1)*(1+1+1+1+1)
  (1+1)*((1+1)*(1+1)+1).

Pontus von Brömssen, Table of n, a(n) for n = 1..10000

Cf. A002095, A005245, A214833.

from itertools import count,islice
from collections import Counter
from math import comb
from sympy import divisors
def euler_transform(x):
    xlist = []
    z = []
    y = []
    for n,x in enumerate(x,1):
        xlist.append(x)
        z.append(sum(d*xlist[d-1] for d in divisors(n)))
        yy = (z[-1]+sum(zz*yy for zz,yy in zip(z,reversed(y))))//n
        yield yy
        y.append(yy)
def factorizations(n,fmin=2):
    if n == 1:
        yield []
        return
    for d in divisors(n,generator=True):
        if d < fmin: continue
        for f in factorizations(n//d,d):
            yield [d]+f
def A373446_generator():
    alist = []
    def bgen():
        blist = []
        for n in count(1):
            b = 0
            for p in factorizations(n):
                if len(p) == 1: continue
                m = 1
                for k,c in Counter(p).items():
                    m *= comb(alist[k-1]-blist[k-1]+c-1,c)
                b += m
            yield b
            blist.append(b)
    for a in euler_transform(bgen()):
        yield a
        alist.append(a)
print(list(islice(A373446_generator(),60))) # Pontus von Brömssen, Jun 13 2024

a(n) >= a(n-1) since, if "+1" is appended to each expression used to calculate a(n-1), then each of the resulting expressions equate to n and are distinct from each other. There may or may not be other ways to express n that do not include an isolated "+1", hence the greater-than possibility.

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

A242955 Decimal expansion of the constant c = lim f(n)*n^(3/2)/rho^n where f(n) = A214833(n) is the number of arithmetic formulas for n, and rho = A242970.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A213923 Minimal lengths of formulas representing n only using addition, multiplication and the constant 1.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

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

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A214843 Number of formula representations of n using addition, exponentiation and the constant 1.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A214835 Total sum of lengths of formula representations of n using addition, multiplication and the constant 1.

Views

Author

Keywords

Examples

Links

Crossrefs

A373446 Number of distinct ways of expressing n using only addition, multiplication (with all factors greater than 1), necessary parentheses, and the number 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Python

Formula