A322453 Number of factorizations of n into factors > 1 using only primes and perfect powers.

1, 1, 1, 2, 1, 1, 1, 3, 2, 1, 1, 2, 1, 1, 1, 5, 1, 2, 1, 2, 1, 1, 1, 3, 2, 1, 3, 2, 1, 1, 1, 7, 1, 1, 1, 5, 1, 1, 1, 3, 1, 1, 1, 2, 2, 1, 1, 5, 2, 2, 1, 2, 1, 3, 1, 3, 1, 1, 1, 2, 1, 1, 2, 11, 1, 1, 1, 2, 1, 1, 1, 7, 1, 1, 2, 2, 1, 1, 1, 5, 5, 1, 1, 2, 1, 1, 1, 3, 1, 2, 1, 2, 1, 1, 1, 7, 1, 2, 2, 5, 1, 1, 1, 3, 1

Offset

1,4

Comments

First differs from A000688 at a(36) = 5, A000688(36) = 4.

Terms in this sequence only depend on the prime signature of n. - David A. Corneth, Dec 26 2018

Links

Antti Karttunen, Table of n, a(n) for n = 1..16384

Antti Karttunen, Data supplement: n, a(n) computed for n = 1..100000

Index entries for sequences computed from exponents in factorization of n

Example

The a(144) = 13 factorizations:
  (144),
  (4*36), (9*16),
  (2*2*36), (2*8*9), (3*3*16), (4*4*9),
  (2*2*4*9), (2*3*3*8), (3*3*4*4),
  (2*2*2*2*9), (2*2*3*3*4),
  (2*2*2*2*3*3).

Mathematica

perpowQ[n_]:=GCD@@FactorInteger[n][[All, 2]]>1;
pfacs[n_]:=If[n<=1, {{}}, Join@@Table[Map[Prepend[#, d]&, Select[pfacs[n/d], Min@@#>=d&]], {d, Select[Rest[Divisors[n]], Or[PrimeQ[#], perpowQ[#]]&]}]];
Table[Length[pfacs[n]], {n, 100}]

Prog

(PARI) A322453(n, m=n) = if(1==n, 1, my(s=0); fordiv(n, d, if((d>1)&&(d<=m)&&(ispower(d)||isprime(d)), s += A322453(n/d, d))); (s)); \\ Antti Karttunen, Dec 26 2018

Crossrefs

Cf. A000688, A000961, A001055, A001597, A025487, A050336, A284696, A294068, A320322, A322452.

Sequence in context: A336736 A000688 A295879 * A327012 A351219 A328855

Adjacent sequences: A322450 A322451 A322452 * A322454 A322455 A322456

Keyword

nonn

Author

Gus Wiseman, Dec 09 2018

Extensions

More terms from Antti Karttunen, Dec 24 2018

Status

approved