EllysConjectureDiv2
SRM 785 · 2020-05-08 · by espr1t
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
Constraints
- L will be between 1 and 1,000,000,000, inclusive.
- R will be between L and 1,000,000,000, inclusive.
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
42 1337 Returns: 6048
12345 67890 Returns: 259216
42666 133742 Returns: 425026
123456789 987654321 Returns: 4032921822
Submissions are judged against all 107 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class EllysConjectureDiv2 with a public method long long getSum(int L, int R) · 107 test cases · 2 s / 256 MB per case