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

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

Author

Daniel W. Grace, Jun 05 2024

Keywords

• nonn
• nice

Comments

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.

Examples

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

Links

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

Crossrefs

Cf. A002095, A005245, A214833.

Programs

Python

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

Formula

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.