A295281 Number of complete strict tree-factorizations of n > 1.

1, 1, 0, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 4, 1, 0, 1, 1, 1, 3, 1, 1, 1, 1, 1, 4, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 9, 1, 1, 1, 0, 1, 4, 1, 1, 1, 4, 1, 6, 1, 1, 1, 1, 1, 4, 1, 1, 0, 1, 1, 9, 1, 1, 1, 1, 1, 9, 1

Offset: 2

Author

Gus Wiseman, Nov 19 2017

Keywords

• nonn

Comments

A strict tree-factorization (see A295279 for definition) is complete if its leaves are all prime numbers.

From Andrew Howroyd, Nov 18 2018: (Start)

a(n) depends only on the prime signature of n.

This sequence is very similar but not identical to the number of complete orderless identity tree-factorizations of n. The first difference is at n=900 (square of three primes). Here a(n) = 191 whereas the other sequence would have 197. (End)

Examples

			The a(72) = 6 complete strict tree-factorizations are: 2*3*(2*(2*3)), 2*(2*3*(2*3)), 2*(2*(3*(2*3))), 2*(3*(2*(2*3))), 3*(2*(2*(2*3))), (2*3)*(2*(2*3)).
		

Links

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

Crossrefs

Cf. A000311, A025475, A085971, A273873, A281113 A281118, A281119, A292505, A295279.

Programs

Mathematica

postfacs[n_]:=If[n<=1,{{}},Join@@Table[Map[Prepend[#,d]&,Select[postfacs[n/d],Min@@#>=d&]],{d,Rest[Divisors[n]]}]];
sftc[n_]:=Prepend[Join@@Function[fac,Tuples[sftc/@fac]]/@Select[postfacs[n],And[Length[#]>1,UnsameQ@@#]&],n];
Table[Length[Select[sftc[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, v[j]+=w[k]*v[j/k])); w[2..n]} \\ Andrew Howroyd, Nov 18 2018

Formula

a(product of n distinct primes) = A000311(n).

Positions of zeros are proper prime powers A025475. Positions of nonzero entries are A085971.