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

Author

Gus Wiseman, Jul 14 2018

Keywords

• nonn

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

Examples

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

Links

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

Crossrefs

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

Programs

Mathematica

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

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

Formula

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

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