A316790 Number of orderless same-tree-factorizations of n.

1, 1, 1, 2, 1, 1, 1, 2, 2, 1, 1, 1, 1, 1, 1, 5, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 2, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 9, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 5, 1, 1, 1, 1, 1, 1

Offset

1,4

Comments

A constant factorization of n is a finite nonempty constant multiset of positive integers greater than 1 with product n. Constant factorizations correspond to perfect divisors (A089723). An orderless same-tree-factorization of n is either (case 1) the number n itself or (case 2) a finite multiset of two or more orderless same-tree-factorizations, one of each factor in a constant factorization of n.

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

Links

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

Formula

a(n) = 1 + Sum_{n = x^y, y > 1} binomial(a(x) + y - 1, y).

a(2^n) = A289078(n).

Example

The a(64) = 9 orderless same-tree-factorizations:
  64
  (8*8)
  (4*4*4)
  (4*4*(2*2))
  (8*(2*2*2))
  (2*2*2*2*2*2)
  (4*(2*2)*(2*2))
  ((2*2*2)*(2*2*2))
  ((2*2)*(2*2)*(2*2))

Mathematica

a[n_]:=1+Sum[Binomial[a[n^(1/d)]+d-1, d], {d, Rest[Divisors[GCD@@FactorInteger[n][[All, 2]]]]}]
Array[a, 100]

Prog

(PARI) a(n)={my(z, e=ispower(n, , &z)); 1 + if(e, sumdiv(e, d, if(d>1, binomial(a(z^(e/d)) + d - 1, d))))} \\ Andrew Howroyd, Nov 18 2018

Crossrefs

Cf. A001055, A001597, A003238, A052409, A052410, A067824, A089723, A281118, A281145, A289078, A292504, A316789.

Sequence in context: A326647 A326028 A294338 * A316789 A319661 A320015

Adjacent sequences: A316787 A316788 A316789 * A316791 A316792 A316793

Keyword

nonn

Author

Gus Wiseman, Jul 14 2018

Status

approved