Collatz Sequence Sum

             Collatz Sequence Sum
 
The following iterative sequence is defined for the set of positive integers:
                                                     
If at some point the value in the sequence is , we end the sequence at this point.
Using the rule above and starting with 13, we generate the following sequence:
It can be seen that this sequence (starting at 13 and finishing at 1) contains 10 terms. Although it has not been proved yet (Collatz Problem), it is thought that all starting numbers finish at 1.
Note: Once the chain starts the terms are allowed to go above N.
Note: Just for the purpose of this problem, we define that the sequence starting at 0 has total length of 0.
Let  g(K) be the largest integer not greater than , which generates the longest Collatz sequence. The task is to find the sum  
This is an online problem. It means that the input is generated using the below generation method:
N[0] = 0
for i = 1 to T:
   N[i] = (A * N[i-1] + B) mod 5003
Input Format
In the first line, there are three space-separated integers .
Constraints
Output Format
Print the sum of results for all  tests.
Sample Input
3 1 4
Sample Output
19
Explanation
The generator generates 3 numbers:
Let  g(K) be the largest integer not greater than K , which generates the longest sequence. Then g(N1) = 3 , g(N2) = 7 and g(N3) = 9 and respective length of these longest sequences are 8,17 and 20. The result is the sum of numbers generating these longest sequences, so it's equal to 3+7+9=19.

Code:

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution 
{
static int collatzSequenceLen(int n) 
{
        if (n == 0) {
            return 0;
        }
        if (n == 1) {
            return 1;
        }
        if (n % 2 == 0) {
            return 1 + collatzSequenceLen(n/2);
        }
        return 1 + collatzSequenceLen(3*n+1);
}

static int collatzSequenceSum(int T, int A, int B)
{
        int n = 0;
        int result = 0;
        while (T-- > 0)
        {
            n = (A*n + B) % 5003;
            int best_len = 0;
            int best_num = 0;
            for (int k = 0; k <= n; ++k)
            {
                int cur_len = collatzSequenceLen(k);
                if (cur_len >= best_len)
               {
                    best_len = cur_len;
                    best_num = k;
                }
            }
            result += best_num;
        }
        return result;
}
public static void main(String[] args)
{       
           Scanner in = new Scanner(System.in);
           int T = in.nextInt();
           int A = in.nextInt();
           int B = in.nextInt();
           int result = collatzSequenceSum(T, A, B);
           System.out.println(result);
           in.close();
}
}

Please do comment If u have any Queries!

Add a Comment

Your email address will not be published. Required fields are marked *