Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Among the Collatz conjecture we have other "similar" problems that are solved and have repeating cycles.

$5n+1$ has the repeating cycle $13, 66, 33, 166, 83, 416, 208, 104, 52, 26$, with a length of $10$

The $5n+1$ Problem

$3n-1$ has the repeating cycle $5,14,7,20,10$

If there is a repeating cycle, must there its smallest length be aprox. of size $2k$, where the algorithm is $kn\pm1$ for odd numbers?

Also, are the following diagrams meaningful?

http://img839.imageshack.us/img839/5650/selection002xv.png

http://img837.imageshack.us/img837/7831/selection003x.png

Added: First row of "Collatz" number diagram can be seen as N, second as 2N-1, third as 3N-1

Adiition number 2: If you look at diagram a), you can see that positional value y betwen 2x in forth row and x in third row is given by formula 4y-1

http://img839.imageshack.us/img839/5650/selection002xv.png

2 in column 1 => 4 in column 3

5 in column 3 => 10 in column 11

. . .

14 in column 5 => 28 in column 19

Added 27.12.2012. at 18.20

Another very naive,probably stupid but do not care subquestion? Finding some solution for (3n-1)/2 is the same as solving sistem of equations with 2 uknowns. http://www.wolframalpha.com/input/?i=2x%2B1%3D3y%2B1%2C+2y%2B1%3D%283x%2B1%29%2F2 . Look at last diagram: http://img837.imageshack.us/img837/7831/selection003x.png. Can there be some generality written?

share|improve this question
add comment

3 Answers 3

up vote 1 down vote accepted

There is a bit of structure which I think is not trivial. It is already mentioned in the wikipedia-article, that cycles of certain forms could be disproved. (This might remind of the situation with the Fermat's last theorem in the time of Kummer, where finitely many prime exponents had already been excluded, and, I think to recall corrctly, by the Sophie Germain proof, also an infinite class of prime exponents).
The proofs of Ray Steiner[2,1977], and later Simons/deWeger,2000 and 2002 say, that there are no cycles of the form "uuuu....uuuddd...ddd", where u means upwards and d downward steps and all d 's are right of the u 's - and this is meant for any, thus unbounded, length. Then Simons proved, there are no cycles of the form "uuu...ddduuu...dddd" , which could be understood as concatenation of two of the first (now:) partial cycles.

To give it a name, they called the the first one the "1-cycle" and the concatenations as "m-cycles" where Simons/deWeger could proceed to the disproof of m-cycles of up to m=68.


A very general tool for the discussion of cycles (and the possible disproof for certain finite lengthes) follows from the following observation:

define the one step-transformation for some $w n + 1$ - problem in the following shorter form $$ b = {(w a + 1 ) \over 2^A} $$ over the odd numbers a and b, where the exponent $A$ is uniquely chosen to make b an odd integer. Then consider the sequence of steps $$ b = {(w a + 1 ) \over 2^A} \qquad c = {(w b + 1 ) \over 2^B} \qquad d = {(w c + 1 ) \over 2^C} \qquad e = {(w d + 1 ) \over 2^D} \qquad $$ where we have a cycle, if we finally have $a = e$ Obviously the product of the numbers a,b,c,d must equal the product of its transforms, so we ask whether -with asome a,b,c,d, we can find equality $$ bcda \overset{?}{=} ({w a + 1 \over 2^A})({w b + 1 \over 2^B})({w c + 1 \over 2^C})({w d + 1 \over 2^D})$$ (whose generalization to as many steps as wished is obvious). Then rearranging and cancelling gives $$ 2^{A+B+C+D} \overset{?}{=} (w+ \frac 1a)(w+ \frac 1b)(w+ \frac 1c)(w+ \frac 1d) \tag {1} $$ and writing S for the sum of exponents and N for the number of steps we can rewrite the question of existence of the cycle whether we can have equality $$ 2^S \overset{?}{=} w^N (1+ \frac 1{wa})(1+ \frac 1{wb})(1+ \frac 1{wc})(1+ \frac 1{wd}) \tag 2 $$ from where then $$ w^N \lt 2^S \overset{?}{=} w^N(1+z) $$ where z is small, and decreases when a,b,c,d increase. This imposes the general problem of distance of perfect powers; for the example case w=3 we can disprove for instance the 4-step-cycle:
We assume a,b,c,d the smallest and different odd values a=5,b=7,c=11,d=13 . We get $$ 2^S \overset{?}{=} (3+ \frac 15)(3+ \frac 17)(3+ \frac 1{11})(3+ \frac 1{13}) \\ 2^S \overset{?}{=} 81 + 27( \frac 15 + \frac 17+\frac 1{11}+\frac 1{13}) + 9( \cdots) + 3(\cdots) + {1 \over 5 \cdot 7 \cdot 11 \cdot 13} $$ and we see, that the rhs can never be as large as the next perfect power of 2 above $3^4$ because we must then have $2^S = 128$ and actually $$ \begin{eqnarray} 2^S &=&128 & \gt && 81 + 27( \frac 15 + \frac 17+\frac 1{11}+\frac 1{13}) + \varepsilon\\ & & & & \sim & 81 + 14.64... \end{eqnarray}$$ even if we increase the assumed values for a,b,c,d up to some trillion and try whether we can find a solution for the 4-step-cycle there...

In the same way this can be done for more steps, and for many number-of-steps this simple tool suffices for the disproof of the existence of a cycle.

Similarly this can be done for other instances of w; and especially if the numbers a,b,c,d,... are in a certain progression (like it is with the structure of the 1-cycle) we can find/identify, or prove the nonexistence of cycles. In the $3n+1$ the 1-cycle defines the progression in $a_1,a_1,a_2,...,a_N$ as $a_{k+1} = a_k + (a_k+1)/2 $ and this suffices for the Steiner-proof (which uses results from the rational approximation of linear forms of logarithms).

Also, if we consider the $w n - 1$ - case, in (2) we simply replace the plus by the minus-sign. Note, then we find then for the $3 n - 1$-problem the cycles of the collatz-transform in the negative integers because then formula (1) and (2) for one,two and six steps give the respective solutions.


But it is as mentioned above: this reminds me a bit of the FLT-problem in the early 20'th century, when isolated prime-exponents could be excluded, and even infinite subclasses, but not yet the whole set of possible primes.

[2] Steiner, R.P.; "A theorem on the syracuse problem", Proceedings of the 7th Manitoba Conference on Numerical Mathematics, pages 553–559, 1977

share|improve this answer
add comment

Nobody knows much of anything about the length of cycles for Collatz-type problems. After all, for all we know, the $3n+1$ problem could have a cycle of length $10^{100}$.

share|improve this answer
    
Are there any known nontrivial solutions to Collatz-type problems? –  Aaron Mazel-Gee Dec 26 '12 at 7:28
    
@Aaron, to the best of my knowledge, there is no non-trivial Collatz-type problem that has been completely solved. –  Gerry Myerson Dec 26 '12 at 7:34
add comment

If you take $k=2^m-1$, then the $kn+1$ problem maps $$1 \mapsto 2^m \mapsto 2^{m-1} \mapsto \cdots \mapsto 1.$$ In this case, the cycle length is $O(\log k)$. This is significantly different to $2k$. (A similar construction works for the $kn-1$ problem.)

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.