OpenKattis
Programmeringsläger 2017 kvalgrupp
Problem D
Hailstone Numbers
Imagine writing up all positive integers on an infinitely
large paper. For each number $n
> 1$, you now draw an arrow to the number
-
$n/2$ if $n$ is even.
-
$3n+1$ if $n$ is odd.
A section of this paper is showed in the comic below. The sequences you get by following these arrows are sometimes called hailstone numbers since they like hailstones go up and down along the number line before finally falling to the ground (the number 1). An interesting fact is that it has thus far not been proven that you always reach the number 1, but it has been verified for all numbers up to $10^{19}$, so it is conjectured that this is true, something called the Collatz conjecture.
![\includegraphics[width=0.4\textwidth ]{collatz.png}](/problems/hageltal/file/statement/en/img-0001.png)
Figure 1: http://xkcd.com/710/
Write a program that, given two integers, compute how many arrows (in either direction) that are between the two numbers.
Input
The first and only line of input contains the two integers, $A$ and $B$ ($1 \leq A, B \leq 1\, 000$).
Output
Output a single line, the number of steps between $A$ and $B$ in the graph. It is guaranteed this is at most $1\, 000$.
| Sample Input 1 | Sample Output 1 |
|---|---|
3 20 |
2 |
| Sample Input 2 | Sample Output 2 |
|---|---|
24 10 |
4 |
| Sample Input 3 | Sample Output 3 |
|---|---|
1 5 |
5 |
| Sample Input 4 | Sample Output 4 |
|---|---|
22 32 |
12 |
| Sample Input 5 | Sample Output 5 |
|---|---|
702 703 |
236 |
