3*

3*x+1

The 3*x+1 problem is a number theory problem. Take any positive integer. If it's odd, multiply it by 3 and add 1. If it's even divide it by 2. Do you always get 1? Or with a negative number, will you always get -1, -5 or -17?

In my research I've discovered some interesting facts, nothing really Earth shattering but interesting none the less. For example, I "know" why 1, -1 and -5 are cycles and why other numbers are not. It doesn't help the question of if 1 is the only cycle. -17 is interesting because it differs from 1, -1 and -5 (see below) and opens up the possibility of more cycles like it.

The idea is solving for the next number in the sequence. The first assumption is that the next number is always the next odd number, so the first number must also be odd. So, the next number after the start will be x1 = (3*x0 + 1)/2^m where m is a positive integer. m is the integer exponent of the number 3*x0+1 with respect for 2. Hence, (3*x0 + 1)/2^m will be an odd number.

So, x0 = (-1 + 2^m*x1)/3. If a number is to cycle to itself, then it must satisfy this equation when in the place of x0 and x1 for some positive integer m.

For example, when x0=x1=1. 1 = (-1 + 2^m*1)/3. If we set m to 2 then we get 1 = 1. The same works for x0=x1=-1.

So, placing x in for our number:

x = (3*x+1)/2^m
x = 1/(-3 + 2^m)

Any whole number that is produced by that sequence for any positive integer value of m will by a first order cycle. Now, let's take this to the next step, for a number that cycles to itself after two iterations. x0 = (-1 + 2^m*x1)/3 in terms of x:

x = (3*(3*x+1)/2^m+1)/2^n.
(3 + 2^m)/(-9 + 2^(m + n))

For a number to be a cycle of the third order, it must satisfy this equation for positive integers m,n and o:

x = (3*(3*(3*x+1)/2^m+1)/2^n+1)/2^o
x = (9 + 3*2^m + 2^(m + n))/(-27 + 2^(m + n + o))

The pattern is pretty obvious: x =

Where d is the degree or order, starting with 0 for first order and n is the integer exponents (m, n, o etc. above). So, now we have an equation that will generate all cycles if we can figure out what values to plug in for all the integer exponents (the n's) that will produce a whole number. An easy way to get whole numbers is if the bottom is 1 or -1. So, for what values is |2^m - 3^n| = 1 for positive integers m and n? In the form (m,n), the only values are (1,1), (2,1) and (3,2). And guess what! Those values map to the cycles 1, -1 and -5 in that order. n a sense, these are the 'trivial' cycles because they occur from such a simple form of the equation.

So, take a set that is d+1 long of values, plug it in to the above and if it produces a whole number, then that number is a cycle of d+1 length. An interesting thing to note is that a first order cycle is also a second, third, forth, etc. because the cycle continues. So -5 is a second, fourth and sixth order cycle as well.

A 'non-trivial' cycle would then be a cycle that occurs when |2^m - 3^n| is not equal to 1 or -1 and hence it divides the top evenly. It could be easy to dismiss this and say that from the complexity, it would never occur, but it does occur with the cycle -17.

When the set for n is {1,1,1,2,1,1,4}, then the equation above produces -17. "Shift" all the terms to the left or right and the other members of the cycle are produced.

So, what exactly can be done with this formula? Since there is a limited amount of values for the set n that make the top part greater than the bottom, it is possible to prove that there are no cycles of that order. Unfortunately, as the degree increases, so does the number of values to test and it becomes impractical over the tenth degree or so. However, it can aid in some other things, such as the maximum number that can be in a certain degree cycle.

I'm not exactly how to prove this except through demonstration that the equation above will produce the largest number (or largest negative number) when all the set of n contains all 1's except n0. This kind of makes sense since if a number in n is 1 is saying that the number produced by 3*x+1 will only be divisible by 2 once and hence will be bigger than 3*x+1. If this continues, the number continues to grow. So, plugging the new set into the equation we get:

So, now we need to determine for what values of n0 the above is greatest for. This occurs to the left and right of the asymptote, so when 2^(d+n0)-3^(1+d) = 0. Solve for n0 and using the floor function, we obtain these formulas:

For the maximum postive integer:

For the maximum negative integer:

So, of what use are these? If it is possible to prove that all the numbers below (or above in the negative case) do not cycle to an already known cycle, then there is no new cycle of length d+1. So, it is possible to prove, knowing that all numbers up to 2^50 have been tested, that there can be no cycle of 80 numbers or less. This is nothing compared to the already proven fact that there are no cycles of 250,000 or less but it's a start. Note however that these functions do not increase linearly. There's a bigger chance for fifth order cycles (d = 4) than there is for sixth order (d = 5).

Unfortunately, at least with this way of thinking, there is no way to get a minimum number for a positive cycle, mainly because one can plug in any size integer into the last element in n (n sub d). Hence the equation will always go to zero.

So there it is, the majority of it anyway. I hope it helps someone think about this problem in a new way, or to simply put a smile on your face and think Ha! What a geek!