Hide

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

Please log in to submit a solution to this problem

Log in