login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A099732 Largest order of a solvable subgroup of the symmetric group S_n. 2
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 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,2

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.

REFERENCES

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

LINKS

Table of n, a(n) for n=1..26.

FORMULA

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

EXAMPLE

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.

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;

CROSSREFS

Cf. A000792.

Sequence in context: A124900 A068819 A060068 * A118381 A123145 A232981

Adjacent sequences:  A099729 A099730 A099731 * A099733 A099734 A099735

KEYWORD

nonn

AUTHOR

David L. Harden, Nov 08 2004

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 15 19:24 EDT 2018. Contains 316237 sequences. (Running on oeis4.)