I worked on the Collatz conjecture extensively for fun and practise about a year ago (I'm a CS student, not mathematician). Today, I was browsing the Project Euler webpage, which has a question related to the conjecture (longest Collatz sequence). This reminded me of my earlier work, so I went to Wikipedia to see if there's any big updates. I found this claim

The longest progression for any initial starting number less than 100 million is 63,728,127, which has 949 steps. For starting numbers less than 1 billion it is 670,617,279, with 986 steps, and for numbers less than 10 billion it is 9,780,657,630, with 1132 steps.[11][12]

Now, do I get this correctly: there is no known way to pick a starting number $N$, so that the progression will last at least $K$ steps? Or, at least I don't see the point of the statement otherwise. I know how this can be done (and can prove that it works). It does not prove the conjecture either true/false, since it is only a lower bound for the number of steps. Anyway, I could publish the result if you think it's worth that? When I was previously working on the problem, I thought it was not.

  • 4
    $\begingroup$ No, that's not the claim. It's just describing how slowly the orbit length increases with the starting value. It's easy to come up with a number that has any initial behavior (of any length). For instance, $2^N$ takes $N-1$ steps to get down to $1$. $\endgroup$ – mjqxxxx Oct 30 '13 at 21:59
  • 3
    $\begingroup$ Well, there is a trivial solution. For a given $K$, set $N=2^K$ and it will take the Collatz procedure $K$ steps to get down to $1$. $\endgroup$ – Tomas Oct 30 '13 at 22:02
  • $\begingroup$ Note that what the 'length' of a sequence is depends strongly on what your definition of a 'step' is - some people take $x\mapsto 3x+1$ for odd $x$, some take $x\mapsto \frac12(3x+1)$, and some in fact take $x\mapsto \frac{3x+1}{2^{\nu_2(3x+1)}}$, where $\nu_2$ is (one less than) the 'ruler function', the number of times $2$ divides into its argument - in other words, each odd $x$ just maps to the next odd number in the sequence, and all of the 'reduction' steps are skipped. $\endgroup$ – Steven Stadnicki Oct 30 '13 at 22:13
  • $\begingroup$ I always used the latter approach, working with just odd numbers. $\endgroup$ – justasking Oct 30 '13 at 22:18

The answer to your question is yes; one can work the Collatz relation backwards to build numbers that last arbitrarily long (for a simple example, just take powers of 2). However the purpose of the wikipedia records is to see if we can find SMALL numbers that last a long time.

  • $\begingroup$ So, if you give me some number $N$, and I give you the smallest number $K < N$, which has the longest progression, there is something interesting in that? $\endgroup$ – justasking Oct 30 '13 at 22:06
  • $\begingroup$ @justasking If you had a consistent way of doing so then there would be something vaguely interesting, yes. Do you believe you have a method that reproduces e.g. the 670617279 result? $\endgroup$ – Steven Stadnicki Oct 30 '13 at 22:09
  • $\begingroup$ Yes, I think so. I'll check my old books. $\endgroup$ – justasking Oct 30 '13 at 22:21
  • $\begingroup$ Did not find the book yet but thought this through while drinking coffee. I sketched the idea on a piece of paper and I think I remember most of it. I'm very confident I can do it. Could you elaborate more why it would vaguely interesting? $\endgroup$ – justasking Oct 30 '13 at 22:56
  • $\begingroup$ @justasking From my perspective, at least, because the numbers that are local maxima 'look' very much random (670617279 is, for instance, $3^3\times23\times41\times26339$, which doesn't seem to mean anything), and so any method that can find such local maxima offers the promise of showing some structure in the problem as a whole that might be unknown. $\endgroup$ – Steven Stadnicki Oct 30 '13 at 23:28

To add on Vadim's answer. With a bit different notation it is perhaps better readable to express the following:

instead of the sequence of steps $ a_1=3a_0+1 ; a_2 = a_1/2; a_3 = a_2/2 ; ... a_k=a_{k-1}/2 $ which means we count k steps and obviously is only allowed until $a_k$ becomes an odd number, let us write $ a_k = T(a_0; K) $ so this is only one step in the new formulation but counts as $1 + k$ steps in the usual convention because it means one step $3a_0+1$ and then $k$ steps dividing by $2$ which simply means one step dividing by $2^K$.

Then further iterations become an expression like $ a_x = T(a_0;A_1,A_2,A_3,...,A_x) $ where the number-of-exponents $N$ (="3x+1" steps) plus the sum $S$ of all exponents $A_k$ give the number of steps $k$ in the conventional way of counting.

Now we can, for any given sequence of exponents $ a_x = T(a_0; A_1,...,A_x)$ find an initial pair of $a_0$ and $a_k$ which solves the transformation equation (and then infinitely many others which only are in the same resdiue class "modulo $2^S$") where, again, $S$ is the sum of the exponents (or: the overall number of divsion-by-2 steps).

To make the same sum of some number of given steps $k$ in the conventional counting, say we want $k =60000$ we can first define any number of $N \lt k/2$ steps for the $3x+1$ transformations and then $N$ exponents $A_1,A_2,...A_n$, whose sum $S$ must then fill the gap $S= k - N"$.

But we have many options to first choose some $N$ - and after that we have another (but finite, fortunately!) number of variations of the exponents $A_k$ to sum up to $S$ and each such variation defines its own smallest pair $a_0 \to a_k$ (and the other solutions in the same modular class).

But which is now the smallest $a_0$ in all that possible settings? It can be determined in a finite amount of time/calculations -which is in its own an interesting observation- , but this is the essence of the discussion/the search of the "records-in-step-numbers"


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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