Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Collatz Conjecture - Bouncing Ideas

  1. Aug 22, 2011 #1
    Hey, this is my first post, so... Hello everybody!

    I've been looking into the Collatz conjecture, and like most mathematically minded people, been completely absorbed by it. I'm looking to bounce some ideas off other people, kind of a peer review of a couple things if you will.

    I'll be the first to state that I'm nowhere near qualified, or intelligent, enough to call myself an expert, so feel free to correct me and tell me this was worked out a hundred years ago, I'd appreciate it.

    I'm looking for a way to avoid checking every number up to n when looking for an exception to the Collatz Conjecture.

    If every positive integer can be expressed as odd * 2n such that prime numbers are p * 20 and powers of 2 are 1 * 2n and branches of the Collatz Tree begin with an odd positive integer followed by that odd positive integer multiplied by 2n where n is the number of steps to get back to the odd positive integer, would it be safe to assume that for each odd positive integer present in the Collatz Tree every even positive integer of the form odd * 2n would be present?

    If this assumption is safe to make, we can instantly avoid the checking of every even positive integer, a 50% reduction in amount of numbers requiring checking.

    Also, for every branch of the Collatz Tree, a new branch is created wherever [(odd * 2n) - 1] % 3 == 0. With this in mind, if 3 is a factor of odd, then 3 is also a factor of odd * 2n and as such [(odd * 2n) - 1] % 3 == 2. Therefore, for any branch where 3 is a factor of the base odd positive integer, no sub-branch can ever be created.

    If no sub-branch can ever be present, any odd positive integer divisible by 3 cannot possibly be reliant on any prior representation of itself in the Collatz Tree in order for itself to be represented in the Collatz Tree and thus cannot be part of the main sequence of an exception loop. Therefore, we can avoid checking odd positive integers that are divisible by 3. This can further reduce the numbers that require testing by 33%.

    These 2 reductions leave us with testing 33% of numbers - something that can increase our search times greatly.

    I hope I have explained myself well enough, it is one of my weaknesses.

    What do you guys think?
  2. jcsd
  3. Aug 22, 2011 #2
    Only got time to quickly look at your assumption paragraph beginning

    "If every +ve integer can be expressed as odd * 2^n..."

    But I can see straight away that you are not considering odd numbers at all in your tree branches as (any number odd or even) * (power of 2) = even.

    You do consider the primes above but that is all you have. Prime numbers and even numbers.

    I looked at the Collatz conjecture many times a few years ago and I came up with what I thought was a repetition of Mersenne primes (as remainders) in the branches. I'll have a look at my notes and get back to this thread. May take a few days.

    Last edited: Aug 22, 2011
  4. Aug 22, 2011 #3
    Hey thankyou for your reply. I too have little time - about 3 minutes before I leave to work.

    Every odd number can be expressed the same way that a prime number can be expressed. That is, odd * 20 because 20 evaluates to 1. Therefore odd numbers are expressed as odd * 1, or more simply, odd.

Share this great discussion with others via Reddit, Google+, Twitter, or Facebook