xlviii. Collatz (3n + 1)

Problem. Repeat $x\to x/2$ (even) or $x\to 3x+1$ (odd). Does every start reach $1$? (Open conjecture, verified far beyond $2^{60}$.) Contest version: compute the number of steps for every start up to $N$.

vector<int> collatzSteps(int N) {                 // steps to reach 1 for every start <= N (memoized; values may exceed N on the way)
    vector<int> s(N + 1, 0);
    for (int i = 2; i <= N; i++) {
        long long x = i; int c = 0;
        while (x >= i) { x = (x % 2) ? 3 * x + 1 : x / 2; c++; }
        s[i] = c + s[x];
    }
    return s;
}

Fact	Value
steps from 27	111 (peak value 9232)
memoization	follow the sequence only until it drops below the start, then reuse the table
overflow	intermediate values exceed $N$ a lot: use long long
cycle detection for variants ($3x+k$, other maps)	Floyd / Brent (Functional Graphs)

Proof: the memoized loop is correct

For start $i$, the loop follows the sequence until the first value $x<i$; every value before that is $\ge i$ and not yet tabled, and $s[x]$ is already known because $x<i$. The total steps are the steps taken plus $s[x]$. Termination for each $i\le N$ is an empirical fact for this range (it is exactly what the conjecture asserts in general). Checked against direct simulation for all starts up to $10^5$.