A345882 Number of numbers expressible as b(1)*b(2)*...*b(n) with 1 <= b(i) <= i for each i.

1, 2, 5, 11, 30, 64, 178, 382, 758, 1367, 3620, 7193, 19707, 40867, 75706, 130017, 339506, 667390, 1824656, 3724917, 6785689, 11545898, 30099090, 58833294, 105348580, 176098677, 282847446, 438090287, 1095200628, 2057512312, 5494259815, 10925293558, 19311381148

Offset: 1

Author

David Galvin, Sep 16 2021

Keywords

• nonn
• nice

Comments

On replacing * with +, one gets A000124.

In other words, take n! = 1*2*3*...*n and replace any factor by any smaller number. a(n) is the number of different numbers that can be obtained. If b(i) is required to be a divisor of i, we get A027423. - N. J. A. Sloane, Sep 18 2021

Examples

			For n=3, b(1) must equal 1, b(2) can be 1 or 2, and b(3) can be 1, 2 or 3. This gives 3!=6 possible products: 1*1*1=1, 1*2*1=2, 1*1*2=2, 1*1*3=3, 1*2*2=4 and 1*2*3=6. Since 1*2*1=1*1*2, this process yields 5 distinct numbers, so a(3)=5.
		

Crossrefs

Cf. A000124, A027423, A110713, A347685 (first differences), A347686.

Programs

Mathematica

list[1] := {1};
list[n_] := list[n] = DeleteDuplicates[Flatten[Table[i*list[n - 1], {i, 1, n}]]];
a[n_] := a[n] = Length[list[n]]; Table[a[n], {n, 1, 10}]

PARI

a(n) = my(l = List()); forvec(x = vector(n, i, [1, i]), listput(l, prod(i = 1, n, x[i])), 1); listsort(l, 1); #l \\ David A. Corneth, Sep 18 2021

Python

def A345882set(n):
    if n == 1:
        return {1}
    else:
        s = A345882set(n-1)
        c = set(s)
        for x in s:
            for i in range(2,n+1):
                c.add(i*x)
        return c
def A345882(n): return len(A345882set(n)) # Chai Wah Wu, Sep 19 2021

Extensions

a(26)-a(28) from Chai Wah Wu, Sep 19 2021

a(29)-a(33) from Martin Ehrenstein, Sep 22 2021