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