A099732 Largest order of a solvable subgroup of the symmetric group S_n.

1, 2, 6, 24, 24, 72, 144, 1152, 1296, 2304, 6912, 82944, 82944, 165888, 497664, 7962624, 15925248, 47775744, 191102976, 191102976, 573308928, 1146617856, 13759414272, 13759414272, 27518828544, 82556485632

Offset: 1

Author

David L. Harden, Nov 08 2004

Keywords

• nonn

Comments

The Maple code uses a recurrence for this function.

Here is a faster algorithm for computing members of this sequence. Input: a positive integer, n.

Step 1. Write n in base 4. This yields a string of digits. Each digit is 0, 1, 2 or 3.

Step 2. Make a pass through the string and replace every occurrence of "12" with "6". Now the string is a string of 0's, 1's, 2s, 3s and 6s.

Step 3. Make a pass through the string and replace every occurrence of "21" by "9". Now the string is a string of 0's, 1's, 2s 3s, 6s and 9s.

Step 4. Add the digits of the string. Call this sum S.

Step 5. Compute the product of f(d) over all digits d of the string, where f(0)=1 and f(d)= A099732(d) for d>0. As a table, these values are f(0)=1, f(1)=1, f(2)=2, f(3)=6, f(6)=72 and f(9)=1296. Call this product P.

Step 6. A099732(n)= P * 24^((n-S)/3).

Examples. n=412089:

Step 1. n = 1210212321 in base 4. Step 2. The new string is 61062321. Step 3. The new string is 6106239. Step 4. S = 6+1+0+6+2+3+9= 27. Step 5. P = 72*1*1*72*2*6*1296=80621568. Step 6. A099732(412089)=80621568 * 24^((412089-27)/3) = 80621568 * 24^(412062/3) = 80621568 * 24^137354.

n=25: Step 1. n=121 in base 4. Step 2. The new string is 61. Step 3. The new string is still 61, since there are no "21"s in 61. Step 4. S= 6+1 =7. Step 5. P= 72*1 = 72. Step 6. A099732(25) = 72 * 24^((25-7)/3) = 72 * 24^6.

n=37: Step 1. n=211 in base 4. Step 2. The new string is still 211, since there are no "12"s in "211". Step 3. The new string is 91. Step 4. S= 9+1 = 10. Step 5. P= 1296*1 = 1296. Step 6. A099732(37) = 1296 * 24^((37-10)/3) = 1296 * 24^9.

It is important that Step 2 be done before Step 3; indeed, proving that doing any of Step 3 before all of Step 2 is accomplished cannot result in a larger value (though it can result in a smaller value, or the same value if there are no "12"-"21" conflicts) is part of the proof of the correctness of this algorithm.

Examples

			a(n) = n! for n<=4 because for those values of n, S_n is solvable and is therefore its own largest solvable subgroup.
a(7)=144 because the largest solvable subgroups of S_7 are the intransitive ones which are isomorphic to S_4*S_3.
		

References

• J. Dixon and B. Mortimer: Permutation groups. Springer 1996, 360p. 3-540-94599-7. DM 84.

Crossrefs

Cf. A000792.

Programs

Maple

largsolv := proc(n :: posint) local valtable,curmax,i,j,k,g; valtable:=Array(1..n); if n<=4 return factorial(n); end if; for i from 1 to 4 do valtable[i]:=factorial(i); end do; for j from 5 to n do curmax:=1; for i from 1 to floor(j/2) do curmax:=max(curmax,valtable[i]*valtable[j-i]) end do; for k from 2 to tau(j)-1 do g:=divisors(j)[k]; curmax:=max(curmax,valtable[g]^(j/g)*valtable[j/g]); end do; valtable[j]:=curmax; end do; return valtable[n]; end proc;

Formula

a(n) <= 24^((n-1)/3). Equality holds iff n is a power of 4.