A303553 Number of periodic factorizations of n > 1 into positive factors greater than 1; a(1) = 1 by convention.

1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 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, 4, 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, 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, 1

Offset: 1

Author

Gus Wiseman, Apr 26 2018

Keywords

• nonn

Comments

A multiset is periodic if its multiplicities have a common divisor greater than 1.

Examples

			The a(64)  = 4 periodic factorizations are (2*2*2*2*2*2), (2*2*4*4), (4*4*4), (8*8).
The a(144) = 4 periodic factorizations are (2*2*2*2*3*3), (2*2*6*6), (3*3*4*4), (12*12).
The a(256) = 5 periodic factorizations are (2*2*2*2*2*2*2*2), (2*2*2*2*4*4), (2*2*8*8), (4*4*4*4), (16*16).
The a(576) = 7 periodic factorizations are (2*2*2*2*2*2*3*3), (2*2*2*2*6*6), (2*2*3*3*4*4), (2*2*12*12), (3*3*8*8), (4*4*6*6), (24*24).
		

Links

• Antti Karttunen, Table of n, a(n) for n = 1..20736
• 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. A000740, A000837, A001055, A007916, A018783(n) = a(2^n), A052409, A052410, A275870, A303386, A303431, A303547, A303552, A303709.

Programs

Mathematica

facs[n_]:=If[n<=1,{{}},Join@@Table[Map[Prepend[#,d]&,Select[facs[n/d],Min@@#>=d&]],{d,Rest[Divisors[n]]}]];
Table[Length[Select[facs[n],GCD@@Length/@Split[#]>1&]],{n,2,100}]

PARI

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
A303553(n, m=n, facs=List([])) = if(1==n, (gcd_of_multiplicities(facs)!=1), my(s=0, newfacs); fordiv(n, d, if((d>1)&&(d<=m), newfacs = List(facs); listput(newfacs,d); s += A303553(n/d, d, newfacs))); (s)); \\ Antti Karttunen, Dec 06 2018

Formula

a(n) >= A303709(n). - Antti Karttunen, Dec 06 2018

Extensions

a(1) = 1 prepended by Antti Karttunen, Dec 06 2018