[GAP Forum] A permutation group with huge finite orbits

[Stefan Kohl]

Dear Jason, dear Forum,

> The length of the orbit is 47610700792.
>
> Using C with GMP and OpenMP, the result can be found in roughly 3 days on a
> new core i7 machine. It is possible to compute the orbit in both directions
> at the same time on separate cores, stopping when they meet somewhere in
> the orbit. The maximum length of a digit in the orbit is 76,785.
>
> You can find the C code here: http://www.jasonbhill.com/residue-collatz/

Thanks. -- Great!!

Just two remarks:

1. In your C program you apply the mappings a, b and c separately.
   It is possible to reduce the number of arithmetic operations by
   evaluating the product g := abc and applying it as one mapping.
   We have

gap> LoadPackage("rcwa");
gap> a := ClassTransposition(0,2,1,2);;
gap> b := ClassTransposition(0,5,4,5);;
gap> c := ClassTransposition(1,4,0,6);;
gap> g := a*b*c;;
gap> Display(g);

Rcwa permutation of Z with modulus 60

        /
        | n-1       if n in 3(30) U 9(30) U 17(30) U 23(30) U 27(30) U 29(30)
        | 3n/2      if n in 0(20) U 12(20) U 16(20)
        | n+1       if n in 2(20) U 6(20) U 10(20)
        | (2n+1)/3  if n in 7(30) U 13(30) U 19(30)
        | n+3       if n in 1(30) U 11(30)
        | n-5       if n in 15(30) U 25(30)
 n |-> <  (3n+12)/2 if n in 4(20)
        | (3n-12)/2 if n in 8(20)
        | n+5       if n in 14(20)
        | n-3       if n in 18(20)
        | (2n-7)/3  if n in 5(30)
        | (2n+9)/3  if n in 21(30)
        |
        \

2. There does not seem to be an obvious reason why the cycles of abc always
   traverse entire orbits of G = <a,b,c>, and at least on a first glance
   one doesn't see a pattern in which order a cycle of abc traverses an orbit
   of G. Nevertheless, computational evidence supports so far the assumption
   that cycles of abc correspond to orbits of <a,b,c>.

Thanks again and

Best regards,

    Stefan

-----------------------------------------------------------------------------
http://www.gap-system.org/DevelopersPages/StefanKohl/
-----------------------------------------------------------------------------