A281119 Number of complete 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, 34, 1, 4, 1, 3, 1, 4, 1, 44, 1, 1, 3, 3, 1, 4, 1, 29, 5, 1, 1

Offset

2,7

Comments

A tree-factorization of n>=2 is either (case 1) the number n or (case 2) a sequence of two or more tree-factorizations, one of each part of a weakly increasing factorization of n into factors greater than 1. A complete (or total) tree-factorization is a tree-factorization whose leaves are all prime numbers.

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

Links

Michael De Vlieger, Table of n, a(n) for n = 2..10000

A. Knopfmacher, M. Mays, Ordered and Unordered Factorizations of Integers, The Mathematica Journal 10(1), 2006.

Formula

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

Example

The a(36)=12 complete tree-factorizations of 36 are:
(2(2(33))), (2(3(23))), (2(233)),   (3(2(23))),
(3(3(22))), (3(223)),   ((22)(33)), ((23)(23)),
(22(33)),   (23(23)),   (33(22)),   (2233).

Mathematica

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

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]+=w[k]^e*v[i]))); w[2..n]} \\ Andrew Howroyd, Nov 18 2018

Crossrefs

Cf. A000311, A001055, A063834, A196545, A262673, A273873, A281113, A281118.

Sequence in context: A316695 A316767 A292505 * A317176 A318812 A337066

Adjacent sequences: A281116 A281117 A281118 * A281120 A281121 A281122

Keyword

nonn

Author

Gus Wiseman, Jan 15 2017

Status

approved