Collatz conjecture

[tomtom2357]

For anyone who has not heard of the collatz conjecture before, the collatz conjecture states that if you take any number, and if it is even, divide by 2, and if it is odd, multiply by three, add 1, then divide by two, and if you repeat this procedure long enough, eventually any positive integer will end up at 1. There are two ways this could fail, by the sequence of a number going to infinity, or by the number entering a cycle of finite length. I am investigating the latter option. In particular, I am trying to prove the non-existence of a 1-cycle, where there are m iterations of x->(3x+1)/2, and n applications of x->x/2. I have proved that the existence of this cycle for a given starting number x implies that 2^m+n/3ⁿ<=1+(1/x)<=1+(1/(2^m-1)) (because x>=2^m-1). Taking the logarithm of both sides to base 2 gives: m+n-log₂(3)n<=m-log₂(2^m-1)<1/(2^m-1). Is this possible? If I can prove that this is impossible for large enough n, then I will have disproved the existence of a 1-cycle.

[notzeb]

For anyone who has not heard of the collatz conjecture before, the collatz conjecture states that if you take any number, and if it is even, divide by 2, and if it is odd, multiply by three, add 1, then divide by two, and if you repeat this procedure long enough, eventually any positive integer will end up at 1. There are two ways this could fail, by the sequence of a number going to infinity, or by the number entering a cycle of finite length. I am investigating the latter option. In particular, I am trying to prove the non-existence of a 1-cycle, where there are m iterations of x->(3x+1)/2, and n applications of x->x/2. I have proved that the existence of this cycle for a given starting number x implies that 2^m+n/3ⁿ<=1+(1/x)<=1+(1/(2^m-1)) (because x>=2^m-1). Taking the logarithm of both sides to base 2 gives: m+n-log₂(3)n<=m-log₂(2^m-1)<1/(2^m-1). Is this possible? If I can prove that this is impossible, then I will have disproved the existence of a 1-cycle.

Your method should work after using a little bit of the theory of Diophantine approximation. I think that for example Baker's theory of linear forms of logarithms should be way more than enough to handle this (especially seeing as his theory is meant to apply to more general questions involving logarithms of large collections of algebraic numbers.)

The result you are trying to prove has already been proved though: http://en.wikipedia.org/wiki/Collatz_co ... nnot_occur

[tomtom2357]

I know that it has been proved before, I just thought it would be a good exercise for me to try to prove it. If I can prove that a 1-cycle cannot occur, then I am that much closer to proving that no cycles can occur.

Also, I am working on an idea to show that the lowest counter-example is very high. My idea involves assuming that the lowest counter-example is x, and that x=Sum_i=2ⁿ2^c(i), then trying to prove things about n and the c(i). For example, it is relatively easy to show that n>=6, c(1)=0, c(2)=1, and 2<=c(3)<=3. It only takes a finite number of cases to show that n must be larger than a particular value. Therefore, any computer program testing the collatz conjecture can also find the amount of 1's in the binary expansion for the given number being tested, and if it is smaller than the proven minimum value of n, then the tester can immediately say that the sequence converges to 1 for that number.

[mfb]

m+n-log₂(3)n<=m-log₂(2^m-1)<1/(2^m-1). Is this possible?

m-log_2(2^m-1) = m- m - log_2(1-2^{-m}) = 2^{-m} - 2^{-2m-1} - O(2^{-3m})

\frac{1}{2^m-1} = 2^{-m} \frac{1}{1-2^{-m}} = 2^{-m} + 2^{-2m} - O(2^{-3m})

For large m, the second inequality is always true. Looking at the Taylor series, I think it is always true.

The first one can be satisfied if n is large enough.

[tomtom2357]

The second inequality is always true. I am using the fact that ln(x)<x-1, which is derived from the maclaurin series for e^x-1, taken at x=1.

[notzeb]

oh, hold on. For some reason I was assuming that you had proven that m+n-log₂(3)n was also positive. If you don't have that, you can't do anything....

[tomtom2357]

I have proved that m+n-log₂(3) is always positive. For the 1-cycle to actually be a cycle, 2^m+n/3^m=1+(2ⁿ-1)/(2ⁿx+1)>1, so 2^m+n/3^m>1, so m+n-log₂(3)n>0.

