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

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

Links

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

Formula

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

Example

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).

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

Prog

(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

Crossrefs

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

Sequence in context: A199515 A316695 A316767 * A281119 A317176 A318812

Adjacent sequences: A292502 A292503 A292504 * A292506 A292507 A292508

Keyword

nonn

Author

Gus Wiseman, Sep 17 2017

Status

approved