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?)
  • 2
    $\begingroup$ How do you know it is a necessary condition if you don't have a proof? $\endgroup$ Dec 8 '20 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$ Dec 8 '20 at 17:49
  • $\begingroup$ @WhoKnowsWho I have computationally tested my conjecture for all moduli below 100000. $\endgroup$
    – DaBler
    Dec 8 '20 at 18:47
  • $\begingroup$ @RaviFernando Note that the $f(n)$ is defined on integers, before aplying the modulo operation. $\endgroup$
    – DaBler
    Dec 8 '20 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$ Dec 8 '20 at 22:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.