[seqfan] Re: Symmetric group S_n as product of at most A225788(n) cyclic subgroups

[Richard J. Mathar]

On a mximum bound of the shortest cyclic subgroup factorization in
http://list.seqfan.eu/pipermail/seqfan/2013-May/011212.html :

The order of the symmetric group is n!. If we whish to write
this as a product of cyclic subgroups, with subgroups of order
m1, m2, m3 etc, the product m1*m2*.. should be n! .
The number of factorizations of n! are counted in A076716. Since
the order of any cyclic subgroup of S_n is at most
A000792(n) as stated in the Bercov-Moser paper quoted in A225788,
we could restrict the factorizations of n! to those with maximum
factor A000792(n). If I take these subsets of factorizations of n!,
then select the factorization with the smallest number of factors,
I get the following list of n and smallest number of factors:
1, 1
2, 1
3, 2
4, 3
5, 3
6, 4
7, 4
8, 4
9, 5
10, 5
11, 5

This does not proof much, because the test that any of
these products of cyclic subgroups acutally equals (up to isomorphism) S(n)
is missing.  So these are only lower limits.

Examples:
n= 1: 1! = 1
n= 2: 2! = 2
n= 3: 3! = 2*3, 2 factors
n= 4: 4! = 4*3*2 = 3*2*2*2, mininum 3 factors.
n= 5: 5! = 6*5*4 = 6*5*2*2 = 5*4*3*2 = 5*3*2*2*2,  minimum 3 factors.

Repeating the same calculation but selecting the factorization with
the maximum number of factors:
1, 1
2, 1
3, 2
4, 4
5, 5
6, 7
7, 8
8, 11
9, 13
10, 15
11, 16


# List of factorizations of n, counted in A001055, listed in A162247.
Lprod := proc(n,nma)
    local L,s,d,r ;
    if isprime(n) then
        if n <= nma then
            return [n] ;
        else
            return [] ;
        end if;
    elif nma = 1 then
        return [] ;
    else
        L := [] ;
        s := convert(numtheory[divisors](n),list) ;
        # recursive with priority to the largest factors
        for i from 1 to nops(s) do
            d := op(-i,s) ;
            if d <= nma then
                r := n/d ;
                if r > 1 then
                    re := procname(r,d) ;
                    for l in re do
                        L := [op(L),[d,op(l)]] ;
                    end do;
                else
                    L := [op(L),[d]] ;
                end if;
            end if;
        end do;
        return L ;
    end if;
end proc:
A001055 := proc(n)
    nops(Lprod(n,n)) ;
end proc:
A076716 := proc(n)
    A001055(n!) ;
end proc:
A000792 := proc(n)
    m := floor(n/3) ;
    if n mod 3 = 0 then
        3^m ;
    elif n mod 3 = 1 then
        4*3^(m-1) ;
    else
        2*3^m ;
    end if;
    floor(%) ;
end proc:
A := proc(n)
    local facts,a,f ;
    a := n! ;
    facts := Lprod(n!,A000792(n)) ;
    for f in facts  do
        a := min(a,nops(f)) ;
    end do:
    a ;
end proc:
for n from 1 do
    print(n,A(n)) ;
end do: