[GAP Forum] A permutation group with huge finite orbits

[Jason B Hill]

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/

With GMP and GCC installed, you could compile with something like:

gcc -O3 -o length-residue-orbit-omp length-residue-orbit-omp.c -lgmp
-fopenmp

And then, on my machine, using:

time ./length-residue-orbit-omp

produces:

total iterations: 47610700792

real    4469m55.660s (About 3.1 days)
user    8736m34.552s
sys    1m43.818s


Cheers,
Jason



On Mon, Nov 19, 2012 at 2:04 PM, Stefan Kohl <stefan at mcs.st-and.ac.uk>wrote:

> On Mon, November 19, 2012 5:51 pm, Bill Allombert wrote:
> > On Mon, Nov 19, 2012 at 05:05:42PM -0000, Stefan Kohl wrote:
> >> Proving finiteness of all cycles may be pretty hard, however.
> >
> > Indeed, this problem is too close to the Collatz ((3n+1)/2) conjecture
> > for comfort.
>
> Most likely yes. -- But I wouldn't claim right away that it is really
> of similar difficulty. There are some regularities, e.g. except for
> the cycle containing 1, all cycles seem to have either length 2 or length
> congruent to 8 mod 16 etc.
>
> > The Collatz sequence can be restated in your notation by
> > asking whether the orbits of Z under M are finite, where M is the
> submonoid
> > of Z^Z generated by a = (1(2)->2(3)) and b = (0(2)->0(1))
> > (a and b are not one-to-one).
>
> You can actually do the same with a group. -- The group
>
>       G := <(1(2),4(6)),(1(3),2(6)),(2(3),4(6))> < Sym(Z)
>
> acts transitively on the set of positive integers which are not
> divisible by 6 if and only if the 3n+1 conjecture holds.
>
> The group G can be entered by pasting the following into GAP:
>
> a := ClassTransposition(1,2,4,6);
> b := ClassTransposition(1,3,2,6);
> c := ClassTransposition(2,3,4,6);
> G := Group(a,b,c);
>
> Best wishes,
>
>     Stefan
>
>
>
> _______________________________________________
> Forum mailing list
> Forum at mail.gap-system.org
> http://mail.gap-system.org/mailman/listinfo/forum
>



-- 
Jason B. Hill
http://www.jasonbhill.com  |  Jason.B.Hill at Colorado.edu