\\ A218958: Number of maximal cyclic subgroups of the symmetric group, counting conjugates as distinct. \\ A218963: Number of maximal cyclic subgroups of the alternating group, counting conjugates as distinct. \\ PartPoly: converts a partition as a vector of part sizes into a polynomial. This is for convenience. \\ Example: PartPoly([1,1,3]) => x^3 + 2*x PartPoly(v)={sum(i=1, #v, x^v[i])} \\ Determines the number of permutations with a given type. A type is described by a polynomial. \\ Example: PermCount(x^2 + 2*x) => 6 PermCount(q) = {subst(deriv(q),x,1)!/prod(i=1, poldegree(q), my(c=polcoeff(q,i)); i^c*c!)} \\ Determines the type of a permutation with a given type raised by an exponent. \\ Example: Raise(x^4, 2) => 2*x^2 Raise(q, e) = {sum(i=1, poldegree(q), my(c=polcoeff(q,i)); if(c, my(d=gcd(i,e)); c*d*x^(i/d)))} \\ Builds the set of permutation types that are not maximal \\ Example: Exclusions(4, v->1) => [4*x, 2*x^2] Exclusions(n, filter) = { my(M=Map()); forpart(v=n, if(filter(v), my(q=PartPoly(v)); for(i=1, poldegree(q), if(polcoeff(q,i), my(f=factor(i)[,1]); for(j=1, #f, mapput(M, Raise(q, f[j]), 1))))) ); if(#M, Set(Mat(M)[,1]), Set()) } \\ Determines the number of maximal cyclic subgroups \\ The algorithm works by enumerating over all partitions of n each of which \\ describe a set of permutations with the same cyclic structure. Non maximal \\ cycles are eliminated by constructing the set of sub-types for each cycle type. MaximalCyclicSubgroupCount(n, filter) = { my(XS=Exclusions(n, filter)); my(s=0); forpart(v=n, if (filter(v), my(q=PartPoly(v)); if(!setsearch(XS, q), s += PermCount(q)/eulerphi(lcm(Vec(v))))); ); s } \\ symmetric group sequence A218958(n)=MaximalCyclicSubgroupCount(n, v->1); \\ alternating group sequence A218963(n)=MaximalCyclicSubgroupCount(n, v->sum(i=1, #v, v[i]-1)%2==0);