login
Number of multisets that can be obtained by choosing a divisor of each positive integer from 1 to n.
9

%I #21 Aug 08 2022 14:21:11

%S 1,1,2,4,10,20,58,116,320,772,2170,4340,14112,28224,78120,212004,

%T 612232,1224464,3873760,7747520,24224608,64595088,175452168,350904336

%N Number of multisets that can be obtained by choosing a divisor of each positive integer from 1 to n.

%F a(n) = A355733(A070826(n)).

%F a(p) = 2*a(p-1) for p prime. - _Michael S. Branicky_, Aug 03 2022

%e The a(0) = 1 through a(4) = 10 multisets:

%e {} {1} {1,1} {1,1,1} {1,1,1,1}

%e {1,2} {1,1,2} {1,1,1,2}

%e {1,1,3} {1,1,1,3}

%e {1,2,3} {1,1,1,4}

%e {1,1,2,2}

%e {1,1,2,3}

%e {1,1,2,4}

%e {1,1,3,4}

%e {1,2,2,3}

%e {1,2,3,4}

%t Table[Length[Union[Sort/@Tuples[Divisors/@Range[n]]]],{n,0,10}]

%o (Python)

%o from sympy import divisors

%o from itertools import count, islice

%o def agen():

%o s = {tuple()}

%o for n in count(1):

%o yield len(s)

%o s = set(tuple(sorted(t+(d,))) for t in s for d in divisors(n))

%o print(list(islice(agen(), 16))) # _Michael S. Branicky_, Aug 03 2022

%Y The sum of the same integers is A000096.

%Y The product of the same integers is A000142, Heinz number A070826.

%Y Counting sequences instead of multisets gives A066843.

%Y The integers themselves are the rows of A131818 (shifted).

%Y For prime indices we have A355733, only prime factors A355744.

%Y For prime factors instead of divisors we have A355746, factors A355537.

%Y A000005 counts divisors.

%Y A000040 lists the prime numbers.

%Y A001221 counts distinct prime factors, with sum A001414.

%Y A001222 counts prime factors with multiplicity.

%Y Cf. A000720, A002110, A006218, A076610, A327486, A355538, A355731, A355737, A355741, A355745.

%K nonn,more

%O 0,3

%A _Gus Wiseman_, Jul 20 2022

%E a(15)-a(21) from _Michael S. Branicky_, Aug 03 2022

%E a(22)-a(23) from _Michael S. Branicky_, Aug 08 2022