# Calculate the maximum in the Collatz sequence

Consider the notorious Collatz function $$T(n) = \begin{cases}(3n+1)/2&\text{ if n is odd,}\\n/2&\text{ if n is even.}\end{cases}$$

One of the most important acceleration techniques of the convergence test is the usage of a sieve (test $$k$$ least significant bits of $$n$$, the sieve has the size of $$2^k$$ entries), and test only those numbers that do not join the path of a lower number in $$k$$ steps. This technique is greatly explained, e.g., here or here.

For example, consider the sieve for $$k=2$$ and particularly the numbers of the form $$4n+1$$ which join the path of $$3n+1$$ in two steps. Their path is $$4n+1 \rightarrow 6n+2 \rightarrow 3n+1 \text{.}$$

What I don't understand is how this can be used to search for the highest number occurring in the sequence (path records in the terminology of Eric Roosendaal). The sieve cuts the calculation before the computation of any intermediate value (which can actually be the maximum, like the value $$6n+2$$ in the above example). How can I detect that $$4n+1$$ does lead to a maximum if no $$6n+2$$ is computed? Testing the path of $$3n+1$$ no longer makes sense since the maximum $$6n+2$$ occurs before this term. Am I missing something?

• $4n+1$ is not the best example since we are supposed to stop at 1 and not continue (and you would see N=1 Mx(N)=2 instead of N=2 Mx(N)=2 on Eric's page) Commented Nov 28, 2019 at 19:24
• @Collag3n Consider for example the number 5 (which is of the form $4n+1$). Using the sieve with $k=2$ bits, the convergence test is skipped since the sieve indicates that the trajectory of this number joins a trajectory of a lower number in at most two steps (namely, the trajectory of the 5 joins the trajectory of 4 in two steps). This, however, results in a miss of the maximum (which is the number 8). Do I get it wrong? (The complete trajectory is 5 → 8 → 4 → 2 → 1.) Commented Nov 28, 2019 at 19:47
• 5 is not skipped in sieve $k=2$ but in sieve $k>2$. But since 3 was already found with a greater path record (16), it is discarded. Commented Nov 28, 2019 at 19:56
• And if 5 had reach another value higher then 8 later (with an higher $k$), it would have been found with 4 (well that's not the best example neither, you would have an odd value somewhere for that case) Commented Nov 28, 2019 at 20:05
• I think your criticism is correct. For the conclusion for the filter being valid it must been proved elsewhere, that there is always a follower from $3n+1$ which is larger than the immediate follower of $4n+1$ (which is $6n+2$). And I didn't see such a statement/proof. Commented Nov 30, 2019 at 12:51

Quote: "As $$k$$ increases, the search only needs to check those residues $$b$$ that are not eliminated by lower values of $$k$$"

Take residue 15 for instance. It survives $$\mod 2^5$$ but is eliminated while sieving $$2^7$$ so any value $$x\equiv 15 \mod 2^7$$ will not be searched anymore for $$k>7$$

Residue 15 was eliminated because it reached a lower value then himself $$\mod 2^7$$. It means that these numbers can't reach higher values, later with $$k>7$$, that were not reached (with a smaller $$k$$) by the lower value they just hit.

• sorry for the poor wording, I am bit lazy on this one Commented Nov 28, 2019 at 20:37
• The real acceleration, is noting that $2^mx+j$ has the parity of $j$ This means it will follow the same style of path as $j$ does ( only for $m$ steps, and only if $m$ is greater than or equal to, the number of divisions by 2 in $j$'s sequence, let $x$ be odd) this shows: $$2048x+7\to 6144x+22\to 3072x+11$$$$\to 9216x+34\to 4608x+17\to 13824x+52$$$$\to 6912x+26\to 3456x+13\to 10368x+40$$$$\to 5184x+20\to 2592x+10\to 1296x+5$$ and 4 more steps, eventually landing on $243x+1=242x+(x+1)$. the altered Collatz function would never hit the highest points.
– user645636
Commented Nov 28, 2019 at 22:57
• I'm sorry, but I still don't get it. Can we stay on that example with the number 5 and $k = 2$? The Wikipedia page says that the sieve answers the question whether the number $n = a2^k+b$ should be tested for the convergence or not. Right so far? Commented Nov 29, 2019 at 8:51
• So if $f^k(a2^k+b) < 2^k+b$ for all nonzero $a$, and this also holds for all $k'<k$, the number $a2^k+b$ can be skipped, okay? Commented Nov 29, 2019 at 8:54
• Note that the acceleration using the identity $f^k(a2^k+b)=a3^{c(b)}+d(b)$ is another technique, usually used right after the above sieve. Commented Nov 29, 2019 at 8:57

(Notation: residue $$n_0\mod 2^{\lceil i \log_23\rceil}$$ = residue $$b\mod2^k$$ from your wiki page)

About the "discarded" 5 reaching maximum 8 (or 16), already reached by "surviving" 3:

• One of the discarded sequence is the inverse V-Shape sequence which rise for $$i$$ steps of $$f(x)=\frac{3x+1}{2}$$ and then fall bellow the initial value by successive division by $$2$$ (See here). Of all discarded sequences $$2^{\lceil i \log_23\rceil}n+n_0$$ for a specific $$n$$, this is the type of sequence that potentially reaches the highest value: $$(2^{\lceil i \log_23\rceil}n+n_0+1)\frac{3^i}{2^{i}}-1$$

Note: $$n_0\leq 2^{\lceil i \log_23\rceil}-3$$ and the exact value can be found in the link above

e.g. with $$4n+1=5$$ where $$n_0=1$$, $$i=1$$,$$n=1$$ which reaches $$8$$ before dropping to $$4<5$$

• One of the surviving sequence is the straight line which rise for the whole $$k={\lceil i \log_23\rceil}$$ steps of $$f(x)=\frac{3x+1}{2}$$. Of all surviving sequences for a specific $$n$$, this is the sequence (starting from $$2\cdot2^{\lceil i \log_23\rceil}n-1$$) that reaches the highest value (limited to $$k={\lceil i \log_23\rceil}$$ steps): $$3^{\lceil i \log_23\rceil}(n+1)-1$$

Note: here we always have $$n_0= 2^{\lceil i \log_23\rceil}-1$$

e.g. with $$4n+3=7$$ where $$i=1$$,$$n=1$$ which reaches $$17$$ (in 2 steps), or with $$n=0$$: $$3$$ reaches $$8$$

Now it is easy to show that the highest value that can be reached by a discarded sequence at $$n$$ is smaller (or equal) than the highest value already reached by a surviving sequence at $$n-1$$

e.g with discarded $$4(1)+1=5$$ reaches $$8$$ which was already reached by surviving $$4(1-1)+3=3$$

Surviving highest value at $$n-1$$ is greater then discarded value at $$n$$?

$$3^{\lceil i \log_23\rceil}n-1 \geq (2^{\lceil i \log_23\rceil}n+n_0+1)\frac{3^i}{2^{i}}-1$$ and with $$n_0< 2^{\lceil i \log_23\rceil}-1$$, we just need to show that $$3^{\lceil i \log_23\rceil}n-1 \geq (2^{\lceil i \log_23\rceil}(n+1))\frac{3^i}{2^{i}}-1$$ $$\Big(\frac{3}{2}\Big)^{\lceil i \log_23\rceil}n \geq \Big(\frac{3}{2}\Big)^i(n+1)$$ $$\Big(\frac{3}{2}\Big)^{\lceil i \log_2\frac{3}{2}\rceil} \geq 1+\frac{1}{n}$$ which is already true for $$n-1=0$$ when $$i\geq 3$$ (manually checked for $$i=1$$ and $$i=2$$ by using the exact value of $$n_0$$ in those cases)

e.g. with $$n-1=0$$: discarded $$32n+23$$ reaches $$188$$ but surviving $$32(n-1)+31$$ already reached $$242$$

Note: you can multiply both side by 2 to get the "real" maximum (16 instead of 8).

The key idea is that even if the discarded inverse V-Shape at $$n$$ was at the highest possible residue $$n_0= 2^{\lceil i \log_23\rceil}-3$$, it would reach a smaller value than the straight line at $$n-1$$ (always with residue $$n_0= 2^{\lceil i \log_23\rceil}-1$$).

This means that record paths are always found in residue $$b\mod2^k$$ (in other word, at $$2^k\cdot n+b$$ with $$n=0$$)

EDIT:

even more, when sieving $$2^{k+1}$$: values below $$2^k$$ that are dropping cannot produce new path records (obviously), but value above $$2^k$$ that are not surviving after $$2^{k+1}$$ sieve are now known, and there maximum is still the RHS above: indeed the condition $$n_0+2^{\lceil i \log_23\rceil}< 2^{\lceil i \log_23\rceil+1}-1$$ or $$n_0< 2^{\lceil i \log_23\rceil}-1$$ do not change, and the value of $$i$$ (climbing steps) neither since the last step was a drop bellow initial value.

So even if the max value on the LHS do not climb anymore at step $$k+1$$, it would still be higher (the whole equation would stay the same).

This means that new record paths are only found in surviving residue $$b\mod2^k$$

No need to check discarded residue at all, even within the sieve range.

• Comments are not for extended discussion; this conversation has been moved to chat. Commented Apr 8, 2020 at 13:17
• I just wanted to let you know that I found another path record while searching the interval up to 2^68. It is also mentioned here. Commented Apr 29, 2020 at 13:56
• @DaBler, Nice :) there is another sieve I am interested in (oeis.org/A005184) but I am currently on something else, so they are both in my "To do" list until I find some time Commented Apr 29, 2020 at 17:21
• These values seem to be very rare. I have found no more terms below $2^{44}$. Commented Apr 30, 2020 at 19:17