The Collatz conjecture is an amazing thing. For people who don't know, the Collatz conjecture is the conjecture where you take any natural number. If that number is even, divide by two. If it is odd, multiply by three and add one. The conjecture is that this process will always return to one. Looking at it, I know when testing I can skip all even numbers, because when you divide by two, you get a smaller number you already tested. And I can skip every other odd number, because when multiplied by three and is added to one, you will get a multiple of four, so you can divide by two twice, and you will get a number smaller than the original which you have already tested. My question is, can I eliminate any other number patterns? Or is there something I'm missing about the ones I already have?

  • $\begingroup$ For $n$ odd, $C(n)= (3n+1)/2^{v_2(3n+1)}$ so you'll have $C(n)\le n$ iff $v_2(3n+1)\ge 2$ iff $3n+1\equiv 0\bmod 4$ iff $n\equiv 1\bmod 4$. Then you can remove the other residue classes by looking at $C(C(n)),C^3(n)$ and so on. $\endgroup$ – reuns Jan 17 at 23:20
  • 1
    $\begingroup$ If you multiply an odd number by three and add one you do not get the multiple of four, in general. Try doing that for numbers in the form $4k+3$, $k\in\mathbb N$. $\endgroup$ – Pavel R. Jan 17 at 23:25
  • 3
    $\begingroup$ @PavelR. That's why he said every other odd number $\endgroup$ – PythonSage Jan 18 at 0:33
  • $\begingroup$ See a visual display of an infinite set of such patterns. This is an old version of mine when I had not yet much experience in writing up maths. Mainpage: go.helms-net.de/math/collatz/aboutloop/collloopintro_main.htm , subpage numerical trees: go.helms-net.de/math/collatz/aboutloop/collatzgraphs.htm and ther the two excel-sheets, especially simple the second in base-4 representation : go.helms-net.de/math/collatz/aboutloop/collatzgraphs-Dateien/… $\endgroup$ – Gottfried Helms Jan 18 at 4:22
  • $\begingroup$ Thanks for the links, @GottfriedHelms! They're very helpful. $\endgroup$ – Isaac Goodman Jan 18 at 12:36

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.