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

%I #18 Dec 30 2018 00:04:11

%S 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,

%T 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,

%U 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

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

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

%C Terms in this sequence only depend on the prime signature of n. - _David A. Corneth_, Dec 26 2018

%H Antti Karttunen, <a href="/A322453/b322453.txt">Table of n, a(n) for n = 1..16384</a>

%H Antti Karttunen, <a href="/A322453/a322453.txt">Data supplement: n, a(n) computed for n = 1..100000</a>

%H <a href="/index/Eu#epf">Index entries for sequences computed from exponents in factorization of n</a>

%e The a(144) = 13 factorizations:

%e (144),

%e (4*36), (9*16),

%e (2*2*36), (2*8*9), (3*3*16), (4*4*9),

%e (2*2*4*9), (2*3*3*8), (3*3*4*4),

%e (2*2*2*2*9), (2*2*3*3*4),

%e (2*2*2*2*3*3).

%t perpowQ[n_]:=GCD@@FactorInteger[n][[All,2]]>1;

%t pfacs[n_]:=If[n<=1,{{}},Join@@Table[Map[Prepend[#,d]&,Select[pfacs[n/d],Min@@#>=d&]],{d,Select[Rest[Divisors[n]],Or[PrimeQ[#],perpowQ[#]]&]}]];

%t Table[Length[pfacs[n]],{n,100}]

%o (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

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

%K nonn

%O 1,4

%A _Gus Wiseman_, Dec 09 2018

%E More terms from _Antti Karttunen_, Dec 24 2018