Computational verification of Collatz conjecture Prerequisites

The typedef name uint128_t designates an unsigned integer type with width exactly 128 bits.

The UINT128_MAX is maximum value for an object of type uint128_t.

Function int ctz(uint128_t n) returns the number of trailing 0-bits in n, starting at the least significant bit position. If n is 0, the result is undefined.

The macro UINT128_C(n) shall expand to an integer constant expression corresponding to the type uint128_t.

The following macros are defined.

/* all 3^n for n &lt; 41 fits into uint64_t */
#define LUT_SIZE64 41
/* all 3^n for n &lt; 81 fits into uint128_t */
#define LUT_SIZE128 81


The following array is defined and initialized with corresponding values.

/* lut[n] contains 3^n */
uint128_t lut[LUT_SIZE128];


Problem

My program is concerned with verifying the convergence of the Collatz problem, using this algorithm.

The convergence for all values n ≤ 87 × 260 has been proven. [Source: Christian Hercher, Uber die Lange nicht-trivialer Collatz-Zyklen, Artikel in der Zeitschrift "Die Wurzel" Hefte 6 und 7/2018.]

The following function is called for n of the form \$4n+3\$, in order from the smallest one to the largest one, only if all preceding calls returned zero.

The following function should either


return 0 if the Collatz problem for the n is convergent,
return 1 if the function cannot verify the convergence using 128-bit arithmetic,
loop infinitely if the trajectory for the n is cyclic.


Code

int check_convergence(uint128_t n)
{
    uint128_t n0 = n;
    int e;

    do {
        if (n &lt;= UINT128_C(87) &lt;&lt; 60) {
            return 0;
        }

        n++;

        e = ctz(n);

        n &gt;&gt;= e;

        if (n &lt; UINT128_C(1) &lt;&lt; 64 &amp;&amp; e &lt; LUT_SIZE64) {
            return 0;
        }

        if (n &gt; UINT128_MAX &gt;&gt; 2*e || e &gt;= LUT_SIZE128) {
            return 1;
        }

        n *= lut[e];

        n--;

        n &gt;&gt;= ctz(n);

        if (n &lt; n0) {
            return 0;
        }
    } while (1);
}
Given that (from your comments) there is one and only one input which would cause overflow, I propose the following check at the beginning of the function:

int check_convergence(uint128_t n)
{
        const uint128_t n0 = n;
        int e;

        if (n == UINT128_MAX)
                return  1;

        do {
                ...
        } while (true);
}




I also added const to n0, given that it's constant through all the function.



if (n &lt; UINT128_C(1) &lt;&lt; 64 &amp;&amp; e &lt; LUT_SIZE64)
        return  0;


That can be rewritten as:

if (n &lt;= UINT64_MAX &amp;&amp; e &lt; LUT_SIZE64)
        return  0;




Although maybe unneeded, I prefer to always parenthesize macros that evaluate to a value, just in case:

#define LUT_SIZE128  (81)