\\ 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);