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,2

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

Links

Table of n, a(n) for n=1..33.

Example

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.

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}]

Prog

(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

Crossrefs

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

Sequence in context: A176637 A272675 A059075 * A121134 A144959 A131347

Adjacent sequences: A345879 A345880 A345881 * A345883 A345884 A345885

Keyword

nonn,nice

Author

David Galvin, Sep 16 2021

Extensions

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

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

Status

approved