Dear Alexander,
>> The little problem for you is now to find the length of the cycle of 173176.
>> This may require nothing more than a little patience -- but who knows ... !
>
> I've started this computation a week ago, being lured by hopefully little
> patience that I may need to have, having no hint from you how much patience
> do I really need ;-). So, after one week, the last line of the output says:
>
> New maximum with 76785 digits reached after 15621898577 iterations.
Then you had notably more patience than me -- thanks and congratulations!
-- I stopped the computation after about 5700000000 iterations and a maximum
slightly above 10^40000.
> How do you know that all cycles for smaller positive integers are finite
> - was it checked with a help of a computer?
Yes, I have checked that by computer. -- Most cycles are MUCH shorter!
In any case, checking all cycles for positive integers less than 173176
took altogether MUCH less computing time than even only the 5700000000
iterations I did on the cycle of 173176 -- let alone the 15621898577 you did!!
Short cycles (length <= 100) intersecting nontrivially with [0..100]
are for example:
gap> ShortCycles(g,[0..100],100);
[ [ 0 ], [ 1, 4, 12, 18, 15, 10, 11, 14, 19, 13, 9, 8, 6, 7, 5 ], [ 2, 3 ],
[ 16, 24, 42, 43, 29, 28, 36, 54, 59, 58, 55, 50, 51, 37, 25, 20, 30, 31,
34, 39, 38, 35, 21, 17 ], [ 22, 23 ], [ 26, 27 ], [ 46, 47 ],
[ 52, 78, 75, 70, 71, 74, 79, 53 ], [ 62, 63 ],
[ 76, 114, 119, 118, 115, 110, 111, 77 ], [ 82, 83 ], [ 86, 87 ],
[ 92, 138, 135, 130, 131, 134, 139, 93 ] ]
Actually the natural density of the set of integers belonging to cycles
of length <= 24 is at least 47/108. -- To find this, we use that finite
cycles of that particular permutation often (likely: always) come in infinite
series that correspond to cycles on the set of all residue classes of Z:
gap> cycs := ShortResidueClassCycles(g,480,24);
[ [ 2(60), 3(60) ], [ 22(60), 23(60) ], [ 26(60), 27(60) ],
[ 46(60), 47(60) ],
[ 52(120), 78(180), 75(180), 70(180), 71(180), 74(180), 79(180), 53(120) ],
[ 76(120), 114(180), 119(180), 118(180), 115(180), 110(180), 111(180),
77(120) ],
[ 92(120), 138(180), 135(180), 130(180), 131(180), 134(180), 139(180),
93(120) ],
[ 116(120), 174(180), 179(180), 178(180), 175(180), 170(180), 171(180),
117(120) ],
[ 16(480), 24(720), 42(1080), 43(1080), 29(720), 28(720), 36(1080),
54(1620), 59(1620), 58(1620), 55(1620), 50(1620), 51(1620), 37(1080),
25(720), 20(720), 30(1080), 31(1080), 34(1080), 39(1080), 38(1080),
35(1080), 21(720), 17(480) ],
[ 176(480), 264(720), 402(1080), 403(1080), 269(720), 268(720), 396(1080),
594(1620), 599(1620), 598(1620), 595(1620), 590(1620), 591(1620),
397(1080), 265(720), 260(720), 390(1080), 391(1080), 394(1080),
399(1080), 398(1080), 395(1080), 261(720), 177(480) ],
[ 232(480), 348(720), 516(1080), 774(1620), 779(1620), 778(1620),
775(1620), 770(1620), 771(1620), 517(1080), 345(720), 340(720),
510(1080), 511(1080), 514(1080), 519(1080), 518(1080), 515(1080),
341(720), 344(720), 522(1080), 523(1080), 349(720), 233(480) ],
[ 392(480), 588(720), 876(1080), 1314(1620), 1319(1620), 1318(1620),
1315(1620), 1310(1620), 1311(1620), 877(1080), 585(720), 580(720),
870(1080), 871(1080), 874(1080), 879(1080), 878(1080), 875(1080),
581(720), 584(720), 882(1080), 883(1080), 589(720), 393(480) ] ]
gap> time; # quick
203
gap> Density(Union(Flat(cycs)));
47/108
Also finding the lengths of all cycles containing positive integers
less than 1000 takes no more than a few seconds:
gap> CycleRepresentativesAndLengths(g,[0..1000]);
[ [ 1, 15 ], [ 2, 2 ], [ 16, 24 ], [ 22, 2 ], [ 26, 2 ], [ 32, 6296 ],
[ 46, 2 ], [ 52, 8 ], [ 56, 296 ], [ 62, 2 ], [ 76, 8 ], [ 82, 2 ],
[ 86, 2 ], [ 92, 8 ], [ 106, 2 ], [ 112, 104 ], [ 116, 8 ], [ 122, 2 ],
[ 136, 440 ], [ 142, 2 ], [ 146, 2 ], [ 152, 40 ], [ 166, 2 ], [ 172, 8 ],
[ 176, 24 ], [ 182, 2 ], [ 196, 8 ], [ 202, 2 ], [ 206, 2 ], [ 212, 8 ],
[ 226, 2 ], [ 232, 24 ], [ 236, 8 ], [ 242, 2 ], [ 256, 56 ], [ 262, 2 ],
[ 266, 2 ], [ 272, 408 ], [ 286, 2 ], [ 292, 8 ], [ 296, 104 ], [ 302, 2 ],
[ 316, 8 ], [ 322, 2 ], [ 326, 2 ], [ 332, 8 ], [ 346, 2 ], [ 352, 264 ],
[ 356, 8 ], [ 362, 2 ], [ 376, 1304 ], [ 382, 2 ], [ 386, 2 ], [ 392, 24 ],
[ 406, 2 ], [ 412, 8 ], [ 416, 200 ], [ 422, 2 ], [ 436, 8 ], [ 442, 2 ],
[ 446, 2 ], [ 452, 8 ], [ 466, 2 ], [ 472, 104 ], [ 476, 8 ], [ 482, 2 ],
[ 496, 24 ], [ 502, 2 ], [ 506, 2 ], [ 512, 696 ], [ 526, 2 ], [ 532, 8 ],
[ 536, 3912 ], [ 542, 2 ], [ 556, 8 ], [ 562, 2 ], [ 566, 2 ], [ 572, 8 ],
[ 586, 2 ], [ 592, 888 ], [ 596, 8 ], [ 602, 2 ], [ 616, 728 ], [ 622, 2 ],
[ 626, 2 ], [ 632, 2776 ], [ 646, 2 ], [ 652, 8 ], [ 656, 24 ], [ 662, 2 ],
[ 676, 8 ], [ 682, 2 ], [ 686, 2 ], [ 692, 8 ], [ 706, 2 ], [ 712, 24 ],
[ 716, 8 ], [ 722, 2 ], [ 736, 495448 ], [ 742, 2 ], [ 746, 2 ],
[ 752, 1272 ], [ 766, 2 ], [ 772, 8 ], [ 776, 376 ], [ 782, 2 ],
[ 796, 8 ], [ 802, 2 ], [ 806, 2 ], [ 812, 8 ], [ 826, 2 ], [ 832, 120 ],
[ 836, 8 ], [ 842, 2 ], [ 856, 2264 ], [ 862, 2 ], [ 866, 2 ], [ 872, 24 ],
[ 886, 2 ], [ 892, 8 ], [ 896, 132760 ], [ 902, 2 ], [ 916, 8 ],
[ 922, 2 ], [ 926, 2 ], [ 932, 8 ], [ 946, 2 ], [ 952, 456 ], [ 956, 8 ],
[ 962, 2 ], [ 976, 24 ], [ 982, 2 ], [ 986, 2 ], [ 992, 1064 ] ]
gap> time;
2824
I still think that likely all cycles are finite --
if my understanding of it is right, besides the regularities mentioned above,
cycles behave in some sense roughly like a simple random walk on Z, and are
finite if the random walk is recurrent. In this "model", +1 in the random walk
on Z roughly corresponds to multiplication by some constant, and -1 corresponds
to division by that constant. If that describes cycles of g in a satisfactory
way, that means of course also that cycles may sometimes be pretty long --
for example if a random walk on Z has reached a value in the 100000's, it
usually takes a while until it gets back to 0 for the next time ... .
Proving finiteness of all cycles may be pretty hard, however.
Best wishes,
Stefan
_______________________________________________
Forum mailing list
Forum@mail.gap-system.org
http://mail.gap-system.org/mailman/listinfo/forum
