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
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
1234567890123
1
Returns: 1234567890122
425
425714616047350198
Returns: 1001681449523200
719433774099204033
532449225634529765
Returns: 301
938681652839233510
270904436553010679
Returns: 114
449144843248846699
624766698590466374
Returns: 105
553056322653628590
31732635724698667
Returns: 573
899
270361549640470092
Returns: 300735872792668
112925283035402051
129
Returns: 875389790972129
985554669660712003
857744876225643905
Returns: 199
745594282516936336
327666700308704705
Returns: 103
295698654017171035
714110448362160427
Returns: 99
124613693185048386
541
Returns: 230339543780141
351
60162289364907391
Returns: 171402533803192
351637995429999877
621415064023300605
Returns: 217
448616607852837213
443148034045473509
Returns: 220
76313610130859795
909914298465648232
Returns: 258
358032404507481657
811994882756629310
Returns: 103
658834888160345336
481764886321987623
Returns: 98
161007885428476854
134968361615629733
Returns: 211
610387032121568866
769215648016174975
Returns: 104
455
630639562155654776
Returns: 1386021015726729
338914788102509440
349421733435796333
Returns: 184
160360075626260195
83916796503352629
Returns: 9077
529732992768310561
530953185541489288
Returns: 603
495970969500886627
361
Returns: 1373880801941539
712
201902233898944635
Returns: 283570553228871
650166809806686892
880156715225054665
Returns: 200
415661963164951408
403270272231987979
Returns: 208
997445735399331185
730880354584413331
Returns: 208
559083626841562699
738637614205066793
Returns: 110
973402044540343580
564072768509662491
Returns: 232
894324517027910917
365997336532448669
Returns: 307
722312518870275373
921731871906944696
Returns: 103
245
969173362437934021
Returns: 3955809642603856
455
752425824415489437
Returns: 1653683130583507
181
147431320293504472
Returns: 814537681179594
217
497644075228405429
Returns: 2293290669255338
38350906486876537
981
Returns: 39093686531015
230685904486689697
799982446078690966
Returns: 105
838947514815112547
511332845794921416
Returns: 101
846050736993328193
372935984945476948
Returns: 105
389
291849059982055533
Returns: 750254652910183
580329488052172225
591719867317294017
Returns: 296
487786896893974777
573611777387862827
Returns: 296
946518513211440295
513332680028123663
Returns: 175
38255831016900615
941
Returns: 40654443163578
544323398746626361
756348195613031830
Returns: 101
565375655953876603
779419297721358496
Returns: 101
817491862470740273
690504415857737733
Returns: 165
78935955745694384
906192017559693567
Returns: 458
271
161914473327440222
Returns: 597470381282086
541
649792948554074850
Returns: 1201096023205343
619299488308235380
911714735711098129
Returns: 338
707962095758001537
991383819553345460
Returns: 320
415192958792629296
125436731148287815
Returns: 226
995882133582379213
268865561418622488
Returns: 102
586036654120253061
593
Returns: 988257426847023
666920745161036992
475114102575554611
Returns: 156
701707653598957063
921
Returns: 761897560910948
690995642197888637
406129986792963905
Returns: 102
360852540475742969
26594938095846912
Returns: 136
963348685515392407
757
Returns: 1272587431328143
589413648960073712
77
Returns: 7654722713767209
735937495250479788
937
Returns: 785418885005863
507487651082263372
595968218643453603
Returns: 106
829
411527553924696742
Returns: 496414419692069
310
354714200209114447
Returns: 1144239355513285
751827388745874118
475495439811194271
Returns: 114
683762750946593239
556431807186785493
Returns: 101
26049163320518491
113200535694542075
Returns: 1780
621
723351232771187536
Returns: 1164816799953648
692
330102544348112637
Returns: 477026798190930
303519947644271533
556495650696534001
Returns: 407
271882838110757763
768024667583809486
Returns: 99
47164541759745349
402
Returns: 117324730745655
706724396751885327
209211228233017834
Returns: 303
648792920646534737
496
Returns: 1308050243239001
105429505529393010
590747514777978667
Returns: 197
2
1111111333333333
Returns: 555555666666667
1
1234567890122
Returns: 1234567890121
3
1234567890128
Returns: 411522630044
2
999999999999999999
Returns: 500000000000000000
420196140727489673
679891637638612258
Returns: 85
1
1000000000000
Returns: 999999999999
1234567123123123
2
Returns: 617283561561562
999999999999
999999999997
Returns: 500000000000
420196140727489673
5
Returns: 84039228145497937
1
2
Returns: 1
2
10000000000001
Returns: 5000000000001
1234567890124
1234567890123
Returns: 1234567890123