Computational verification of Collatz conjecture using gmplib Prerequisites

The unsigned long type has a size of 64 bits.

The following macros are defined.

/* all 3^n for n &lt; 41 fits into 64-bit unsigned long */
#define LUT_SIZE 41
/* any reasonably high number */
#define LUT_SIZEMPZ 512


The following array is defined and properly initialized with corresponding values.

/* lut[n] contains 3^n */
mpz_t lut[LUT_SIZEMPZ];


Additionally, the following auxiliary function is defined.

/* count trailing zeros */
mp_bitcnt_t mpz_ctz(const mpz_t n)
{
    return mpz_scan1(n, 0);
}


Problem

This code review request follows my previous request Computational verification of Collatz conjecture. The implementation in this request should handle the numbers which cannot be handled with the code in previous post.

In short: My program verifies the convergence of the Collatz problem, using this algorithm. The convergence for all values n ≤ 87 × 260 has already been proven.

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.

This function should either


return 0 if the problem for the n is convergent, or
loop infinitely if the trajectory for the n is cyclic.


Code

The 128-bit input n is split into two 64-bit parts nh and nl such that n = nh * 2^64 + nl.

int check_convergence(unsigned long nh, unsigned long nl)
{
    mpz_t n;
    mpz_t n0;
    mpz_t n_max;
    mp_bitcnt_t e;

    mpz_init_set_ui(n, nh);
    mpz_mul_2exp(n, n, (mp_bitcnt_t)64);
    mpz_add_ui(n, n, nl);

    mpz_init_set_ui(n_max, 87UL);
    mpz_mul_2exp(n_max, n_max, (mp_bitcnt_t)60);

    mpz_init_set(n0, n);

    do {
        if (mpz_cmp(n, n_max) &lt;= 0) {
            mpz_clear(n);
            mpz_clear(n0);
            mpz_clear(n_max);
            return 0;
        }

        mpz_add_ui(n, n, 1UL);

        e = mpz_ctz(n);

        mpz_fdiv_q_2exp(n, n, e);

        assert( e &lt; LUT_SIZEMPZ );

        mpz_mul(n, n, lut[e]);

        mpz_sub_ui(n, n, 1UL);

        mpz_fdiv_q_2exp(n, n, mpz_ctz(n));

        if (mpz_cmp(n, n0) &lt; 0) {
            mpz_clear(n);
            mpz_clear(n0);
            mpz_clear(n_max);
            return 0;
        }
    } while (1);
}
If you need a type with exactly 64 bits, use uint64_t (from &lt;stdint.h&gt;).  That will give a clear compilation error if no such type is available.

Given that the function never returns anything other than zero, we can move the cleanup of n, n0 and n_max outside the loop, and simply break to reach them.

Is indefinite looping really a good output if a cycle is detected?  How is that distinguishable from an arbitrarily long (but finite) chain?  Look up the standard algorithms for cycle detection in your graph theory textbook.