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,16

Comments

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

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

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

Crossrefs

Cf. A000740, A000837, A001055, A007916, A018783(n) = a(2^n), A052409, A052410, A275870, A303386, A303431, A303547, A303552, A303709.

Sequence in context: A347438 A245196 A259362 * A365550 A188585 A294068

Adjacent sequences: A303550 A303551 A303552 * A303554 A303555 A303556

Keyword

nonn

Author

Gus Wiseman, Apr 26 2018

Extensions

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

Status

approved