[notzeb]

Ok, good.

If we blindly apply the results stated in http://en.wikipedia.org/wiki/Linear_forms_in_logarithms as a blackbox, we can see that

log((m+n)log(2) - nlog(3)) > -18*3!*2^3*32^4*log(4)^3*log(m+n) > -3*10^9*log(m+n), so

m+n - log₂(3)n > (m+n)^{-3*10^9}/log(2), and for large enough m and n this will be greater than 1/(2^m-1).

Of course, it would be more satisfying to find a low-tech method to get the same result (and hopefully with a better bound!) But at least now you know whether or not it is possible.

[CCC]

I've been thinking about this conjecture... and I think I may be partway to a proof, though under completely different lines to the original poster.

First of all, I'll take a slightly modified version of the conjecture. If x is even, I divide by two; if x is odd, I multiply by three and add one. (This always results in an even number, so in the following step I will complete the division by two). Any sequence that ends up at 1 in my modified version of the conjecture will always end up at 1 in the original conjecture and vice versa (I just add some extra numbers to the sequence).

Now I write all my numbers in binary. The "if x is even, divide by two" step can now be rewritten as "discard all the zeros that follow the last 1". Importantly, this step does not chance the number, or relative position, of the ones. Now, I can consider the binary number to consist of a number of strings of ones, seperated by e number of strings of zeros (where each string of digits contains at least one of that digit). For example, 27 (decimal) is 11011; a string of two ones, followed by a string of one zero, followed by a string of two ones.

Now, consider the "multiply be three and add one" step.

If I multiply a string of ones by three, I get:

1 -> 11
11 -> 1001
111 -> 10101
1111 -> 101101
11111 -> 1011101
111...(n ones)...111 -> 10111...(n-2 ones)...11101

With the exception of a single 1 all on its own, this has the following important properties:
- The number of ones is not increased
- The resulting number ends "01"
- The resulting number is exactly two digits longer than the original number

