Programming — Hailstone (Collatz) Sequence: 25-Comp-A4 Program Design and Data Structures, December 2017, Q2

Question 2: Programming — Hailstone (Collatz) Sequence (20 marks)

Question text not reproduced: the examination questions are © Engineers and Geoscientists BC. Open the official past paper (linked at the top of this page) to read the question, then follow the worked solution below.

Given. Starting integer $n_0>0$; rule $n_{k+1}=3n_k+1$ (odd) or $n_{k+1}=n_k/2$ (even); worked example $n_0=10\Rightarrow$ 6 steps, largest value 16.

Find. A program reporting the step count to reach the repeating ground state $4,2,1,4,2,1,\ldots$ and the largest value visited.

Approach. Apply the rule repeatedly, counting one step per application and tracking the running maximum, stopping the first time the current value reaches 1 (the ground state $4,2,1$ then repeats forever from there, so reaching 1 marks the end of the "climbing" part of the sequence — this matches the worked example exactly).

Confirm the stopping rule against the worked example. For $n_0=10$: $10\to5\to16\to8\to4\to2\to1$ is 6 applications of the rule, and the running maximum along the way is 16 — both figures match the question's own example, so "reach the ground state" means "reach the value 1" (after which $4,2,1$ repeats forever from the next steps).

Write the program.

#include <stdio.h>

int main(void)
{
    long n, largest, steps = 0;

    printf("Enter a starting number: ");
    scanf("%ld", &n);
    largest = n;

    while (n != 1) {
        if (n % 2 == 1)
            n = 3 * n + 1;
        else
            n = n / 2;
        steps++;
        if (n > largest) largest = n;
    }

    printf("Steps to reach the ground state: %ld\n", steps);
    printf("Largest number reached: %ld\n", largest);
    return 0;
}

Verify the trace. The program's loop body executes for $n_0=10$ exactly at $n=10,5,16,8,4,2$ (6 iterations, ending when $n$ becomes 1), and $\max\{10,5,16,8,4,2,1\}=16$. $$\boxed{\text{steps}=6,\ \ \text{largest}=16}$$

Question 2 — results
Starting number	Steps to ground state	Largest value reached
10	6	16
1 (already at ground state)	0	1
27 (illustrative, long-running case)	111	9232

Concept & Theory

Topic. The Collatz (hailstone) iteration and loop-with-running-extremum programs.

Key relations. $n_{k+1} = 3n_k+1$ if $n_k$ odd, $n_k/2$ if even; the Collatz conjecture (unproven in general, verified computationally to about $2.95\times10^{20}$ as of recent large-scale checks, consistent with the question's "up to about 1.2e12" figure at the time it was written) asserts every positive starting value eventually reaches 1.

Why this works. Because every even step strictly decreases the value and every odd step is always followed by an even one (an odd $n$ gives $3n+1$, always even), the sequence cannot grow without bound in practice for the tested range, so a simple `while (n != 1)` loop terminates; tracking `largest` incrementally avoids storing the whole sequence.

Common pitfall. Using `int` for the intermediate `3*n+1` (some starting values, e.g. 27, push the running value into the thousands, still safe in `int`, but very large starting values can overflow — `long` is the safer default); miscounting the ground state as reached at 4 instead of 1 (both appear in the repeating cycle, but the worked example only matches counting to 1).

Source. Weiss, Data Structures and Algorithm Analysis in C, 2nd ed., §1.3 (loop-based numeric algorithms and termination arguments).

Question 2 of 9: Programming — Hailstone (Collatz) Sequence

Question 2: Programming — Hailstone (Collatz) Sequence (20 marks)