cp's OEIS Frontend

A303709 Number of periodic factorizations of n using elements of A007916 (numbers that are not perfect powers).

%I A303709 #15 Dec 06 2018 16:33:22
%S A303709 1,0,0,1,0,0,0,1,1,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,0,1,0,0,0,0,1,0,0,
%T A303709 0,2,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,
%U A303709 0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0
%N A303709 Number of periodic factorizations of n using elements of A007916 (numbers that are not perfect powers).
%C A303709 A periodic factorization of n is a finite multiset of positive integers greater than 1 whose product is n and whose multiplicities have a common divisor greater than 1. Note that a factorization of a number that is not a perfect power (A007916) is always aperiodic (A303386), so the indices of nonzero entries of this sequence all lie at perfect powers (A001597).
%H A303709 Antti Karttunen, <a href="/A303709/b303709.txt">Table of n, a(n) for n = 1..100000</a>
%F A303709 a(n) <= A303553(n) <= A001055(n). - _Antti Karttunen_, Dec 06 2018
%e A303709 The a(900) = 5 periodic factorizations are (2*2*3*3*5*5), (2*2*15*15), (3*3*10*10), (5*5*6*6), (30*30).
%t A303709 radQ[n_]:=Or[n===1,GCD@@FactorInteger[n][[All,2]]===1];
%t A303709 facsr[n_]:=If[n<=1,{{}},Join@@Table[Map[Prepend[#,d]&,Select[facsr[n/d],Min@@#>=d&]],{d,Select[Rest[Divisors[n]],radQ]}]];
%t A303709 Table[Length[Select[facsr[n],GCD@@Length/@Split[#]!=1&]],{n,200}]
%o A303709 (PARI)
%o A303709 gcd_of_multiplicities(lista) = { my(u=length(lista)); if(u<2, u, my(g=0, pe = lista[1], j=1); for(i=2,u,if(lista[i]==pe, j++, g = gcd(j,g); j=1; pe = lista[i])); gcd(g,j)); }; \\ the supplied lista (newfacs) should be monotonic
%o A303709 A303709(n, m=n, facs=List([])) = if(1==n, (1!=gcd_of_multiplicities(facs)), my(s=0, newfacs); fordiv(n, d, if((d>1)&&(d<=m)&&!ispower(d), newfacs = List(facs); listput(newfacs,d); s += A303709(n/d, d, newfacs))); (s)); \\ _Antti Karttunen_, Dec 06 2018
%Y A303709 Cf. A000740, A000837, A001055, A001597, A007716, A007916, A052409, A052410, A281116, A303547, A303552, A303553, A303386, A303707, A303708, A303710.
%K A303709 nonn
%O A303709 1,36
%A A303709 _Gus Wiseman_, Apr 29 2018
%E A303709 Changed a(1) to 1 by _Gus Wiseman_, Dec 06 2018