A316789 Number of same-tree-factorizations of n.

1, 1, 1, 2, 1, 1, 1, 2, 2, 1, 1, 1, 1, 1, 1, 6, 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, 14, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 6, 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). A same-tree-factorization of n is either (case 1) the number n itself or (case 2) a finite sequence of two or more 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} a(x)^y.

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

Example

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

Mathematica

a[n_]:=1+Sum[a[n^(1/d)]^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, a(z^(e/d))^d)))} \\ Andrew Howroyd, Nov 18 2018

Crossrefs

Cf. A001055, A001597, A001678, A003238, A007916, A052409, A052410, A067824, A089723, A281118, A281145, A294336, A316790.

Sequence in context: A326028 A294338 A316790 * A319661 A320015 A342956

Adjacent sequences: A316786 A316787 A316788 * A316790 A316791 A316792

Keyword

nonn

Author

Gus Wiseman, Jul 14 2018

Status

approved