A292505 Number of complete orderless tree-factorizations of n >= 2.

1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 3, 1, 1, 1, 5, 1, 3, 1, 3, 1, 1, 1, 9, 1, 1, 2, 3, 1, 4, 1, 12, 1, 1, 1, 12, 1, 1, 1, 9, 1, 4, 1, 3, 3, 1, 1, 29, 1, 3, 1, 3, 1, 9, 1, 9, 1, 1, 1, 17, 1, 1, 3, 33, 1, 4, 1, 3, 1, 4, 1, 44, 1, 1, 3, 3, 1, 4, 1, 29, 5, 1, 1, 17, 1

Offset: 2

Author

Gus Wiseman, Sep 17 2017

Keywords

• nonn

Comments

An orderless tree-factorization (see A292504 for definition) is complete if all leaves are prime numbers. This sequence first differs from A281119 at a(64)=33.

a(n) depends only on the prime signature of n. - Andrew Howroyd, Nov 18 2018

Examples

			The a(60)=17 complete orderless tree-factorizations are: (2(2(35))), (2(3(25))), (2(5(23))), (2(235)), (3(2(25))), (3(5(22))), (3(225)), (5(2(23))), (5(3(22))), (5(223)), ((22)(35)), ((23)(25)), (22(35)), (23(25)), (25(23)), (35(22)), (2235).
		

Links

• Andrew Howroyd, Table of n, a(n) for n = 2..10000

Crossrefs

Cf. A000311, A000669, A001055, A050336, A281119, A292504.

Programs

Mathematica

postfacs[n_]:=If[n<=1,{{}},Join@@Table[Map[Prepend[#,d]&,Select[postfacs[n/d],Min@@#>=d&]],{d,Rest[Divisors[n]]}]];
oltfacs[n_]:=If[n<=1,{{}},Prepend[Union@@Function[q,Sort/@Tuples[oltfacs/@q]]/@DeleteCases[postfacs[n],{n}],n]];
Table[Length[Select[oltfacs[n],FreeQ[#,_Integer?(!PrimeQ[#]&)]&]],{n,2,100}]

PARI

seq(n)={my(v=vector(n), w=vector(n)); v[1]=1; for(k=2, n, w[k]=v[k]+isprime(k); forstep(j=n\k*k, k, -k, my(i=j, e=0); while(i%k==0, i/=k; e++; v[j]+=binomial(e+w[k]-1, e)*v[i]))); w[2..n]} \\ Andrew Howroyd, Nov 18 2018

Formula

a(p^n) = A000669(n) for prime p. - Andrew Howroyd, Nov 18 2018