As with triangular numbers ($ text {mod} 2 ^ n $) as a permutation of $ {0,1,2, dots, 2 ^ n-1 } $ and what is the set of triangular numbers mod $ n $? , Mapping the integer $ n $ to the $ 0 le n lt2 ^ k $ to the rest of the corresponding triangle number $ frac12n (n + 1) $ modulo $ 2 ^ k $ results in a permutation. For example for $ k = $ 3:

$$

01234567 \

01362754

$$

I noticed $ k = 5 $, all elements except $ 0 $ and $ 1 $ (which are always mapped to themselves) form a single cycle of length $ 2 ^ k-2 $, The probability of an evenly random permutation of the length $ n $ consists of a single cycle $ frac1n $So if these permutations (except $ 0 $ and $ 1 $) could be regarded as uniformly random, the probability would only be $ frac12 cdot frac16 cdot frac1 {14} cdot frac1 {30} = frac1 {5040} $, Reason enough to check whether the pattern remains larger $ k $,

It turns out that this is not the case $ k = 6 $ there is a $ 3 $-Cycle: $ (4,10,55) $, Nevertheless, unusually long cycle lengths remain: for everyone $ k $ of $ 2 $ to $ 12 $, except for $ k = 7 $The largest cycle contains more than half of the elements, while the likelihood that this will happen in a random permutation is rough $ ln $ 2, Indeed, in $ 9 $ of these $ 11 $ Cases (all except $ k = 6 $ and $ k = 7 $) the largest cycle contains more than $ frac45 $ of the elements; The probability of this is approximate $ ln frac54 ca.0.223 $ per case, so the probability that it will at least happen $ 9 $ get out $ 11 $ is $ sum_ {k = 9} ^ {11} binom {11} k left ( ln frac54 right) ^ k left (1- ln frac54 right) ^ {11-k} approx5 cdot10 ^ {- 5} $,

However, this pattern does not continue either: $ k $ of $ 2 $ to $ 30 $, there are $ 21 $ Cases with cycles of more than half of the elements, which is beyond the expected number $ 29 ln2 approx. $ 20.1; and for $ k $ of $ 13 $ to $ 30 $ It is only $ 4 $ Cases with cycles of more than $ frac45 $ of items that is almost exactly the expected number $ 18 ln frac54 ca.4.0 $,

My question is: is there an explanation for this initial tendency to form long cycles? Or should we attribute it to a coincidence?

For simplicity, here is the code that I used to determine the cycle lengths, and here are the results up to $ k = $ 30:

```
4 : 2
8 : 6
16 : 14
32 : 30
64 : 40, 19, 3
128 : 55, 48, 14, 6, 3
256 : 247, 4, 3
512 : 488, 7, 6, 6, 3
1024 : 818, 157, 47
2048 : 1652, 371, 23
4096 : 4060, 25, 9
8192 : 3754, 3609, 412, 321, 79, 12, 3
16384 : 15748, 292, 190, 71, 24, 22, 13, 13, 9
32768 : 20161, 11349, 333, 305, 281, 218, 72, 44, 3
65536 : 20128, 17231, 16759, 8072, 2377, 579, 295, 60, 33
131072 : 85861, 26603, 9389, 3887, 3365, 682, 594, 488, 118, 49, 23, 6, 5
262144 : 159827, 89991, 5749, 5465, 592, 231, 118, 100, 42, 24, 3
524288 : 211265, 176243, 59029, 35639, 28496, 6122, 4245, 1239, 713, 632, 244, 146, 133, 59, 39, 36, 6
1048576 : 620076, 216520, 131454, 68118, 7535, 2111, 1235, 1028, 225, 213, 36, 20, 3
2097152 : 993084, 583840, 394263, 87941, 31835, 3389, 1648, 459, 306, 273, 45, 35, 14, 10, 8
4194304 : 1487646, 1119526, 942359, 429054, 118037, 64446, 28806, 3238, 323, 291, 186, 126, 118, 102, 12, 11, 10, 7, 4
8388608 : 2542051, 2462220, 2040680, 1138236, 93072, 45880, 19664, 16473, 14243, 6319, 2917, 2598, 2160, 1414, 514, 118, 23, 19, 5
16777216 : 12137774, 4004239, 271250, 253890, 43860, 33597, 25495, 4132, 2575, 157, 116, 67, 35, 9, 8, 6, 4
33554432 : 28169497, 2552414, 1401622, 1019221, 356682, 21006, 14735, 10242, 8223, 566, 135, 45, 21, 15, 6
67108864 : 32223531, 29360424, 3530597, 932310, 809707, 99109, 83093, 67418, 1612, 364, 248, 248, 166, 21, 14
134217728 : 87591110, 34361487, 3360928, 3343185, 3291274, 1345478, 353498, 323522, 158252, 47767, 17776, 11159, 5927, 2681, 2343, 530, 235, 208, 162, 84, 59, 31, 30
268435456 : 232647749, 24918738, 5559122, 3742461, 525140, 384941, 278834, 197080, 62977, 48736, 21684, 16632, 13525, 8993, 3073, 2721, 1625, 1262, 153, 5, 3
536870912 : 379598603, 129063661, 26279056, 665648, 483286, 222289, 137686, 106713, 94323, 80276, 59199, 41767, 15498, 10615, 5066, 2816, 2699, 1579, 113, 10, 7
1073741824 : 877039442, 181409872, 7571387, 6549459, 921247, 240525, 3924, 3416, 1602, 894, 54
```