Statistics

Problem Statement for "EllysConjectureDiv2"

Problem Statement

Elly remembers hearing about the Collatz conjecture a long time ago, but apparently she doesn't remember it well. She only vaguely remembers that the conjecture involves a process in which we start with a positive integer and end with some positive integer. This is the process she remembers:

  1. Start with a positive integer X.
  2. If the number you currently have is even, divide it by two.
  3. If the number you currently have is odd, multiply it by 1 and then add 3 to it. (This is effectively the same as only adding 3 to the number.)
  4. Continue this process until you get to a number you've already seen. That number is the result.


For example, let's see what happens if we execute this process starting with X = 42:

  1. 42 is even, so we divide it by 2 and get 21.
  2. 21 is odd, so we add 3, getting 24.
  3. 24 is even, so we divide it by 2, getting 12.
  4. 12 is also even, so we divide it by 2, getting 6.
  5. 6 is still even, so we divide it by 2, getting 3.
  6. 3 is odd, so we add 3 and get 6.
  7. 6 is a number we've had before, so we stop here.
Thus, the result for X = 42 is 6.


Given the ints L and R, return the sum of the results for all starting numbers L ≤ X ≤ R.

Definition

Class:
EllysConjectureDiv2
Method:
getSum
Parameters:
int, int
Returns:
long
Method signature:
long getSum(int L, int R)
(be sure your method is public)

Constraints

  • L will be between 1 and 1,000,000,000, inclusive.
  • R will be between L and 1,000,000,000, inclusive.

Examples

  1. 13

    17

    Returns: 22

    The results for each of the numbers in the interval [13, 17] are: 4, 4, 6, 4, 4. Their sum is 4 + 4 + 6 + 4 + 4 = 22

  2. 42

    1337

    Returns: 6048

  3. 12345

    67890

    Returns: 259216

  4. 42666

    133742

    Returns: 425026

  5. 123456789

    987654321

    Returns: 4032921822

  6. 1

    10

    Returns: 38

  7. 1

    1000000000

    Returns: 4666666658

  8. 999999998

    999999998

    Returns: 4

  9. 999999999

    999999999

    Returns: 6

  10. 1000000000

    1000000000

    Returns: 4

  11. 782154

    893178543

    Returns: 4164516488

  12. 3287414

    791365741

    Returns: 3677698864

  13. 1

    1

    Returns: 1

  14. 1

    2

    Returns: 3

  15. 1

    3

    Returns: 6

  16. 1

    4

    Returns: 10

  17. 1

    5

    Returns: 14

  18. 1

    6

    Returns: 20

  19. 2

    2

    Returns: 2

  20. 2

    3

    Returns: 5

  21. 2

    4

    Returns: 9

  22. 2

    5

    Returns: 13

  23. 2

    6

    Returns: 19

  24. 3

    3

    Returns: 3

  25. 3

    4

    Returns: 7

  26. 3

    5

    Returns: 11

  27. 3

    6

    Returns: 17

  28. 4

    4

    Returns: 4

  29. 4

    5

    Returns: 8

  30. 4

    6

    Returns: 14

  31. 5

    5

    Returns: 4

  32. 5

    6

    Returns: 10

  33. 6

    6

    Returns: 6

  34. 1

    1000000000

    Returns: 4666666658

  35. 1

    999999999

    Returns: 4666666654

  36. 1

    999999998

    Returns: 4666666648

  37. 2

    1000000000

    Returns: 4666666657

  38. 2

    999999999

    Returns: 4666666653

  39. 2

    999999998

    Returns: 4666666647

  40. 3

    1000000000

    Returns: 4666666655

  41. 3

    999999999

    Returns: 4666666651

  42. 3

    999999998

    Returns: 4666666645

  43. 4

    1000000000

    Returns: 4666666652

  44. 4

    999999999

    Returns: 4666666648

  45. 4

    999999998

    Returns: 4666666642

  46. 5

    1000000000

    Returns: 4666666648

  47. 5

    999999999

    Returns: 4666666644

  48. 5

    999999998

    Returns: 4666666638

  49. 6

    1000000000

    Returns: 4666666644

  50. 6

    999999999

    Returns: 4666666640

  51. 6

    999999998

    Returns: 4666666634

  52. 608637543

    699753856

    Returns: 425209466

  53. 211680421

    999526835

    Returns: 3676616602

  54. 151077271

    248374502

    Returns: 454053748

  55. 723748677

    797756105

    Returns: 345368002

  56. 670094951

    935406814

    Returns: 1238122032

  57. 669991379

    769371771

    Returns: 463775168

  58. 249467211

    720860585

    Returns: 2199835750

  59. 574769066

    732343833

    Returns: 735348918

  60. 713197982

    753202239

    Returns: 186686538

  61. 253818730

    260878778

    Returns: 32946894

  62. 88409750

    330695626

    Returns: 1130667426

  63. 129236224

    452478632

    Returns: 1508464574

  64. 719653398

    983567481

    Returns: 1231599060

  65. 911989542

    915334311

    Returns: 15608928

  66. 780932288

    814383365

    Returns: 156105030

  67. 787716373

    944635393

    Returns: 732288764

  68. 306710476

    588068393

    Returns: 1313003616

  69. 41155564

    71505128

    Returns: 141631302

  70. 855189740

    954242116

    Returns: 462244426

  71. 250819633

    793536183

    Returns: 2532677238

  72. 667079111

    719864483

    Returns: 246331740

  73. 599121578

    799549097

    Returns: 935328426

  74. 254751708

    367470881

    Returns: 526022812

  75. 573512144

    720281724

    Returns: 684924712

  76. 958805694

    977208608

    Returns: 85880270

  77. 922662227

    937588560

    Returns: 69656226

  78. 857592371

    933770180

    Returns: 355496446

  79. 86347211

    158370008

    Returns: 336106390

  80. 750566082

    759826114

    Returns: 43213488

  81. 199502979

    801054367

    Returns: 2807239816

  82. 685582031

    800978817

    Returns: 538518340

  83. 732395541

    794043881

    Returns: 287692258

  84. 279394471

    336367032

    Returns: 265871956

  85. 219534974

    467776550

    Returns: 1158460692

  86. 147609286

    318490691

    Returns: 797446560

  87. 822927120

    884622480

    Returns: 287911686

  88. 308306185

    376880738

    Returns: 320014584

  89. 419498549

    830678506

    Returns: 1918839804

  90. 356208814

    747614134

    Returns: 1826558164

  91. 890440559

    936100060

    Returns: 213077676

  92. 524150215

    771652462

    Returns: 1155010490

  93. 126768637

    843191030

    Returns: 3343304504

  94. 147697583

    892293073

    Returns: 3474778958

  95. 389465908

    847990250

    Returns: 2139780266

  96. 111451556

    894149589

    Returns: 3652590826

  97. 449455770

    949626288

    Returns: 2334129090

  98. 338788866

    842397185

    Returns: 2350172160

  99. 61292156

    954394801

    Returns: 4167812348

  100. 946864536

    996971683

    Returns: 233833358

  101. 793943862

    928433426

    Returns: 627617970

  102. 57

    1000000000

    Returns: 4666666406

  103. 10

    1000000000

    Returns: 4666666624

  104. 1

    987654321

    Returns: 4609053490

  105. 1

    15

    Returns: 62

  106. 10

    987654321

    Returns: 4609053456

  107. 5

    12

    Returns: 38

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.
This problem was used for: