Implication for m-cycles in Collatz-type problems. - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-21T19:44:33Z http://mathoverflow.net/feeds/question/78124 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/78124/implication-for-m-cycles-in-collatz-type-problems Implication for m-cycles in Collatz-type problems. x1101011x 2011-10-14T12:15:56Z 2011-10-26T07:17:28Z <p><strong>Background</strong></p> <p>Consider Collatz-type problems of the form $an + 1$, where $a > 2$ is a positive, odd integer (e.g., $3n + 1$, $5n +1$, $7n + 1$, etc.). For convenience, automatically divide by two.</p> <p>The $3n + 1$ problem has a single known positive cycle $(1, 2)$. This cycle has period $2$, and the maximum value this cycle obtains differs from its minimum value by a power of two; that is $2 = 2 \cdot 1$.</p> <p>The $7n + 1$ problem has a positive cycle $(1, 4, 2)$. This cycle has period $3$, and the maximum value $4 = 2^2 \cdot 1$ is the minimum value multiplied by some power of two.</p> <p>The $5n + 1$ problem has three positive cycles: $(1, 3, 8, 4, 2)$, $(13, 33, 83, 208, 104, 52, 26)$, and $(17, 43, 108, 54, 27, 68, 34)$. The first cycle has period $5$, and its maximum $8 = 2^3 \cdot 1$. The other two cycles have period $7$, and <em>one</em> of these $7$-cycles has a maximum value $208 = 2^4 \cdot 13$.</p> <p><strong>Question</strong></p> <p>Is it known whether the existence of a positive $m$-cycle in such a Collatz-type problem implies the existence of a positive $m$-cycle such that its maximum $M$ and its minimum $\mu$ are related by $M = 2^k \mu$, for some $k \in \mathbb{N}$?</p> <p><strong>Edit</strong></p> <p>I used $m$-cycle to denote a cycle of period $m$ when it has already been standardized that $m$-cycle means a cycle with $m$ local minima. Either affirmative answer would serve just as well, however.</p> <p><em>Question 2</em></p> <p>Does the existence of a nontrivial (positive) cycle in the $3n+1$ problem imply the existence of a nontrivial (positive) cycle with maximum $M$ and minimum $m$ such that $M = 2^k m$, for some $k \in \mathbb{N}$?</p> <p>Note: If you prefer to work with the odd-only transformation, the condition would be that the maximum element transforms into the minimum element.</p> http://mathoverflow.net/questions/78124/implication-for-m-cycles-in-collatz-type-problems/78219#78219 Answer by Gottfried Helms for Implication for m-cycles in Collatz-type problems. Gottfried Helms 2011-10-15T19:01:58Z 2011-10-16T22:27:14Z <p>[update 2] Rereading the question after my own answer I note, that the doubly used symbol <em>m</em> for length of a series of collatz-transformation and the <em>m</em> for the minimal element (<em>M</em> for the maximal) irritated me and made me misunderstanding the question.<br> Anyway - the already given answer might be interesting for the background of my argument below as well as for further analysis of the problem at hand, so I'll leave it here for the cursory reader. </p> <p>To answer the real question : "is there some requirement, that in a cyclic Collatz-trajectory the maximal element is a perfect-power-of-2-multiple of the minimal element (<em>M=2^k m</em>) ?" : there is no such requirement to all my knowledge.<br> Also this would only define a single special case according to my notation for a cycle, which by convention might begin with the smallest element <em>m</em> : $\small m = T(m; A_1,A_2,\ldots ,A_{n-1},A_n)$.<br> Here your requirement simply means, that the maximal element <em>M</em> must occur after the transformation $\small A_{n-1}$ (whose exponent must thus equal <em>1</em>) frome where then the $\small A_n$ is the <em>k</em> in <em>M=2^k m</em> in your question. I didn't come across such a restriction in my own study or in any seen literature, and cannot see any reason for it (see derivations below). [end update 2]</p> <hr> <p>If you write a collatz-transformation this way $\small a_{k+1} = (3 a_k + 1)/2^A$ where <strong>A</strong> is the number of all following even (divide-by-2) steps, then also all $\small a_k$ must be odd. </p> <p>With this write for one transformation $\small a_{k+1} = T(a_k;A)$ and for more $\small a_{k+m} = T(a_k;A_1,A_2,\ldots,A_m)$.<br> For $\small A=1$ these steps are increasing and if $\small A>1$ the steps are decreasing. </p> <p>A cycle occurs, if $\small a_m=T(a_0;A_0,A_1,\ldots,A_m) = a_0$ thus $\small a_m = a_0$. </p> <p>Now let's look at two different types of cycles - the "general" one, where the exponents $\small A_k$ have no a priori restriction, and the "primitive" one, where all but the last $\small A_k = 1$, thus $\small a_0 = T(a_0;1,1,1,1,\ldots,1,A)$ with say $\small N-1$ times <em>1</em> and only one $\small A_{N} \gt 1$ </p> <p>For the primitive cycle of the length <em>N</em> the smallest element $\small a_0$ must have the form $\small a_0 = 2^{N-1} \cdot 2w - 1$ where <em>w</em> is some positive odd integer and that primitive cycle increases then up to $\small a_{N-1} = 3^{N-1}\cdot 2w-1$ from where it must decrease by a consecutive set of <em>A</em> "even" transformations. </p> <p>The <a href="http://en.wikipedia.org/wiki/Collatz_conjecture#m-cycles_cannot_occur" rel="nofollow">proof of Ray Steiner</a> (and the subsequent proofs of J.Simons and B.de Weger) use that requirement of the "primitive cycle" (in their nomenclature "1-cycle", see <a href="http://en.wikipedia.org/wiki/Collatz_conjecture#m-cycles_cannot_occur" rel="nofollow">wikipedia</a>) to show that such a cycle <em>cannot exist</em> except $\small a_0 = T(a_0;2) \qquad a_0=1$ (where no exponents of value <em>1</em> occur - the degenerate case (also called "circuit"). </p> <p>For the general cycle this is much more complicated and does definitely not have the properties which you sketch in your op.<br> <hr> [added] Answering to the comment. A characterization of the general cycle of <em>m</em> collatz-steps (<em>m=N + S</em> in my notation, where I refer -writing "steps"- to the number <em>N</em> of abbreviated steps $\small T(a;A)$ </p> <p>Assume again one step as on the form $\small a_{k+1} = (3 a_k +1)/2^{ A_k} = T(a_k;A_k)$. Then to have a cycle this means (ignore the index <em>k</em> here) $\small a=(3a +1)/2^A$ and also $\small 2^A=(3a +1)/a = (3 + 1/a)$ This can only be solved if <em>a=1</em> and <em>A=2</em>, so there is only one general-cycle of length <em>N=1</em>, <em>S=2</em> and <em>m=N+S=3</em> and we see a characteristic of the exponent <em>A</em>, which is much descriptive: the number of even steps of the original notation of the collatz-transformation is <em>2</em>.<br> Now we assume a 2-step cycle $\small a = T(a;A,B)$ and dissolve this in two steps: $\small b=T(a;A) \qquad a=T(b;B)$ thus $\small b = (3 a +1)/2^A \qquad a=(3b+1)/2^B$. I'm used to write <em>S</em> for the sum <em>A+B</em> meaning the whole number of even steps, and <em>N</em> for the number of "odd steps", both wrt the original Collatz-notation, and in my notation <em>N</em> is the number of steps (and the power of <em>3</em> involved). If we write the (trivial) product of the two involved elements <em>a</em> and <em>b</em> in their direct notation and in their transformed expression we get $\small a\cdot b = (3b+1)/2^A \cdot (3a+1)/2^B$ and this can be rewritten as $\small 2^{A+B} = (3+1/a)(3+1/b)$ This is an interesting form and easily generalized for the analysis with bigger <em>N</em> (and respectively <em>m</em>) . Here we see, that a 2-step general cycle can only exist if $\small (3+1/a)(3+1/b)$ is a perfect power of <em>2</em>; now considering the whole set of odd positive integers for <em>a</em> and <em>b</em> we see, that that product can vary only between $\small 9 \ldots 16$ and thus must be <em>S=A+B=4</em> and this requires <em>a = b = 1</em> and thus <em>A=B=2</em> (which is then only a concatenation of the trivial cycle $\small 1=T(1;2,2)$ . Here <em>m=N+S=2+4=6</em> . </p> <p>This way you may proceed studying longer assumed cycles. For instance it shows that the whole distance between two numbers $\small a_k - a_j = 2^S$ where <em>S</em> is the number of even transformations can never occur because there are always "odd Collatz steps" interspersed; even less can the distance between the minimal and maximal member of a loop be $\small 2^{N+S} = 2^m$, which were the whole length of the cycle in the counting of original Collatz-steps. </p> <p>This formula describes pretty well important properties of the exponents of <em>2</em> in relation to the length of a "general cycle" , so it might be useful for the answering of your question. However - I can't relate anything in that formula to the asked property of a connection between the distance minimal...maximal member and <em>2^m</em> where <em>m</em> is the number of all Collatz steps and actually is $\small m=S+N$ nd so I think there is none. </p> <p>Addendum : It might be interesting to look at the <em>existing</em> cycles in the domain of <em>negative</em> odd numbers; they can also be identified using the procedere exercised above. The 2-step cycle was $\small 2^{A+B} = (3+1/a)(3+1/b)$ and allowing negative <em>a</em> and <em>b</em> gives the example: $\small 2^{A+B} = (3-1/5)(3-1/7) = {14 \over 5} \cdot {20 \over 7} = {8 \over 1} = 2^3$ which is a perfect power of <em>2</em> as required. Then $\small A+B=3$ and one of them must equal <em>1</em>. In fact we have the 2-step-cycle $\small -5=T(-5;1,2)$</p> <p>Finally: a short treatize using the notation here is in that <a href="http://go.helms-net.de/math/collatz/Collatz061102.pdf" rel="nofollow">article of mine</a> </p> <hr> <p><a href="http://en.wikipedia.org/wiki/Collatz_conjecture#m-cycles_cannot_occur" rel="nofollow">1</a> Steiner,R.P.; A theorem on the syracuse problem, Proceedings of the 7th Manitoba Conference on Numerical Mathematics,pages 553...559, 1977</p>