An optimisation of Luo's paper

The last optimisation can also be used for trajectories not reaching 1 (e.g. cycles)

It seems to work based on densities (but I am not sure it is correct, I need to dig, but it matches empirically)

In the classic 6n\pm1 optimisation you work with a denisty of \frac{1}{6}+\frac{1}{6}=\frac{1}{3}, but here we work with a density of \frac{1}{12}+\frac{1}{12}+\frac{1}{24}+\frac{1}{24}+\frac{1}{96}+\frac{1}{48}=\frac{9}{32}, so if we take our optimized a_i (only the roots) we work with

\sum\limits_{i=0}^{k-1} \frac{1}{a_i}\sim\frac{9}{32}\log (k) instead of \sum\limits_{i=0}^{k-1} \frac{1}{a_i}\sim\frac{1}{3}\log (k)

Now, if we take a_j, the smallest number of the Collatz trajectory which is not necessary 5, but is the j^{th} number of the sequence (of roots) and take the k smallest of them from there, we have \sum\limits_{i=j}^{j+k-1} \frac{1}{a_i}\sim\frac{9}{32}(\log (k+j)-\log (j))=\frac{9}{32}(\log (\frac{k}{j}+1)) and with a_j\sim \frac{32}{9}j we have \sum\limits_{i=j}^{j+k-1} \frac{1}{a_i}\sim\frac{9}{32}(\log (\frac{32k}{9a_j}+1))

To keep \operatorname{Res}(N)<2 we find a bound like this: \log(\operatorname{Res}(N))<\frac{1}{3}\sum\limits_{i=j}^{j+k-1} \frac{1}{a_i}\sim\frac{1}{3}\frac{9}{32}(\log (\frac{32k}{9a_j}+1))<\log(2) and from there \frac{32k}{9a_j}+1<2^{\frac{32}{3}} or

k<457a_j

and indeed, a quick check on the product of \prod\limits_{i=j}^{j+k-1} \left( 1 + \frac{1}{3a_i}\right) for various j shows that it starts to exceed 2 at k\sim 457 a_j (a_j being the smallest element of the trajectory and of the roots sequence).

Since all numbers have been checked up to 10^{21} this means a cycle don’t exceed 2 as long as k<457\cdot 10^{21}

1 Like