What number has 62,118 steps ? (Collatz conjecture)

Solution 1:

This is not the answer, but an attempt to find it.

It is easy to find a number that takes $k$ Collatz steps to reach $1$, namely $2^k$. This is of course gets infeasibly large, and exceeds the 500 digit limit of that site when $k>1661$.

You can of course do better by not just inverting the 'divide by $2$' step $k$ times to get a number that needs $k$ steps, but also but using an inverse $3x+1$ step when it is possible and useful, because that keeps the number small.

I tried doing this in a slightly naive way, by repeating:

If $x \equiv 4\ or\ 16 \mod 18$ then do $x\to (x-1)/3$ else do $x\to 2x$.

I started at $x=8$ so that it wasn't stuck in the $1,2,4$ loop from the start.

BTW, the reason for the mod is that the $3x+1$ rule with $x$ odd always results in a number that is $4 \mod 6$ so the inverse of that rule is only allowed if we have such a number. We also want to avoid getting an $x$ that is a multiple of $3$ (which happens when the input $x$ is $1 \mod 9$) because otherwise all further inverted steps will be doublings.

The best result for a number that still lies within the 500 digit limit was one that takes $7449$ steps.

Clearly the person who found a number within that limit that takes so many more steps must have been doing something much more clever.

FYI, the $7449$-step number I found is:

$99128,42552,45070,58214,49794,21433,09617,71434,\\ 35751,13169,69228,12299,48208,17398,14999,66674,\\ 07909,73211,57857,75169,98703,66806,51365,17271,\\ 44964,80888,82391,81744,25916,60261,13042,03866,\\ 66103,49056,80916,51374,86393,63112,68646,00014,\\ 51265,78980,63819,41418,78232,36960,28854,91873,\\ 32045,03658,35551,66924,74284,74756,27331,65465,\\ 06917,90508,40100,42755,07304,51692,27781,51879,\\ 28347,37220,21499,69801,81717,10793,96853,00241,\\ 92286,70480,20097,55644,06511,04039,72081,20501,\\ 67137,12978,12761,35222,27067,25690,90233,93366,\\ 78269,76657,53601,98939,20113,98389,35981,59681,\\ 41626,53623,05243,67777$

Edit:

A different but equally naive method is to just try various random numbers, but preferably those whose binary expansion ends in lots of ones because those will cause the $3x+1$ rule to be chosen many times at the start of the Collatz sequence, making for a bigger number.

The best 500-digit number I found used $25858$ steps, and is:
$16910 \cdot 2^{1646} - 1=$

$52907,40618,32017,54152,63867,78240,01344,94071,\\ 10672,87955,14970,95443,32426,37432,94723,15343,\\ 69589,15667,94197,77289,84251,30595,66986,13736,\\ 01999,30240,57853,88392,15872,66353,93648,16021,\\ 76528,02318,47325,39772,11544,04475,63943,10264,\\ 65156,58431,35122,30262,85026,21429,61128,92928,\\ 64147,40168,11368,14718,14844,43105,54823,58463,\\ 32284,16963,01649,12670,32815,41060,21677,81365,\\ 13557,54204,91127,46553,29004,21933,21888,08910,\\ 76179,94524,51718,32033,27205,55270,66366,57606,\\ 00582,53081,68267,14042,35673,44288,21454,35891,\\ 44482,68697,66804,20865,40074,26362,70517,10800,\\ 03191,26585,23809,38239$