|
|
A295279
|
|
Number of strict tree-factorizations of n.
|
|
12
|
|
|
1, 1, 1, 1, 1, 2, 1, 2, 1, 2, 1, 4, 1, 2, 2, 3, 1, 4, 1, 4, 2, 2, 1, 10, 1, 2, 2, 4, 1, 8, 1, 6, 2, 2, 2, 12, 1, 2, 2, 10, 1, 8, 1, 4, 4, 2, 1, 26, 1, 4, 2, 4, 1, 10, 2, 10, 2, 2, 1, 28, 1, 2, 4, 12, 2, 8, 1, 4, 2, 8, 1, 44, 1, 2, 4, 4, 2, 8, 1, 26, 3, 2, 1
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,6
|
|
COMMENTS
|
A strict tree-factorization of n is either (case 1) the number n itself or (case 2) a set of two or more strict tree-factorizations, one of each factor in a factorization of n into distinct factors greater than one.
a(n) depends only on the prime signature of n. - Andrew Howroyd, Nov 18 2018
|
|
LINKS
|
|
|
FORMULA
|
a(product of n distinct primes) = A005804(n).
Dirichlet g.f.: (Zeta(s) + Product_{n >= 2}(1 + a(n)/n^s))/2.
|
|
EXAMPLE
|
The a(30) = 8 strict tree-factorizations are: 30, (2*3*5), (2*15), (2*(3*5)), (3*10), (3*(2*5)), (5*6), (5*(2*3)).
The a(36) = 12 strict tree-factorizations are: 36, (2*3*6), (2*3*(2*3)), (2*18), (2*(2*9)), (2*(3*6)), (2*(3*(2*3))), (3*12), (3*(2*6)), (3*(2*(2*3))), (3*(3*4)), (4*9).
|
|
MATHEMATICA
|
sfs[n_]:=If[n<=1, {{}}, Join@@Table[Map[Prepend[#, d]&, Select[sfs[n/d], Min@@#>d&]], {d, Rest[Divisors[n]]}]];
sft[n_]:=1+Total[Function[fac, Times@@sft/@fac]/@Select[sfs[n], Length[#]>1&]];
Array[sft, 100]
|
|
PROG
|
(PARI) seq(n)={my(v=vector(n), w=vector(n)); w[1]=v[1]=1; for(k=2, n, w[k]=v[k]+1; forstep(j=n\k*k, k, -k, v[j]+=w[k]*v[j/k])); w} \\ Andrew Howroyd, Nov 18 2018
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|