Observations on the Collatz Conjecture – Part 2

The Basic Shape of the Collatz Conjecture

If you map out the numbers of the Collatz Conjecture on paper you will create a branching tree, similar to the diagram below:

Diagram 1: The Collatz Tree

The green lines represent a division by 2, the red lines being a multiplication by 3 (plus 1). The tree is built from the bottom up, performing these processes in reverse. Note: the Red line from 1 to 4 is the only time that the Conjecture has caused any repetition, as the numbers cycle 4, 2, 1, 4, 2, 1. It is not considered when proving the Conjecture.

If you rearrange the shape of the tree to a more uniform look, you can show easily that any odd number “k” will go “down” to 3k+1, “up” to 12k+4, and up again to 4k+1 ass shown in the following diagram:

Diagram 2: Basic Collatz Structure

It should be noted that you can technically plug in any value of k into this number, even even numbers, and the math will work out, however you are breaking the rules of the game.

Ex: If k=8, 3k+1=25, 4(25)=100, (100-1)/3=33, and 33=4(8)+1

However, that is a red herring, because if k=8, then you would divide out all the 2s to reach 1.

The Mathematical Pattern

Just as the numbers themselves can be reduced as whole numbers, they can be reduced using modular arithmetic. In Diagram 2: we placed 4k+1 is a value in the Basic Shape, which you can also be said as 1 mod 4, any number that when divided by 4 leaves a remainder of 1.

When you perform the Odd function on a modular number, you multiply both the Divisor (4k in this case) and the Remainder (1 in this case) by 3, then add 1 to the Remainder only. This is where 12k+4 comes out.

If you look at the tree in Diagram 1, 4 decreases to 2, then to 1, then increases to 4, and the same pattern holds here, because if k=0, then the whole Divisor is ignored, and we are back to whole numbers.

Thus, as long as the Divisor remains a whole number, you can follow the Remainders through the Tree Diagram

The 4k+3 Problem

As I showed before any numbers that fit into 0, 1, or 2 mod 4 will always reduce to a lower number, but 4k+3 does not.

  • 4k+3 (Odd)
  • 12k+10 (Even)
  • 6k+5 (Odd)
  • 18k+16 (Even)
  • 9k+8 (Either Even or Odd)

You can not reduce it further, because of that ambiguous ending, and it is clearly larger than where it started. But if we start at a higher Divisor:

  • 16k+3 (Odd)
  • 48k+10 (Even)
  • 24k+5 (Odd)
  • 72k+16 (Even)
  • 36k+8 (Even)
  • 18k+4 (Even)
  • 9k+2 (Either Even or Odd)

Again, we reach an ambiguous level, however because we started higher 16k+3>9k+2, and we have a solution.

We can therefor show that any number 3 mod 16 will decrease, every time.

But there are other options that also equal 3 mod 4:

  • 128k+7 (Odd)
  • 384k+22 (Even)
  • 192k+11 (Odd)
  • 576k+34 (Even)
  • 288k+17 (Odd)
  • 864k+52 (Even)
  • 432k+26 (Even)
  • 216k+13 (Odd)
  • 648k+40 (Even)
  • 324k+20 (Even)
  • 162k+10 (Even)
  • 81k+5 (Lower)

The List So Far

The following numbers can be safely eliminated as failures, meaning any number that fits in these criteria will always reach a lower number than you started:

  • 4k + 0
  • 4k + 1
  • 4k + 2
  • 16k + 3
  • 128k + 7

And these numbers we will still need to explore:

  • 16k+11
  • 16k+15
  • 32k+23
  • 32k+27
  • 32k+31
  • 128k+71

To be continued…

Each following installment will run through and eliminate possibilities, starting from the least complex, in the hope of eliminating all possibilities where the number never decreases.

Series NavigationObservations on the Collatz Conjecture – Part 1 >>
Advertisements

Leave a Reply