TopcoderARCHIVE
Archive/Problems/EllysConjectureDiv2
SRM · Problem 16139

EllysConjectureDiv2

Problem statement, definition, constraints, and public examples.

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
← All problems