cp's OEIS Frontend

A000198 Largest order of automorphism group of a tournament with n nodes.

%I A000198 M2280 N0902 #59 Jul 01 2024 14:55:37
%S A000198 1,1,3,3,5,9,21,21,81,81,81,243,243,441,1215,1701,1701,6561,6561,6561,
%T A000198 45927,45927,45927,137781,137781,229635,1594323,1594323,1594323,
%U A000198 4782969,4782969,7971615,14348907,33480783,33480783,129140163,129140163,129140163
%N A000198 Largest order of automorphism group of a tournament with n nodes.
%D A000198 J. W. Moon, Topics on Tournaments. Holt, NY, 1968, p. 81.
%D A000198 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D A000198 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A000198 Joseph Myers, <a href="/A000198/b000198.txt">Table of n, a(n) for n = 1..1000</a>
%H A000198 B. Alspach, <a href="http://dx.doi.org/10.4153/CMB-1968-078-3">A combinatorial proof of a conjecture of Goldberg and Moon</a>, Canad. Math. Bull. 11 (1968), 655-661.
%H A000198 B. Alspach, <a href="https://doi.org/10.4153/CMB-1970-061-7">On point-symmetric tournaments</a>, Canad. Math. Bull., 13 (1970), 317-323. [<a href="/A002086/a002086.pdf">Annotated copy</a>] See g(n) as defined on page 317 (NOT on page 322).
%H A000198 B. Alspach and J. L. Berggren, <a href="http://dx.doi.org/10.4153/CMB-1973-003-7">On the determination of the maximum order of the group of a tournament</a>, Canad. Math. Bull 16 (1973), 11-14.
%H A000198 J. D. Dixon, <a href="http://dx.doi.org/10.4153/CMB-1967-048-9">The maximum order of the group of a tournament</a>, Canad. Math. Bull. 10 (1967), 503-505.
%H A000198 <a href="/index/To#tournament">Index entries for sequences related to tournaments</a>
%F A000198 a(3^k) = 3^((3^k - 1)/2), a(5*3^k) = 5*3^((5*3^k - 5)/2), a(7*3^k) = 7*3^((7*3^k - 5)/2), and, for all other n, a(n) = max(a(i)a(n-i)) where the maximum is taken over 1 <= i <= n-1 (from Alspach and Berggren (1973) Theorem 4).
%F A000198 a(3r) = (3^r)a(r), a(n) = a(n-1) for n = 1, 2 or 4 mod 9, a(9k+8) = max(a(9k+7), a(5)a(9k+3)), a(9k+5) = max(a(2)a(9k+3), a(5)a(9k), a(7)a(9k-2)), a(9k+7) = a(7)a(9k) (from Alspach and Berggren (1973) Theorem 5).
%p A000198 a:= proc(n) local t, r; t:= irem(n, 9);
%p A000198    `if`(3^ilog[3](n)=n, 3^((3^ilog[3](n)-1)/2),
%p A000198    `if`(irem(n, 5, 'r')=0 and 3^ilog[3](r)=r, 5*3^((5*3^ilog[3](r)-5)/2),
%p A000198    `if`(irem(n, 7, 'r')=0 and 3^ilog[3](r)=r, 7*3^((7*3^ilog[3](r)-5)/2),
%p A000198    `if`(irem(n, 3, 'r')=0, 3^r*a(r),
%p A000198    `if`(t in {1, 2, 4}, a(n-1),
%p A000198    `if`(t = 8, max(a(n-1), a(5)*a(n-5)),
%p A000198    `if`(t = 5, max(a(2)*a(n-2), a(5)*a(n-5), a(7)*a(n-7)),
%p A000198         a(7)*a(n-7) )))))))
%p A000198     end:
%p A000198 seq(a(n), n=1..50);  # _Alois P. Heinz_, Jun 29 2012
%t A000198 a[n_] := a[n] = With[{t = Mod[n, 9]}, Which[ IntegerQ[Log[3, n]], 3^((1/2)*(n-1)),{q, r} = QuotientRemainder[n, 5]; r == 0 && IntegerQ[Log[3, q]], 5*3^((1/2)*(n-5)),{q, r} = QuotientRemainder[n, 7];r == 0 && IntegerQ[Log[3, q]], 7*3^((1/2)*(n-5)), {q, r} = QuotientRemainder[n, 3]; r == 0, 3^q*a[q],MemberQ[{1, 2, 4}, t], a[n-1],t == 8, Max[a[n-1], a[5]*a[n-5]], t == 5, Max[a[2]*a[n-2],a[5]*a[n-5], a[7]*a[n-7]],True, a[7]*a[n-7]]]; Table[a[n], {n, 1, 38}] (* _Jean-François Alcover_, Nov 12 2012, after _Alois P. Heinz_ *)
%o A000198 (Python)
%o A000198 from functools import lru_cache
%o A000198 @lru_cache(maxsize=None)
%o A000198 def A000198(n):
%o A000198     if n <= 7: return (1, 1, 3, 3, 5, 9, 21)[n-1]
%o A000198     if (r:=n%9) in {0,3,6}:
%o A000198         return 3**(m:=n//3)*A000198(m)
%o A000198     elif r in {1,2,4}:
%o A000198         return A000198(n-1)
%o A000198     elif r == 5:
%o A000198         return max(A000198(n-2),5*A000198(n-5),21*A000198(n-7))
%o A000198     elif r == 7:
%o A000198         return 21*A000198(n-7)
%o A000198     elif r == 8:
%o A000198         return max(A000198(n-1),5*A000198(n-5)) # _Chai Wah Wu_, Jul 01 2024
%Y A000198 Cf. A000568, A374164.
%K A000198 nonn,nice
%O A000198 1,3
%A A000198 _N. J. A. Sloane_
%E A000198 Edited and extended by _Joseph Myers_, Jun 28 2012