login
A303553
Number of periodic factorizations of n > 1 into positive factors greater than 1; a(1) = 1 by convention.
3
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,16
COMMENTS
A multiset is periodic if its multiplicities have a common divisor greater than 1.
FORMULA
a(n) >= A303709(n). - Antti Karttunen, Dec 06 2018
EXAMPLE
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).
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}]
PROG
(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
KEYWORD
nonn
AUTHOR
Gus Wiseman, Apr 26 2018
EXTENSIONS
a(1) = 1 prepended by Antti Karttunen, Dec 06 2018
STATUS
approved