Wednesday, September 15, 2010

Collatz conjecture

The Collatz conjecture is also known as the 3n + 1 conjecture. Take any natural number n. If n is even, divide it by 2 to get n / 2, if n is odd multiply it by 3 and add 1 to obtain 3n + 1. Repeat the process indefinitely. The conjecture is that no matter what number you start with, you will always eventually reach 1.

For instance, starting with n = 19, generates the sequence 19, 58, 29, 88, 44, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1.

Multiplying any odd integer by 3, then adding 1, always results in an even integer. The sequence can be shortened using (3n + 1) / 2 when n is odd. Which produces the sequence 19, 29, 44, 22, 11, 17, 26, 13, 20, 10, 5, 8, 4, 2, 1.

Let the repeating process be (3n + 1) / 2 when n is odd, and maintain n / 2 when n is even.

Dividing random even integers by 2, results in a 50/50 chance of being even or odd.

Starting any sequence with a random integer, at any given point within the sequence, if there are as many even integers as odd, the value for the next integer will be lower than the starting value of (n). The longer the sequence, the greater allowable disparity between the number of even and odd integers for (n) to be lower than its original value. This demonstrates a natural decay. Since each integer has a 50/50 chance of being even or odd, coupled with the natural decay, all values for (n) will eventually reach 1.


Scratching my head, wondering why it's called a conjecture...

© Copyright 2010 ProjectPrimality.blogspot.com

Last update: September 16, 2010

No comments: