The Collatz Conjecture and Hailstone Sequences: Deceptively Simple, Devilishly Difficult

Here is a very simple math problem:

If a number is even, divide the number by two. If a number is odd, multiply the number by three, and then add one. Do this over and over with your results. Will you always get down to the value 1 no matter what number you choose?

Go ahead and test this out for yourself. Plug a few numbers in. Try it out. I’ll wait.

Back? Good. Here’s my example: I start with the number 12.

12 is even, so I divide it by 2.

12/2=6.

6/2=3.

3 is odd, so we multiply it by 3 then add 1.

(3*3)+1=10.

10/2=5.

(5*3)+1=16.

16/2=8.

8/2=4.

4/2=2.

2/2=1.

And we have arrived at one, just like we thought we would. But is this ALWAYS the case, for ANY number I could possibly dream of?

This may sound easy, but in fact it is an unsolved mathematics problem, with some of the best minds in the field doing research on it. It’s easy enough to check low values, but numbers are infinite, and can get very, very, very large. How do we KNOW that it works for every single number that exists?

That is what is so difficult about this problem. While every single number we have checked (which is a LOT) ends up at 1 sooner or later (some numbers can bounce around for a very long time, hence why they are called “hailstone sequences”), we still have no method to prove that it works for every number. Mathematicians have been looking for some method to predict this, but despite getting into some pretty heavy mathematics in an attempt to attack this problem, we still do not know for sure.

This problem is known as the Collatz Conjecture and is very interesting to mathematicians young and old because it is so easy to explain and play with, yet so tough to exhaustively prove. What do you think? Will this problem ever be solved? And what would be the implications if it was?

Here is some simple Python code that can display the cycles for any number you type in:

#!/usr/bin/python
num = int(input("Enter a number: "))
while num!=1:
if num%2 == 0:
num = num/2
else:
num = (num*3)+1
    print num
Advertisements

6 comments on “The Collatz Conjecture and Hailstone Sequences: Deceptively Simple, Devilishly Difficult

  1. fishes56 says:

    Have you heard of “Four is the magic number”? It’s not really anything to do with math, more about silly word coincidences, but this reminded me of it. I was going to try and write a python thing to show it, but I realized I don’t know how to convert spelled out numbers into integers and vice versa yet… haha but maybe I’ll try and figure it out.

    • Could you elaborate?

      • fishes56 says:

        It’s supposed to be a riddle:
        12 is 6, 6 is 3, 3 is 5, 5 is 4, 4 is 4. 4 is the magic number, why?
        68 is 10, 10 is 3, 3 is 5, 5 is 4, 4 is 4. 4 is the magic number, why?
        26 is 9, 9 is 4, 4 is 4. 4 is the magic number, why?
        Do you want the answer, or would you like to guess?

    • The second number is the number of letters in the first number.

      T W E L V E = 6 letters
      F O U R = 4 letters
      S I X T Y E I G H T = 10 letters

      Good riddle, I’d seen this one before and had forgotten about it 🙂

    • here is some code:

      (got the number->spelling code from http://code.activestate.com/recipes/285100-getnum/ )

      #!/usr/bin/python
      
      def getNum(n):
          nums = ['zero','one','two','three','four','five','six','seven','eight','nine','ten', \
          'eleven','twelve','thriteen','fourteen','fifteen','sixteen','seventeen','eighteen','nineteen']
          tens = [None, None,'twenty','thrity','fourty','fifty','sixty','seventy','eighty','ninety']
          try: n = int(n)
          except ValueError: return 'NaN'
      
          if n < 0:
              return 'negitive ' + getNum(abs(n))
          if n < 20:
              return nums[n]
          if n < 100: # and n >= 20
              s = tens[n//10]
              if n % 10:
                  s += ' ' + nums[n%10]
              return s
          if n < 1000: # and n >= 100
              s = nums[n//100] + ' hundred'
              if n % 100:
                  s += ' ' + getNum(n - (n//100)*100)
              return s
          if n < 1000000: # and n >= 1000
              s = getNum(n//1000) + ' thousand'
              if n % 1000:
                  s += ' ' + getNum(n - (n//1000)*1000)
              return s
          if n < 1000000000: # and n >= 1000000
              s = getNum(n//1000000) + ' million'
              if n % 1000000:
                  s += ' ' + getNum(n - (n//1000000)*1000000)
              return s
          if n < 1000000000000: # and n >= 1000000000
              s = getNum(n//1000000000) + ' billion'
              if n % 1000000000:
                  s += ' ' + getNum(n - (n//1000000000)*1000000000)
              return s
          if n < 1000000000000000: # and n >= 1000000000
              s = getNum(n//1000000000000) + ' trillion'
              if n % 1000000000000:
                  s += ' ' + getNum(n - (n//1000000000000)*1000000000000)
              return s
          else:
              return 'infinity'
      
      def __main__():
          while True:
              i = raw_input("Enter a number or 'q' to quit: ")
              if i in ('q','quit','exit'): break
              letters=len(getNum(i))
              print i + " is " + str(letters)
      
      if __name__ == '__main__': __main__()
      
      
  2. […] fishes56 alerted me to this riddle in a comment here, and if you didn’t see it I wanted to share it here in a separate post cause its a little fun […]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s