CalkinWilfReversed | Topcoder Archive

Problem Statement

The Calkin-Wilf tree is a rooted tree that contains each positive rational number exactly once. The definition of the tree is really simple:

The root of the tree contains the value 1/1.
Each node in the tree has one left child and one right child.
If a node contains the fraction a/b, its left child contains the fraction a/(a+b) and its right child contains the fraction (a+b)/b.

Here is an ASCII art drawing of the first few levels of the tree:

                ____________1/1____________
               /                           \
        ____1/2____                     ____2/1____
       /           \                   /           \
    1/3             3/2             2/3             3/1
   /   \           /   \           /   \           /   \
1/4     4/3     3/5     5/2     2/5     5/3     3/4     4/1

The depth of the root is 0. If a node has depth n, its children have depth n+1.

You are given the longs a and b. Compute and return the depth of the node that contains the fraction a/b.

Definition

Class:: CalkinWilfReversed
Method:: getDepth
Parameters:: long, long
Returns:: long
Method signature:: long getDepth(long a, long b)
(be sure your method is public)

Constraints

a will be between 1 and 10^18, inclusive.
b will be between 1 and 10^18, inclusive.
a and b will be relatively prime. (I.e., their greatest common divisor will be 1.)

Examples

```
1
```
```
1
```
```
Returns: 0
```
The fraction 1/1 appears in the root of the tree, and by definition the depth of the root is 0.
```
4
```
```
3
```
```
Returns: 3
```
The fraction 4/3 can be found in the bottom level of the figure shown in the problem statement. The depth of its node is 3.
```
1
```
```
1234567890123
```
```
Returns: 1234567890122
```
The fraction 1/1234567890123 is in the leftmost branch of the tree, and its node is quite deep.
```
1234567
```
```
7654321
```
```
Returns: 8837
```

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.