A295279 - OEIS

%I #13 Nov 19 2018 03:11:37

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

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

%U 8,1,4,2,8,1,44,1,2,4,4,2,8,1,26,3,2,1

%N Number of strict tree-factorizations of n.

%C 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.

%C a(n) depends only on the prime signature of n. - _Andrew Howroyd_, Nov 18 2018

%H Andrew Howroyd, <a href="/A295279/b295279.txt">Table of n, a(n) for n = 1..10000</a>

%F a(product of n distinct primes) = A005804(n).

%F a(prime^n) = A273873(n).

%F Dirichlet g.f.: (Zeta(s) + Product_{n >= 2}(1 + a(n)/n^s))/2.

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

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

%t sfs[n_]:=If[n<=1,{{}},Join@@Table[Map[Prepend[#,d]&,Select[sfs[n/d],Min@@#>d&]],{d,Rest[Divisors[n]]}]];

%t sft[n_]:=1+Total[Function[fac,Times@@sft/@fac]/@Select[sfs[n],Length[#]>1&]];

%t Array[sft,100]

%o (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

%Y Cf. A005804, A045778, A273873, A281113 A281118, A292504, A294786, A295281.

%K nonn

%O 1,6

%A _Gus Wiseman_, Nov 19 2017