3
$\begingroup$

By 'bit-limited', I mean that we have a computer/calculator that handles binary numbers up to $n$ bits ($n>=1$), and any numbers greater than $2^n-1$ overflow by truncating the higher bits. Background information about the Collatz map and cycles can be found here.

For example, with 4 bits, we represent numbers from 0 to 15. Starting at 7, the map goes 7 -> 22 (overflow!) -> 6 -> 3 -> 10 -> 5 -> 16 (overflow!) -> 0 -> 0 -> 0... Using the same 4 bits, but starting from 11, we get 11-> 34 (overflow!) -> 2 -> 1 -> 4 -> 2 -> 1...

I have found that for $n = 9$, there is an additional cycle through 71: of the 512 possible numbers, the 71 cycle covers 124 of them. For $n=11$, there is a cycle through 55 covering 632/2048 numbers. I have tried higher numbers of bits, up to 22, and I haven't found any other cycles.

I'm trying to find a way to approach the question: are there higher values of $n$ that also result in cycles? or:

What values of m lead to cycles in a modified Collatz map

$$a_{i+1} = \begin{cases} (3\cdot a_i + 1) \mod{2^m} & a_i \mbox{ odd} \\ (\frac{a_i}{2}) \mod{2^m} & a_i \mbox{ even} \end{cases} $$

I found other treatments where the whole trajectory is found and then transformed modulo $2^m$, but that does not create cycles.

$\endgroup$
2
  • $\begingroup$ Do you know about congruences? See this $\endgroup$
    – ajotatxe
    Apr 26, 2019 at 13:58
  • $\begingroup$ @ajotatxe oh thanks, that at least helps me frame the question better. I did some looking around for Collatz sequences mod $2^n$ but I didn't quite find what I was looking for -- I'm updating my question $\endgroup$ Apr 26, 2019 at 14:11

1 Answer 1

2
$\begingroup$

I had made some experiments with the T alternative function few years ago.

$T(n) = \left\{ \begin{array}{ll} \frac{n}{2} & \text{if }n\text{ even}\\ \frac{3n + 1}{2} & \text{if }n\text{ odd}\\ \end{array}\right.$

I don't remember the details. But I only tried in modulo arithmetic with modulo $2^8$, $2^{16}$, $2^{24}$ and $2^{32}$. For these values I had only found new particular cycles that contains 0.

You can see 3np1 mod problem C++ Documentation and my code on Bitbucket 3np1_mod_problem.

--- Null and odd exceptions with modulo = 2^8 for T function ---
0 -> 0
85 -> 0
227 -> 85

--- Null and odd exceptions with modulo = 2^16 for T function ---
0 -> 0
14563 -> 21845 -> 0
19417 -> 29126 -> 14563
21845 -> 0
53399 -> 14563
56635 -> 19417

--- Null and odd exceptions with modulo = 2^24 for T function ---
0 -> 0
5592405 -> 0
9320675 -> 5592405

--- Null and odd exceptions with modulo = 2^32 for T function ---
0 -> 0
1431655765 -> 0
3817748707 -> 1431655765
$\endgroup$
1
  • $\begingroup$ Thanks for checking out $2^{32}$. You might notice that the bit patterns that lead to 0 are either 101010...101 or 111000111..00011. $\endgroup$ Apr 30, 2019 at 13:34

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .