TopCoder Statistics - Problem Statement

Problem Statement

The Collatz conjecture (also known as the 3n+1 conjecture) is a well-known open problem in mathematics. In this problem we'll study a related problem: the n+odd problem.

You are given an odd int K. The function f is defined as follows: if N is even, f(N) = N/2, otherwise f(N) = N+K.

For any starting positive integer x, consider the following sequence: x, f(x), f(f(x)), f(f(f(x))), ...

It can be shown that regardless of x and K the sequence will eventually reach a value that is less than or equal to K. Let g(x) be the smallest number of consecutive applications of the function f needed for this to happen.

For example, g(x) = 3 means that the values x, f(x), and f(f(x)) are all strictly greater than K and the value f(f(f(x))) is at most equal to K.

Another example: Suppose K=1 and x=5. This x defines the following sequence: 5, 5+1 = 6, 6/2 = 3, 3+1 = 4, 4/2 = 2, 2/2 = 1, ... Hence, in this case we have g(5) = 5.

You are given two longs L and R, and the int K mentioned above. Compute and return the sum of g(x) for x between L and R, inclusive.

Definition

Class:: NAddOdd
Method:: solve
Parameters:: long, long, int
Returns:: long
Method signature:: long solve(long L, long R, int K)
(be sure your method is public)

Constraints

K will be between 1 and 100,000, inclusive.
K will be an odd number.
L and R will be between 1 and 10^16, inclusive.
L will be smaller than or equal to R.

Examples

5

5

1

Returns: 5

we need to calculate g(5). This example is explained by problem statement. So the answer is 5.
1

99999

99999

Returns: 0

For each x in the given range we have g(x) = 0. In general, whenever x <= K, g(x) = 0.
16

17

3

Returns: 9

The sequence for x=16 looks as follows: 16, 8, 4, 2, 1, ... The sequence for x=17 looks as follows: 17, 20, 10, 5, 8, 4, 2, 1, ... Hence, g(16) = 3 and g(17) = 6.
3

7

5

Returns: 4
1645805087361625

9060129311830846

74935

Returns: 421014795656548226
1

10000000000000000

1

Returns: 779684339768164354
1

10000000000000000

99999

Returns: 555604353933868904
1431825960716539

8605466393872494

86363

Returns: 404075036119428179
2629186606594285

8941414261101452

93533

Returns: 357086390766032184
2340116991224422

8651630970288470

95999

Returns: 355905853448487920
1344970294753376

8067715096372317

94609

Returns: 376469210467442895
551663688842910

9954853576068478

80799

Returns: 530104820625618613
2355213341202329

8791700931565861

94205

Returns: 363390664274866963
1992757464888941

7644990592522080

98377

Returns: 316792443718751735
1415011303050921

8986644493415528

96935

Returns: 425138008826424268
1591850852407660

8078803486064951

95069

Returns: 363778690459191879
141131195344101

8112530186913431

92001

Returns: 442002085878315928
926864264758706

9016308197943306

77891

Returns: 456535512064016964
1856450849314299

6643753720328690

34545

Returns: 277896829574424622
150316538188123

7349872659663281

62863

Returns: 403676539374204561
193785627606525

7217105580227058

70169

Returns: 392153427270374705
35559144925060

9443695790280305

97985

Returns: 522413250684505101
76781996867141

8758475322109152

82589

Returns: 484228968044026946
1775895166909957

7537984965051779

74403

Returns: 325854638213741919
220925663821178

9458112709877697

81507

Returns: 517948766956933961
3880973301397345

9826436838906435

54237

Returns: 345804464757791633
4215567212352711

4511621477466140

94573

Returns: 16583198222326423
466871217641903

9613687627118405

84593

Returns: 513746926740639620
80547236600074

9896011141217587

80409

Returns: 550557486642047156
556880839548313

8035834828940273

77625

Returns: 419301481574777799
2039055685423278

6098633560902735

91147

Returns: 226841784600458443
3176742251034504

6096438278979872

94101

Returns: 163942613732683024
2863654450825103

9198835324130401

28153

Returns: 375511063313617407
79487747753021

5980036475851046

98717

Returns: 322153436796569641
1641510073506710

5978628079230903

96051

Returns: 241088786570737345
35434097693434

9226988291857149

80393

Returns: 513814237859214836
1723948731068593

7436305745887553

94845

Returns: 319869446940854193
3308538569344459

8905214008507847

78735

Returns: 319476933825099244
2033654483135074

7577502104007672

49077

Returns: 319055082998950576
2171057647210263

9223975418800180

63301

Returns: 404449190141138369
28763007718492

9280009671870855

87655

Returns: 515483523970674464
2366935444777567

9283781049514624

96203

Returns: 390782523744155397
2927510543404756

5420217906864391

57073

Returns: 142134492036688742
5537167563905748

8116335331916179

63065

Returns: 149237253758833702
4314433891040479

9510360644804573

88019

Returns: 296906835354343789
2698798465540246

8999090439091884

79829

