7
$\begingroup$

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.

$\endgroup$
4
  • 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
    Commented Oct 30, 2013 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
    Commented Oct 30, 2013 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$ Commented Oct 30, 2013 at 22:13
  • $\begingroup$ I always used the latter approach, working with just odd numbers. $\endgroup$
    – justasking
    Commented Oct 30, 2013 at 22:18

2 Answers 2

6
$\begingroup$

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.

$\endgroup$
5
  • $\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
    Commented Oct 30, 2013 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$ Commented Oct 30, 2013 at 22:09
  • $\begingroup$ Yes, I think so. I'll check my old books. $\endgroup$
    – justasking
    Commented Oct 30, 2013 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
    Commented Oct 30, 2013 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$ Commented Oct 30, 2013 at 23:28
2
$\begingroup$

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"

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .