Simple Collatz Sequence

Interview

Time limit1sMemory limit512 MB

Summary

Simulate the modified Collatz rule (halve even k, increment odd k) from n until reaching 1 and count the steps taken.

Level: Easy2 of 10
Topics: Simulation, Implementation, Math
Solved: No attempts yet

Problem

The Simple Collatz Sequence (SCS) starting at an integer $n$ is defined by the formula:

$S(k) = \begin{cases} k/2 & \text{if } k \text{ is even} \\ k+1 & \text{if } k \text{ is odd} \end{cases}$

The sequence is then $n, S(n), S(S(n)), \dots$ until the value first reaches 1.

For example, starting at 11, we have:

11 -> 12 -> 6 -> 3 -> 4 -> 2 -> 1

The sequence always ends at 1. (Fun Fact: The Hard Collatz Sequence sends odd $k$ to $3k+1$ . It is unknown whether that sequence always ends at 1.)

Let $A(n)$ be the number of steps in the SCS starting at $n$ . For example, $A(11) = 6$ . Write a program which computes $A(n)$ for a given input $n$ .

Input

Input consists of a single line which contains a positive decimal integer, $n$ , which starts the sequence. $n$ will fit in a 32-bit unsigned integer.

Output

The output consists of a single line that contains the value of $A(n)$ , the number of steps in the SCS starting at $n$ .

Examples2

Example 1
Input
```
11
```
Expected output
```
6
```
Example 2
Input
```
123456789
```
Expected output
```
39
```