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:
- Start with a positive integer X.
- If the number you currently have is even, divide it by two.
- 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.)
- 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:
- 42 is even, so we divide it by 2 and get 21.
- 21 is odd, so we add 3, getting 24.
- 24 is even, so we divide it by 2, getting 12.
- 12 is also even, so we divide it by 2, getting 6.
- 6 is still even, so we divide it by 2, getting 3.
- 3 is odd, so we add 3 and get 6.
- 6 is a number we've had before, so we stop here.
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
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 = 2242
1337
Returns: 6048
12345
67890
Returns: 259216
42666
133742
Returns: 425026
123456789
987654321
Returns: 4032921822