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.

In the "Collatz conjecture" we want to find a number that makes the process go on forever never reaching 1. I want to find an example - a problem like "Collatz conjecture" but where you have to find a number that makes the process stops (the opposite situation, where you know alot of numbers that makes the process go on forever).

share|improve this question
    
I want to find a problem like the collatz conjecture, but where in most cases the sequence doesn't reach a given number, but we haven't proven it yet. –  Ilikenumbers Dec 8 '11 at 16:42
2  
The question makes sense to me. Here is an illustration to show what something like this could be. Consider the recursion $x \mapsto x/2$ for $x$ even, $x \mapsto 5x+1$ for $x$ odd. Nonrigorous arguments predict that this sequence should go to infinity for most initial conditions. In this case, it is pretty easy to find some loops, for example, $1 \to 6 \to 3 \to 16 \to 8 \to 4 \to 2 \to 1$. But one could imagine a recursion for which the heuristics predict that most values will escape to $\infty$, and for which it is open to find any loops. I think this is what Ilikenumbers wants. –  David Speyer Dec 8 '11 at 17:00
2  
You might like to look at this answer of mine math.stackexchange.com/questions/14569/the-5n1-problem/… –  David Speyer Dec 8 '11 at 17:01

2 Answers 2

The trouble with this question (or at least with my understanding of it) is that, the more ignorant the answerer, the easier it is to answer. For example, consider the recursion $$x \mapsto \begin{cases} x/2 & x \ \mbox{even} \\ 17x+3 & x \ \mbox{odd} \end{cases}.$$ Does it have any cycles? I don't know! Five minutes with pencil and paper didn't find any, but I see no obvious reason that it couldn't.

If I think about it for half an hour, I might find a cycle. But then this wouldn't be a good answer to your question anymore, so I'm going to stop thinking and post it.

share|improve this answer

To add examples to @David Speyer's answer:
We look at odd numbers a only and formulate a transformation of one step as $\small T(a;A)= {a \cdot 17 + 3 \over 2^A } $ Two steps should then be $\small T(a;A,B)= {{a \cdot 17 +3 \over 2^A }\cdot 17 + 3 \over 2^B} $ and so on.

Now if we look at a cycle, we should have solutions to the following examples:

  1. $\small a = {a \cdot 17 +3 \over 2^A } \qquad$ or $\qquad \small 2^A = 17 + {3 \over a } \qquad$ for some allowed a and A.
    It is obvious, that no solution for a one-step-cycle exists
    But we see immediately, that we have one in the negative domain:
    Because $\small 2^4 = 17 + {3 \over -3} = 16 $ we have the cycle $\Tiny (-3)\cdot 17 + 3 =-48 \to -48/2 = -24 \to -24/2=-12 \to -12/2=-6 \to -6/2=-3 \to \ldots$.

  2. $\small b = {a \cdot 17 +3 \over 2^A } \qquad a = {b \cdot 17 +3 \over 2^B } \qquad $
    or $\qquad \small a \cdot b = {a \cdot 17 +3 \over 2^A } \cdot {b \cdot 17 +3 \over 2^B } \qquad $
    or $\qquad \small 2^{A+B} = ( 17 + {3 \over a })(17+{3 \over b }) \qquad$ for some allowed a,b,A and B.
    It is obvious, that for the smallest a,b (a=b=1) we have $\small 20 \cdot 20=400$ and for the greatest a,b (a=b->oo) we have $\small 17 \cdot 17 = 289 $ and there is no perfect power of 2 between 289 and 400, so there is also no 2-step cycle.

  3. Any three-step-cycle must satisfy the analoguous condition:
    $\qquad \small 2^{A+B+C} = ( 17 + {3 \over a })(17+{3 \over b })(17+{3 \over b }) \qquad$ for some allowed a,b,c,A,B and C.
    Again, between $\small 17^3=4913 \ldots 20^3=8000 $ there is no perfect power of 2 so also the 3-step-cycle does not exist.

  4. This can analoguously extended to the question more-step cycles; however the criteria become weaker as the number of steps increases over N=3. . At least, by the perfect power-of-2 condition we get always an upper bound for the minimal member a of an assumed cycle so we need only brute-force-check smaller numbers a than this upper bound.

  5. Similarly as R. Steiner, J. Simons and B.de Weger have done this with the consideration of certain simple types of cycles, one can now look at the question of existence of the "1-cycle": arbitrary many ascending steps, one descending step. We look only at ascending steps with exponent A=1. Then , for N steps we get
    $\small \begin{array} {rlll} a_1 &= & {a_0 \cdot 17 + 3\over 2 } \\ a_2 &= & {a_0 \cdot 17^2 + 17 \cdot 3 + 2\cdot 3\over 2^2 } \\ a_3 &= & {a_0 \cdot 17^3 + 17^2 \cdot 3 + 17\cdot 2\cdot 3 + 2^2\cdot 3 \over 2^3 } = {a_0 \cdot 17^3 + 3 \cdot {(17^3 - 2^3) \over 17-2} \over 2^3} = a_0 { 17^3 \over 2^3 }+ {3 \over 15} {17^3 - 2^3 \over 2^3} \\ \ldots \\ &&\Tiny \text{ now let L=N-1, S=L+A = N-1+A } \small \\ a_L &=& a_0 { 17^L \over 2^L }+ {3 \over 15} {17^L - 2^L \over 2^L} \\ a_0 &=& {a_L \cdot 17 + 3 \over 2^A}= a_0 { 17^N \over 2^S }+ {3 \over 15} {17^N - 2^N \over 2^S } \\ \text{ and } \\ a_0 &=& {1 \over 5} {17^N - 2^N \over 2^S-17^N } = {1 \over 5} ( 2^N{ 2^{A-1} -1 \over 2^S-17^N }-1) \\ \end{array} $
    and we can check, whether for any N there is an S which makes $\small 2^S \gt 17^N $ and still allows positive odd $\small a_0 $

These are just some initial steps to discuss the possibility of the 17n+3-cycle. At least some more initial insight can be won by short paper&pencil-operations...

share|improve this answer

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.