login
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, 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,4
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.
LINKS
Pontus von Brömssen, Table of n, a(n) for n = 1..10000
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.
EXAMPLE
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).
PROG
(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
CROSSREFS
KEYWORD
nonn,nice
AUTHOR
Daniel W. Grace, Jun 05 2024
STATUS
approved