Create an efficient way to sum

Question

i have wrote a code to calculate the sum of the lengths whereby

syra(1) = 1

syra(2) = n + syra(n/2) if n%2==0

syra(3) = n + (n*3) + 1

eg.

• syra(1) will generate 1
• syra(2) will generate 2 1
• syra(3) will generate 3 10 5 16 8 4 2 1
• lengths(3) will be sum of all syra(1),syra(2),syra(3) which is 11.

Here's the code :

public static int lengths(int n) throws IllegalArgumentException{
  int syra = n;
  int count = 0;    
  int sum = 0;
  if (syra < 1){
    throw new IllegalArgumentException("Value must be greater than 0");
  }else{
    for (int i=1; i<=syra; i++){
      count = i;
      sum++;
      while (count > 1){
        if ((count % 2) == 0){
          count = count / 2;
          sum++;
        }else{
          count = (count * 3) + 1;
          sum++;
        }
      } 
    }   
  }
  return sum;
}

Question is, if i blast the lengths with big value eg 700000, it will take very long time and do repeat step for those syra(10),syra(5)...which already appear in syra(3).

How can I fine tune the code to store some temp (array) of the overlap sequences?

Ok, according to the info, here's my another modified code with array, why it produce array index out of bound error?

public class SyraLengths{

public static void main (String[]args){
    lengths(3);
}

public static int lengths(int n) throws IllegalArgumentException{
    int syra = n;
    int count = 0;  
    int sum = 0;
    int [] array = new int [syra+1];
    array[0] = 0;
    if (syra < 1){
        throw new IllegalArgumentException("Value must be greater than 0");
        }else{


                for (int i=1; i<=syra; i++){
                    count = i;
                    sum++;

                    while (count > 1){

                        if(array[count] !=0){sum = sum + array[count];}

                        else if ((count % 2) == 0){
                            count = count / 2;
                            array[count]=sum;
                            sum++;
                        }else{
                            count = (count * 3) + 1;
                            array[count]=sum;
                            sum++;

                            }
                        } 
                }   
            }return sum;
}

}

Answer 1

Use a HashMap<Integer, Integer> to store results that you have already computed, and look up values there before trying to recompute them. This technique is known as memoization.

Answer 2

The technique you want to do is called memoization.

You will need to store output of those smaller calls in some data structure and then use it instead of calculating over and over.

Consider to use LinkedHashMap special constructor with accessOrder=True and overrriden removeEldestEntry() method. Read the javadoc LinkedHashMap. It's well described there.

Doing so, you can easily keep only those most used values and keep your cache reasonable small (i.e. mostly used 1000 elements).