cp's OEIS Frontend

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

%I A099732 #10 May 26 2017 16:41:38
%S A099732 1,2,6,24,24,72,144,1152,1296,2304,6912,82944,82944,165888,497664,
%T A099732 7962624,15925248,47775744,191102976,191102976,573308928,1146617856,
%U A099732 13759414272,13759414272,27518828544,82556485632
%N A099732 Largest order of a solvable subgroup of the symmetric group S_n.
%C A099732 The Maple code uses a recurrence for this function.
%C A099732 Here is a faster algorithm for computing members of this sequence. Input: a positive integer, n.
%C A099732 Step 1. Write n in base 4. This yields a string of digits. Each digit is 0, 1, 2 or 3.
%C A099732 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.
%C A099732 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.
%C A099732 Step 4. Add the digits of the string. Call this sum S.
%C A099732 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.
%C A099732 Step 6. A099732(n)= P * 24^((n-S)/3).
%C A099732 Examples. n=412089:
%C A099732 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.
%C A099732 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.
%C A099732 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.
%C A099732 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.
%D A099732 J. Dixon and B. Mortimer: Permutation groups. Springer 1996, 360p. 3-540-94599-7. DM 84.
%F A099732 a(n) <= 24^((n-1)/3). Equality holds iff n is a power of 4.
%e A099732 a(n) = n! for n<=4 because for those values of n, S_n is solvable and is therefore its own largest solvable subgroup.
%e A099732 a(7)=144 because the largest solvable subgroups of S_7 are the intransitive ones which are isomorphic to S_4*S_3.
%p A099732 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;
%Y A099732 Cf. A000792.
%K A099732 nonn
%O A099732 1,2
%A A099732 _David L. Harden_, Nov 08 2004