6
$\begingroup$

Let $\langle n \rangle_N$ be a notation for an integer $n$ modulo $N$. Now consider the function \begin{align} f(n) = \begin{cases} (3n+1)/2 \text{,} & \text{if } n \equiv 1 \pmod{2} \text{,} \\ n/2 \text{,} & \text{if } n \equiv 0 \pmod{2} \text{,} \end{cases} \end{align} and the sequences \begin{align} a_{i} = \left\langle f(a_{i-1}) \right\rangle_N \end{align} for all $0 < a_0 < N$.

I deal with the question of whether, for given modulus $N > 2$ and for each starting value $0 < a_0 < N$, there is an element $a_i = 1$ with $i \ge 0$.

I figured out that the answer is yes (i.e. the Collatz conjecture holds in the set of integers modulo $N$) in about half of the cases. Moreover, I have found that necessary conditions for the existence of $a_i = 1$ are \begin{align} N &\neq -1 \pmod{3} \text{, and} \\ N &\neq \phantom{+}0 \pmod{19} \text{.} \end{align}

My questions are:

  • Has this problem been studied before? (Collatz problem on integers modulo $N$)
  • Would anyone be able to sketch a proof of the necessary conditions? (Why 19?)
$\endgroup$
7
  • 3
    $\begingroup$ How do you know it is a necessary condition if you don't have a proof? $\endgroup$
    – Raghav
    Commented Dec 8, 2020 at 17:49
  • 2
    $\begingroup$ I'm not convinced that your operation is well-defined modulo $N$. In particular, if $N$ is odd, then it doesn't make sense to ask whether $n \in \mathbb Z/N\mathbb Z$ is odd or even. If $N$ is even and $n \pmod N$ is also even, then $n/2$ exists but is not unique mod $N$. $\endgroup$
    – Ravi Fernando
    Commented Dec 8, 2020 at 17:49
  • $\begingroup$ @WhoKnowsWho I have computationally tested my conjecture for all moduli below 100000. $\endgroup$
    – DaBler
    Commented Dec 8, 2020 at 18:47
  • $\begingroup$ @RaviFernando Note that the $f(n)$ is defined on integers, before aplying the modulo operation. $\endgroup$
    – DaBler
    Commented Dec 8, 2020 at 18:50
  • $\begingroup$ I've studied it on modulo $8$. But the resulting output-bit is necessary in the next iteration. It's a bit difficult to explain in a few words. $\endgroup$
    – user366820
    Commented Dec 8, 2020 at 22:49

1 Answer 1

Reset to default
2
$\begingroup$

To answer your first question, there has been at least some study precisely on what exceptions to the Collatz Conjecture arise in the integers modulo N, however, what I found focused on finding choices of $a_0$ with $a_i = a_0,\,i\geq1$ given the parities of $a_0,a_1,a_2,\ldots$ i.e. fixed points or cycles that disprove the existence of $a_i=1.$ You can check out this paper:

Moorthy, C.Ganesa & Thangappan, T.Kannan. (2016). Collatz Conjecture for Modulo an Integer. International Journal of Mathematics And its Applications. 4. 41-61.
https://www.researchgate.net/profile/Cganesa-Moorthy/publication/316141441_Collatz_Conjecture_for_Modulo_an_Integer/links/58f21cadaca27289c21671cf/Collatz-Conjecture-for-Modulo-an-Integer.pdf

I can answer your second question with, "no." I can disprove your $N \not\equiv 0 (\text{mod}\;19)$ requirement with 54 counterexamples less than or equal to 12217. For example, $N=57.$

You can check below that each $a$ -> $b$ satisfies $b=\langle f(a)\rangle_{57}$, each $0 < a < N$ is the left hand side of one these operations and each row terminates at either 1 or a value that was shown to reach 1 in a previous row, meaning $\forall a_0,\,0<a_0<N\,\exists\,i\geq 0,\,a_i=1$.

1
2 -> 1
3 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2
6 -> 3
7 -> 22 -> 11 -> 34 -> 17 -> 52 -> 26 -> 13 -> 40 -> 20 -> 10
9 -> 28 -> 14 -> 7
12 -> 6
15 -> 46 -> 23 -> 13
18 -> 9
19 -> 1
21 -> 7
24 -> 12
25 -> 19
27 -> 25
29 -> 31 -> 37 -> 55 -> 52
30 -> 15
32 -> 16
33 -> 43 -> 16
35 -> 49 -> 34
36 -> 18
38 -> 19
39 -> 4
41 -> 10
42 -> 21
44 -> 22
45 -> 22
47 -> 28
48 -> 24
50 -> 25
51 -> 40
53 -> 46
54 -> 27
56 -> 28

The other examples are; 133, 285, 361, 513, 817, 969, 1045, 1653, 1881, 1957, 2109, 2185, 2565, 2641, 3021, 3097, 3477, 3705, 3781, 4009, 4389, 4617, 4845, 5377, 5605, 5757, 5833, 6745, 6973, 7201, 7429, 7885, 8569, 8797, 9405, 9481, 9633, 9709, 9861, 9937, 10089, 10545, 10621, 10773, 11001, 11077, 11229, 11305, 11457, 11685, 11761, 12141, 12217.

P.S. I didn't do a deep dive on this just to answer, I was investigating this with a c++ class I wrote for integers modulo $N$. I skipped even $N$ (sometimes with the exception of $N=2$) because I applied the Collatz function modulo $N$ and attempting to create the multiplicative inverse of 2 in such cases throws an exception.

$\endgroup$

You must log in to answer this question.

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