# Arithmetic progressions in stopping time of Collatz sequences

Inspired by the question here, we did a few more simulations of numbers of some specific forms and noticed a pattern.

We consider the original $$3n+1$$ transform where we divide by $$2$$ if it's even and multiply $$3$$ and add $$1$$ if it's odd. The stopping times of the sequences are defined as the number of iterations it took to reach $$1$$ (which is believed to be finite for all natural numbers in this case).

We look at numbers of the form $$2^n+1$$ (as in the link above) and note that the stopping times create the following sequence:

$$7, 5, 19, 12, 26, 27, 121, 122, 35, 36, 156, 113, 52, 53, 98, 99, 100, 101, 102, 72, 166, 167, 168, 169, 170, 171, 247, 173, 187, 188, 251, 252, 178, 179, 317, 243, 195, 196, 153, 154, 155, 156, 400, 326, 495, 496, 161, 162, 331, 332, 408, 471, 410, 411, 337, 338, 339, 340, 553, 479, 480, 481, 482, 483, 559, 560, 561, 562, 563, 564, 565, 566, 567, 568, 569, 570, 571, 572, 573, 574, 575, 576, 626, 578, 628, 629, 630, 631, 583, 584, 634, 635, 636, 637, 894, 895, 640, 641, 898, 643, 644, 645, 902, 903, 648, 649, 769, 907, 652, 653, 654, 655, 656, 657, 658, 915, 916, 917, 918, 919, 920, 921, 914, 923, 916, 917, 918, 919, 920, 921, 930, 923, 994, 995, 996, 997, 998, 999, 938, 1001, 1002, 1003, 1004, 1005, 1006, 1007, 1145, 1009, 1147, 1148, 1012, 1013, 1151, 1152, 1016, 1017, 1018, 1019, 1020, 1021, 1022, 1023, 1528, 1529, 1530, 1531, 1532, 1533, 1534, 1535, 1169, 1537, 1445, 1446, 1447, 1448, 1542, 1543, 1544, 1545, 1546, 1547, 1548, 1549, 1550, 1551, 1552, 1553, 1554, 1555, 1556, 1557, 1527, 1528, 1560, 1561, 1562, 1563, 1533,\ \ldots$$

The curious fact is that there seems to exist arithmetical sequences with common difference $$1$$ and of various lengths existing in the sequence. In this sequence shown, the largest such sequence starts at $$559$$ and ends at $$576$$ with a length of $$18$$.

Next we looked at numbers of the form $$3^n+1$$ and noted the following sequence of stopping times:

$$2, 6, 18, 110, 21, 95, 32, 75, 74, 42, 134, 133, 132, 131, 143, 204, 128, 189, 139, 94, 93, 260, 427, 90, 257, 393, 330, 254, 253, 389, 388, 387, 461, 460, 459, 458, 457, 456, 455, 454, 453, 452, 500, 499, 449, 497, 496, 751, 494, 493, 492, 747, 490, 745, 488, 487, 486, 741, 740, 739, 738, 737, 728, 727, 726, 725, 794, 793, 792, 791, 790, 789, 788, 787, 923, 785, 921, 783, 782, 781, 780, 1283, 1282, 1281, 1280, 1279, 1185, 1184, 1276, 1275, 1274, 1273, 1272, 1271, 1270, 1269, 1237, 1267, 1266, 1234, 1264, 1263, 1231, 1230, 1229, 1228, 1227, 1226, 1225, 1255, 1422, 1222, 1420, 1419, 1418, 1417, 1248, 1216, 1246, 1214, 1213, 1212, 1211, 1409, 1408, 1407, 1406, 1343, 1342, 1403, 1733, 1339, 1338, 1337, 1336, 1335, 1727, 1333, 1681, 1724, 1723, 1678, 1677, 1720, 1675, 1718, 1717, 1716, 1715, 1714, 1713, 1712, 1711, 1710, 1709, 1708, 1707, 1706, 1705, 1704, 1703, 1702, 1701, 1700, 1699, 1698, 1697, 1696, 1695, 1694, 1693, 1692, 1691, 1690, 1707, 1688, 1687, 1686, 1703, 1702, 1701, 1700, 1681, 1680, 1679, 1678, 1695, 1676, 1675, 1692, 1691, 1690, 1689, 2585, 1687, 1686, 2334, 2333, 2332,\ \ldots$$