Returns: 358678269245006232
842961672375395

8264424206301598

82023

Returns: 416616471341286327
290754272900363

9191668973645301

87203

Returns: 497707008851344232
174199105391655

9218135931721991

93805

Returns: 503646730473108522
2952206344236866

9082317427037254

96197

Returns: 347043042884589785
1590085646947387

9725216450674514

55301

Returns: 468216490667739521
3507840918984519

6898308650352049

91099

Returns: 191489506067330802
1291521976963857

9585549755802665

94059

Returns: 466758203045566600
793028884139876

9049024871807813

79477

Returns: 465159788791635664
1019642091932377

9929748792853651

98109

Returns: 500292038130267436
5885155787811

6932917725457939

98701

Returns: 379684060744214408
211431208978075

8492057744871330

21583

Returns: 486310877798727863
915957034589266

6844709080430448

10621

Returns: 357330297818712359
4143717785915280

6700046608182829

29939

Returns: 150761861639244130
2346896008514554

7068189260899094

31345

Returns: 276180301973833876
4306648962088232

6641538536374470

2873

Returns: 149641564499994492
2440644160259499

7687476758553192

60431

Returns: 300265491809261063
2178717530734359

5694112795409225

6193

Returns: 216681109248119758
47455507256149

5419771076894842

5045

Returns: 326559570164099591
346128190081952

7855125038779489

21461

Returns: 440651589549514291
2816065946327063

9725037413391438

20611

Returns: 414564597167266341
246364144265967

8953014127743164

24001

Returns: 510485402277990101
2312109353967290

6583750551959060

12111

Returns: 258213496283635340
4159864990428125

9331400942577727

1251

Returns: 342777077230569847
1803523981502850

7744868428163214

35353

Returns: 345848531747840528
260558147153528

8910920869589788

10095

Returns: 523335148653169541
179467961203432

7654512960536599

25275

Returns: 434744452360578936
375868441789230

9895906445262437

7021

Returns: 586138488716343945
4058452480138989

8842195532290611

1957

Returns: 312082808114357849
185838830623746

9994909628625343

14783

Returns: 587221188595811536
3744433764362094

5174836758937476

15275

Returns: 85919132428640576
209249520258682

9372651560798428

12975

Returns: 550085586779538438
3428269132367211

8324176061836905

5645

Returns: 307105479096223265
3704704699726268

8592151449128730

29679

Returns: 289588935007459492
539421943268123

8582807342347989

305

Returns: 547988228695857216
91396177046881

9438433087720438

53009

Returns: 531955340116337366
1632337019993458

9947365460685696

13249

Returns: 504671338347679457
1592384279564397

6698527685428215

41661

Returns: 293932392022722931
146079499068887

7965300813850021

32999

Returns: 450575706586281194
53995344856402

9124404083150326

8415

Returns: 551326516883239157
1071576798231283

8549158637161731

2527

Returns: 477200797588685004
1617270389589442

9482169032401249

20501

Returns: 469176263111684613
2753256242586229

8004441631242687

10363

Returns: 321356727655029616
2174293736048861

9650571042172947

2919

Returns: 478944422273500361
1812021098647724

8468182493136263

11135

Returns: 405086319799287292
77550586677648

7517108510005794

23429

Returns: 432929449956268791
2114954045016602

8067388317859446

347

Returns: 406883214565351712
1014113761282071

9373227929182437

56093

Returns: 478658540898165682
1920421113270623

9373235083548470

3889

Returns: 472034902710914202
127399402143816

9598588462316188

24471

Returns: 555429387300963376
2880434541371644

8184297958431084

17897

Returns: 318584219805110346
1075330510133099

9708096617547562

44087

Returns: 499471045774834361
308682161676784

9342319592959267

58053

Returns: 513553104972493736
4106680865991160

9795478871727639

12255

Returns: 349354278096312651
4123662766248769

7085313757365145

28685

Returns: 175127711764473420
347406506003307

9665603232363625

13327

Returns: 560207943107875098
4740425426626955

8439912300100422

8849

Returns: 229477764892091773
3145600479199640

9426383851235514

7161

Returns: 391527813028185436
4628391593026948

9419466213218317

53719

Returns: 279155823583570812
763870999004343

6129173509583519

17

Returns: 394726897305233437
1715896604003664

8383585218566018

4213

Returns: 419449416669897840
4503599627370498

9007199254740993

1

Returns: 355784370562269186
8796093022210

9007199254740993

1

Returns: 697508186428538900
2251799813785248

9007199254840991

99999

Returns: 380588813585692008
68719576736

9007199254840991

99999

Returns: 498442501710439489
4503599627420496

9007199254790991

49999

Returns: 262732403991817330
10000000000000000

10000000000000000

12345

Returns: 56
9007199254840991

9007199254840991

99999

Returns: 107
1

10000000000000000

54673

Returns: 568706535983354931
1

100000000000000

5

Returns: 6613537488692710

Statistics

Problem Statement for "NAddOdd"

Problem Statement

Definition

Constraints

Examples