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

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)

Links

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

Formula

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

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

Example

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

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

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

Crossrefs

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

Sequence in context: A290455 A290460 A334429 * A256461 A174699 A213027

Adjacent sequences: A295278 A295279 A295280 * A295282 A295283 A295284

Keyword

nonn

Author

Gus Wiseman, Nov 19 2017

Status

approved