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

Author

Gus Wiseman, Dec 09 2018

Keywords

• nonn

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

Examples

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

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

Crossrefs

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

Programs

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

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

Extensions

More terms from Antti Karttunen, Dec 24 2018