Here also, we notice that there exist arithmetic sequences with common difference $$-1$$ and again of various lengths in the sequence. The largest such sequence here starts at $$1718$$ till $$1690$$ with a length of $$29$$.

We did these simulations a few more times with more and more numbers and sequences and essentially noted the following:

So we tried combining the two observations and guessed that numbers of the form $$6^n+1$$ should create sequences would have arithmetic sequences with common difference $$0$$. And yes it does so. The below sequence shows it:

$$16, 21, 26, 101, 83, 83, 145, 145, 220, 158, 145, 207, 114, 114, 450, 114, 357, 357, 282, 419, 419, 494, 494, 494, 494, 494, 494, 494, 543, 494, 543, 799, 799, 543, 543, 799, 543, 543, 799, 799, 791, 791, 791, 791, 861, 861, 861, 861, 998, 998, 998, 861, 861, 861, 1365, 1365, 998, 1272, 1365, 1365, 1365, 1365, 1365, 1365, 1365, 1365, 1365, 1365, 1334, 1334, 1334, 1334, 1365, 1533, 1533, 1533, 1533, 1365, 1365, 1334, 1533, 1334, 1533, 1533, 1471, 1471, 1864, 1471, 1471, 1471, 1864, 1471, 1864, 1864, 1820, 1864, 1864, 1864, 1864, 1864, 1864, 1864, 1864, 1864, 1864, 1864, 1864, 1864, 1864, 1864, 1864, 1864, 1864, 1864, 1864, 1864, 1864, 1864, 1882, 1882, 1882, 1864, 1864, 1864, 1864, 1864, 1882, 1882, 2779, 1882, 2531, 2531, 2779, 1882, 1882, 2779, 2779, 2779, 2779, 2779, 2779, 2779, 2779, 2779, 2779, 2805, 2805, 2805, 2779, 2779, 2779, 2779, 2779, 2779, 2779, 2779, 2779, 2779, 2779, 2779, 2779, 2779, 2779, 2779, 2779, 2779, 2779, 2779, 2779, 2779, 2779, 2779, 2779, 2779, 2779, 2779, 2779, 3203, 2779, 2779, 3203, 2779, 2779, 3203, 3203, 3203, 3932, 3932, 3932, 3932, 3932, 3203, 3932, 3932, 3203, 3203, 3203, 3203, 4586,\ \ldots$$

Also:

The final thing that we observed (sorry for not having a table ready, I will edit it as soon as possible) is that any number of the form $$(2^a3^b)+1$$ had stopping time sequences with the existence of arithmetic progressions with common difference $$a-b$$.

Claim: Any number of the form $$(2^a3^b)+1$$ has stopping time sequences with the existence of arithmetic progressions with common difference $$a-b$$.

We know this is true, but a proof eludes us.

Following everything we found, we made a conjecture :

Strong Conjecture : If the Collatz conjecture is true then the sequence of stopping times of the Collatz sequence for numbers of the form $$(2^a3^b)^n +1$$ has arbitrarily long arithmetic sequences and with common difference $$a-b$$.

We were not successful in proving or disproving the result, neither did we find any literature on this.

Any input on the topic would be highly appreciated.

Edit: I added a claim separately to highlight a part I just mentioned in passing.

We believe that there may not be arbitrarily long progressions because clearly we were missing a lot of values in the length sequences. But they did seem to be unbounded (no upper limit on the length of the progressions). So we weakened the conjecture a bit:

Weak Conjecture : If the Collatz conjecture is true then the sequence of stopping times of the Collatz sequence for numbers of the form $$(2^a3^b)^n +1$$ has arithmetic sequences with no length bound and with common difference $$a-b$$.

Evidence for the weakening:

For numbers of the form $$6^n+1$$, the sequence of length of progressions (what progression lengths are there in the stopping time sequences) looked like this:

For the first $$1000$$ terms:

$$1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 27, 29, 38, 48, 51, 52$$

For the first $$2000$$ terms:

$$1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 25, 27, 28, 29, 36, 38, 45, 46, 48, 51, 52, 59, 110$$

For the first $$10000$$ terms:

$$1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 25, 26, 27, 28, 29, 31, 36, 38, 41, 45, 46, 48, 50, 51, 52, 54, 55, 56, 58, 59, 60, 61, 65, 71, 72, 73, 74, 78, 82, 83, 86, 92, 99, 101, 102, 107, 109, 110, 111, 116, 126, 130, 132, 133, 160, 161, 163, 172, 180, 182, 184, 185, 186, 189, 220, 248, 271, 337$$

We are clearly missing $$12$$ and $$24$$. Probably $$30$$ is also missing. We are not sure if these are actually missing, but appears to be so. If indeed they are missing, then the strong version is false. If not i.e. if the values will be available as the number of terms increase, then it's true.

But as of this moment, both the conjectures are open (possibly).

So the main questions to move forward will be to the answer the following:

• Why are their arithmetic sequences in the stopping times of these specific numbers?
• Can we prove the claim?
• Are the conjectures true?

(I will be editing the question with more data and possibly some graphs as soon as I have some more time on hand. Till then, please let us know of your thoughts. Thank you).

• This is fascinating! A slightly different approach could be to ignore the (more or less occasional) "interruptions" of the arithmetic progressions. So you get longer ranges where the stopping times are essentially linear functions of $n$. This graphic suggests looking for the longest segments of slope 1 you can draw between two points. Those segments supposedly contain many other points, and you could numerically look at their lengths, but also at the proportions of points they contain - tending to 1? Here, by "points" I obviously mean pairs $(n,A179118(n))$. Dec 20, 2019 at 10:51
• Yes the graphic is interesting. Plotting this on a semi log plot with points as (n, log(A179118(n)) gives a nice logarithmic graph as more points are added. Dec 20, 2019 at 11:02
• I don't see the use of introducing logs here... Dec 20, 2019 at 11:19
• The graph is fascinating. Dec 20, 2019 at 11:20
• the Collatz sequence maps $2^a3^b+1$ to $2^{a-2}3^{b+1}+1$ in 3 steps and in particular $2^{2a}+1$ to $3^a+1$ in $3a$ steps. Then it follows that if we have sequences with -1 for $3^a+1$ numbers we will have sequences of steps $3-1=2$ for the numbers of the form $4^a+1$ or every second number of the form $2^a+1$. Apr 20, 2020 at 18:16

Here an attempt to try to explain the very interesting observations. I believe it does not have much to do with powers but with the fact that consecutive integers often converge to $$1$$ with the same number of $$/2$$ and $$*3+1$$ steps in a different order. For example if you start with $$8n+4$$ and $$8n+5$$ you end up with $$3n+2$$ in both cases with three $$/2$$ and one $$*3+1$$ step. So any consecutive numbers equal to $$4$$ and $$5$$ modulo 8 end will use the same number of $$/2$$ and $$*3+1$$ steps to converge to 1 (if they converge at all). You can find more similar rules for higher powers of two. For example $$\begin{eqnarray} 4,5 \text{ mod } 8\\ 2,3 \text{ mod } 16\\ 5,6 \text{ and } 22,23 \text{ mod } 32\\ 14,15 \text{ and } 45,46 \text{ mod } 64\\ 29,30 \text{ and } 49,50 \text{ and } 94,95 \text{ mod } 128\\ 62,63 \text{ and } 99,100 \text{ and } 145,146 \text{ and } 189,190 \text{ mod } 256 \end{eqnarray}$$ The number of pairs that converge to the same value $$\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|} \hline n & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 \\ \hline \text{number of new "converging" pairs mod } 2^n & 1 & 1 & 2 & 2 & 3 & 4 & 6 & 11 & 19 & 34 & 60 \\ \hline \end{array}$$
If we now compute the probability that two consecutive numbers converge with the same number of steps we and up with more than $$1/3$$. If we start with $$3^n+1$$ then there is the chance it will the need the same number of iterations as $$3^n$$. The number $$3^n$$ will after one step be at $$3^{n+1}+1$$. Hence the chances are that $$3^{n+1}+1$$ needs one step less than $$3^n+1$$.