A301829 Number of ways to choose a nonempty submultiset of a factorization of n into factors greater than one.

0, 1, 1, 3, 1, 4, 1, 7, 3, 4, 1, 12, 1, 4, 4, 15, 1, 12, 1, 12, 4, 4, 1, 29, 3, 4, 7, 12, 1, 17, 1, 29, 4, 4, 4, 37, 1, 4, 4, 29, 1, 17, 1, 12, 12, 4, 1, 64, 3, 12, 4, 12, 1, 29, 4, 29, 4, 4, 1, 53, 1, 4, 12, 54, 4, 17, 1, 12, 4, 17, 1, 92, 1, 4, 12, 12, 4, 17

Offset: 1

Author

Gus Wiseman, Mar 27 2018

Keywords

• nonn

Examples

			The a(12) = 12 submultisets ("<" means subset or equal):
(2)<(2*2*3), (3)<(2*2*3), (2*2)<(2*2*3), (2*3)<(2*2*3), (2*2*3)<(2*2*3),
(2)<(2*6), (6)<(2*6), (2*6)<(2*6),
(3)<(3*4), (4)<(3*4), (3*4)<(3*4),
(12)<(12).
		

Crossrefs

Cf. A000712, A001055, A001222, A001405, A122768, A276024, A281113, A284640, A295632, A299701, A299702, A299729, A301830.

Programs

Mathematica

facs[n_]:=If[n<=1,{{}},Join@@Table[Map[Prepend[#,d]&,Select[facs[n/d],Min@@#>=d&]],{d,Rest[Divisors[n]]}]];
Table[Sum[Length[facs[d]]*Length[facs[n/d]],{d,Rest[Divisors[n]]}],{n,100}]

Formula

a(n) = Sum_{d|n, d>1} f(d) * f(n/d) where f(n) = A001055(n) is the number of factorizations of n into factors greater than 1.