Follow-up to the previous Collatz conjecture post

 After reflection, it is in fact the case that if there is a loop that begins with a number other than 1, call it z, that the sequence of operations that cause z to loop around to z will in fact converge on z regardless of the number chosen as a starting point.  The number z is encoded in the sequence of operations and if that sequence is repeated any starting number will converge on Z.

The combination of operations that make up the Collatz conjecture, i.e multiplying odd numbers by three and adding 1 or dividing even numbers by zero, can be described by a linear function of the form

y = ax + b. 

More accurately, for the Collatz conjecture,  y = (ax + b)/c where a is equal to 3^N, where N is the number of odd numbers that appear in the loop, and c = s^ m, and represents the total number of divisions by 2 performed in traversing the loop.  The term b is a number that is determined solely by the sequence of operations and is only implicitly dependent on z. The equation above describes a line with slope a/c and y intercept of b/c.  This line will intersect the line y = x at the point (z,z); thus for any sequence that can be written in the form above, any starting number n will converge on the value b/(c-a). Also, all sequences, regardless of whether they terminate in a loop containing 1 or some other number, will converge on a number b/(c-a). For example, the Collatz sequence that begins with number 7 terminates at 1, can be described by the equation (243x + 347)/2048.  If you begin with any number n and repeat the sequence many times, the result will converge on 347/(2048-243) = 0.192243.  Likewise, if you take the sequence describing the loop based on 1; (3x+1)/4, begin with any number, not necessarily an integer and substitute each result back into the equation, the results will converge on 1.

This result is so because any number less than z will increase when substituted into an equation that loops, and any number greater than z will decrease..  This can be shown graphically.

Some thoughts on the Collatz conjecture

 

Problem:

 

One of the unanswered questions regarding the Collatz conjecture is whether there are any loops other than the sequence 1, 4, 2. The following argument suggests there are not.

 

Procedure:

 

Write any number in binary form, to make the calculations easier. Now divide the binary number at some random point into two parts; a “high” part and a low part. For example, the number 15 is 1111 binary and we can divide it 3 possible ways: a high part of 1 x (2^3) and low part of 7; 3x(2^2) and 3; or 7 x (2^1) and 1.

The original number is just the high part plus the low part. We make two columns, one below the high part and one below the low part.  Now the operation of (3x +1)/2 is performed by multiplying the value in the left column by 3/2 and performing the (3x+1)/2 operation on the right. For example if we start with 15 and divide it as 1100 and 11 binary, or 12 and 3 decimal for the left and right columns, we would perform the first (3x+1)/2 by multiplying 12 by 3/2 giving 18, and the right column would have (3(3)+1)/2 = 5. The sum is 23, the same answer we get if we just use (3(15)+1)/2=23.  We use the sum of the columns to decide whether we multiply by 3 and add 1 or divide by 2. Fractions are allowed in the two columns, and we can perform the (3x+1)/2 operation on even numbers in the right column. This process works for any starting number.

 

We notice a very significant characteristic of this approach: the ratio of the number in the right column to the ratio of the number in the left column increases as the process continues, but neither column ever reaches zero.  Also, once the process applied to the original number converges to whatever number the procedure produces we can continue the process indefinitely.  For example, if the starting number is 7 and we divide it as 1 x (2^2) +3, when we get to 1, the number in the left column will be 243/512, and in the right 269/512. We can continue the process. If we just used the number 1 we would get back the number 1, which does not tell us much. However, if we apply the same operations to the two columns, after one iteration we get 729/2048 in the left column and 1319/2048 in the right column. The sum is still 1.

 

Notice however that the ratio of the value in the right column to that in the left continues to increase, meaning that the right column eventually converges to 1, i.e. the same number to which the original number (15) converges. This is so because the operation (3x+1)/4 produces a smaller number if  x>1  and a larger number for x<1.

 

Argument:

 

If a there is a number, B  not equal to one, where B is the smallest odd integer in a loop, then if we perform the series of operations dictated by the Collatz conjecture we will arrive back at B.  Now if we write B as a binary number as above and choose an arbitrary point at which to divide into H*(2^N) + L, where the first number is the first element in the left column and L is the first element in the right, we perform the series of operations until the sum arrives back at B. HOWEVER, when we get back at B the values in the left and right columns will be different than when we started, AND the ratio of the value in the right column to that of the left will be higher than the ratio when we first started.  We continue this process any number of times we wish.  If there is in fact a number B such that it is part of a loop that does not converge to 1, the sums of the values in the left and right columns will also loop back to B, but with the right column becoming progressively larger than the left.  This means that the right column must converge to B.

 

NOW the sequence of operations is the same whenever we start with B, and is determined by B. BUT the choice of the number in the right column depends on where we arbitrarily decide to divide the original number.  We could have divided the binary number between the 1^st and second digit, or the 4^th and 5^th, or anywhere such that we had at least one 1 in each column.

 

This means that multiple numbers, using the exact same sequence of operations must converge to B, if such a loop exists.  This implies that if we start, in the most extreme case with 1 in the right column, the sequence of operations that caused B to loop back to B will also cause 1 to converge to B.  This seems to imply a contradiction: if you perform the same sequence of operations on different starting numbers, they nonetheless converge to the same end point.  Either that end point must be the same for all starting numbers (e.g. 1), or the sequence of operations that causes B to loop back on B (if there are any) will converge to B for any starting number.