Problem C
Watch Out For Those Hailstones!
An interesting theory in mathematics is that there is a sequence generator that, given any positive integer as the starting point, always ends with the number $1$. Although this theory has never been proven, the conjecture is known as the Collatz Conjecture (named after Lothar Collatz, who posed the idea in 1937). Given an integer, $n\geqslant 1$, this conjecture pertains to the sequence $h(n)$, which we recursively define as follows:
-
If $n=1$, the sequence is composed of a single integer: $1$
-
If $n$ is even, the sequence is composed of $n$ followed by sequence $h(n/2)$
-
If $n$ is odd, the sequence is composed of $n$ followed by sequence $h(3\cdot n + 1)$
For example, the following are the sequences for the numbers $5$ and $7$:
$h(5) = (5, 16, 8, 4, 2, 1)$
$h(7) = (7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1)$
The $h(n)$ sequence is commonly known as the hailstone sequence, because of its nature of going up and down like a hailstone in a cloud before eventually falling to Earth. In this problem, you will calculate the sum of all the values in a hailstone sequence. Using the sequences above, the sum of $h(5)$ is $36$ and the sum of $h(7)$ is $288$.
Your solution must use a
RECURSIVE function,
based on the recursive definition of $h(n)$ presented above.
On the exam, any other type of solution will receive zero points!
EVEN IF KATTIS JUDGES IT AS CORRECT!
Note: You are allowed to add up the numbers iteratively, as long as the $h(n)$ sequence is computed recursively.
Input
The input contains a single positive integer, $n$ ($0 < n \leqslant 2^{32}-1$).
Output
The output contains a single integer: the sum of all the values in $h(n)$. You may assume that this sum will fit in an unsigned 64-bit integer.
| Sample Input 1 | Sample Output 1 |
|---|---|
5 |
36 |
| Sample Input 2 | Sample Output 2 |
|---|---|
7 |
288 |
