Friday, 1 June 2012

Revisited: The Collatz Conjecture 5n+1

In a previous post, I've outlined and explained the Collatz conjecture - take a real, positive number, and if it's odd multiply by three and add one; if it's even, divide by two, and repeat until you reach one.  The sequence terminates at 1, although it's not yet been proved for all numbers (just a lot of them).


But what happens if we change the rules of the sequence, and divide by two for even numbers, but multiply by FIVE and add one for odd numbers?  So instead of 3n+1 the next term is 5n+1.  My searching on the internet has not identified anybody who has previously followed this line of research, so I have decided to pursue it.

A variation on the Collatz Conjecture:  5n+1



For the Collatz conjecture, all series reach one (or so it seems, there's no formal proof yet).  However, if we follow a new algorithm, and multiply by five and add one for the odd numbers, we enter one of a number of different scenarios (I've identified four,but this is not conclusive or exhaustive).


Firstly, trying this variation of the Collatz series, starting with 1.  Seems like a good place to start, and it's not as trivial as the original series.  Starting with 1 produces a loop:

1 -- 6 -- 3 -- 16 -- 8 -- 4 -- 2 -- 1 which is the simplest loop, "Loop A" and contains 1, 2, 3 and 4.



Secondly:  (5 -- 26 --) 13 -- 66 -- 33 -- 166 -- 83 -- 416 -- 208 -- 104 -- 52 -- 26 -- 13 which is another loop, "Loop B"


So far, this covers 1, 2, 3, 4, 5 and 6, 8, and 10 (which divides by two to enter Loop B).

Thirdly:  However, something that I found strange and unexpected happens if we start with 11 (which goes through 7 after four steps)






Observations:

*  The series does not appear to enter a loop, it just keeps growing and growing - although 
I can't prove it.
*  The odd numbers that series includes are either prime - shown in red - or semi-prime (only having prime factors), shown in blue.
*  The first non-prime in the series is 9, which is the square of a prime (3).

The fourth variation I've seen starts with 17.  It seems that there's no pattern for other odd numbers which have not been in the previous loops, so I'm working through them.  For example, 15 enters the growing sequence at 46 (in the top row of the diagram of the sequence shown above), but 17 enters a different loop, Loop C.

Summary:

The 5n+1 variation of the Collatz conjecture leads to one of four situations:

Loop A:  1 - 6 - 3 - 16 - 8 - 4 - 2 - 1

Loop B:   (5 - 26 -) 13 - 66 - 33 - 166 - 83 - 416 - 208 - 104 - 52 - 26 - 13
Loop C:  17 - 86 - 43 - 216 - 108 - 54 - 27 - 136 - 68 - 34 - 17
Sequence:  Starting with 11 (and including 7) - limitless growth (it does not appear to enter a loop)


Future developments: 

*  To look for additional loops, continuing to review the prime numbers not already covered.
*  To try another variation on the Collatz Conjecture, for example, 5n-1 instead of 5n+1.  Clearly, 5n+1 has the scope to grow very rapidly with almost no chance of decreasing, and the only observations that can be made are on the numbers that the sequence goes through.

4 comments:

  1. I would look up Jeffrey Lagarias and his annotated bibliography of people pursuing the Collatz Conjecture. Url is here:

    http://www.math.lsa.umich.edu/~lagarias/3x+1.html

    There are definitely papers cited in these papers that discuss 3x + d for various d.

    Best of luck!

    ReplyDelete
  2. In loop B, 104 is followed by 52.

    ReplyDelete
  3. In loop B, 5 is not part of the loop. and you should identify loops with their smallest element, which is 13 in loop B.

    ReplyDelete
  4. Hello, anonymous commenter - thanks for your comments, and I have made the corrections you identified.

    ReplyDelete