Since the resulting number is exactly two digits longer than the original number, the only effect that one string of 1s can have on the string of ones to the left of it is to add 1. Since the number ends 01 (except in the case of a single one), the only effect of adding 1 is to change the 01 into 10, which does not increase the total number of ones in the binary number (in fact, it decreases the number of ones, since the initial 1 of the rightmost string and the final 1 of the leftmost string combine to end up with only one 1). In fact, the only way to increase the total number of ones in the binary representation is to have a string consisting of a single 1. (The case of the single 1 will have to be handled seperately - I'm not sure how to do that, hence my proof is incomplete).

Now, the complete number must end in a string of ones. If that final string is of length n (where n>1), then multiplying by 3 turns it into 10111...(n-2 ones)...11101. Adding one, gives 10111...(n-1 ones)...1110. In the next step, I eliminate that final zero, ending up with a number that ends with a string of n-1 ones. Eventually, therefore, I will end up with a number that ends ...01. At this point, multiplying by three (...11) and adding one will allow me to possibly eliminate several ones at once. (Example: 101*11 = 1111. Add one, and I get 10000, or 16, which only contains a single 1 and this quickly reduces to 1 via elimination of zeros).

--------------

Aside from the question of loops, there's the question of a sequence that grows to infinity. When considering such a sequence, it's important to consider the first few digits of the number. It can start with either 11 or 10.

If it starts "10...", then multiplication by 3 results in a number, one digit longer, which starts "11...". (Addition of one can be ignored insofar as the number of digits is concerned. While it is possible that addition of one can result in an extra digit, if it does, it will result in a number consisting of a single 1 followed by a string of zeros, which will be quickly reduced to 1 and thus cannot grow to infinity). This number must end in a zero; when this is removed, the number of digits will drop back to its oringal value.

If it starts with "11...", then multiplication by three will result in a value that starts "10..." and is two digits longer. The following step must remove at least one digit (and may remove more), but that's still a potential net gain of one digit.

In every four steps, therefore, I can gain at most one digit. If I follow my starting string of ones with a string of n zeros, then a string of n ones, I can ensure that the number will gain one digit every four steps for at least 2n steps, for any finite n. Thus, I can construct a number that takes a minimum of an arbitrary number of steps before reaching 1; but I have neither proven that it can reach infinity nor that it can't.

[tomtom2357]

Well, the problem with that is that I could already construct numbers that take an arbitrarily long time to reach one. What would be good is if you could construct numbers such that the ratio of the time to reach one and the log of the number is arbitrarily large. To try to construct such a number, you would have to find a number that cannot be reached by smaller numbers. Therefore, it wouldn't be 2(mod 3) or anything like that. Choosing a multiple of three would be a good idea.

[CCC]

Choosing a multiple of three would be a good idea.

Hmmm. A multiple of three cannot be part of a loop; 3x+1 can never lead to a multiple of 3, and x/2 can only lead to a multiple of 3 if starting from a multiple of three. Thus, no multiple of 3 can be reached from any smaller number at any point, nor can it be reached from itself; it can only be reached from higher, even multiples of three. I'm not entirely sure how that helps, though.

--------------

I've been putting a but more thought into the special case of a number that's a continual string of ones in binary; that is, a number of the form 2ⁿ-1 for arbitrary n. It is odd, so multiplying by 3 gives 3*2ⁿ-3; add one, 3*2ⁿ-2; halve it, 3*2^n-1-1. Continuing this process n times leads me to a result of 3ⁿ-1. This is itself even, so the next step is to halve it, but after that it gets harder to predict (for n=2, you halve it until it hits one; for n=3, you jump around a bit before hitting 1; for n=4, it collapses quickly; for n=5 you've got somewhere around 96 steps to go before getting there).

In base 3, this number takes the form of n 2s in a row. Halve that; and the number consists of n ones in a row.. If n is odd, this is an odd number; multiply by 3 and add 1 (in base 3, this leads to a string of (n+1) ones). You now have a number consisting of an even number of ones all in a row in base 3; halve it, to get a (n-1)-digit (or n-digit if n was odd) number of the form 202020....020202. This can be halved again: 101010...010101. This may be odd or even, depending on the number of ones; it's an odd base, and therefore the number is even if and only if the sum of the digits is an even number...

[tomtom2357]

Choosing a multiple of three would be a good idea.

Hmmm. A multiple of three cannot be part of a loop; 3x+1 can never lead to a multiple of 3, and x/2 can only lead to a multiple of 3 if starting from a multiple of three. Thus, no multiple of 3 can be reached from any smaller number at any point, nor can it be reached from itself; it can only be reached from higher, even multiples of three. I'm not entirely sure how that helps, though.

--------------

I've been putting a but more thought into the special case of a number that's a continual string of ones in binary; that is, a number of the form 2ⁿ-1 for arbitrary n. It is odd, so multiplying by 3 gives 3*2ⁿ-3; add one, 3*2ⁿ-2; halve it, 3*2^n-1-1. Continuing this process n times leads me to a result of 3ⁿ-1. This is itself even, so the next step is to halve it, but after that it gets harder to predict (for n=2, you halve it until it hits one; for n=3, you jump around a bit before hitting 1; for n=4, it collapses quickly; for n=5 you've got somewhere around 96 steps to go before getting there).

In base 3, this number takes the form of n 2s in a row. Halve that; and the number consists of n ones in a row.. If n is odd, this is an odd number; multiply by 3 and add 1 (in base 3, this leads to a string of (n+1) ones). You now have a number consisting of an even number of ones all in a row in base 3; halve it, to get a (n-1)-digit (or n-digit if n was odd) number of the form 202020....020202. This can be halved again: 101010...010101. This may be odd or even, depending on the number of ones; it's an odd base, and therefore the number is even if and only if the sum of the digits is an even number...

Looking at this algebraically, 2ⁿ-1 goes to (3ⁿ-1)/2 after n 'up' steps and one 'down' step. If n is even, then you can divide by 4 to get (3ⁿ-1)/8. If n is odd, multiply by 3 and add 1, then divide by 2 and get (3ⁿ⁺¹-1)/4. This is divisible by two, so you get (3ⁿ⁺¹-1)/8. Notice that 2ⁿ goes to the same number as 2ⁿ⁺¹, if n is odd. Therefore, we only have to consider the case where n is odd. After that, I don't fully understand what happens, except that if n is -1(mod 2^a), then after those first n+3 steps, there are another a-1 down steps.