Computational verification of Collatz conjecture

Question

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 < 41 fits into uint64_t */
#define LUT_SIZE64 41
/* all 3^n for n < 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 × 2⁶⁰ 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 <= UINT128_C(87) << 60) {
            return 0;
        }

        n++;

        e = ctz(n);

        n >>= e;

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

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

        n *= lut[e];

        n--;

        n >>= ctz(n);

        if (n < n0) {
            return 0;
        }
    } while (1);
}

Answer 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 < UINT128_C(1) << 64 && e < LUT_SIZE64)
        return  0;

That can be rewritten as:

if (n <= UINT64_MAX && e < 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)