Project Euler 14(Collatz Conjecture), issue implementing cache in Java

skynil

I was solving Project Euler problems and I'm stuck at number 14, I did manage to solve it using brute force, the problem states: http://projecteuler.net/problem=14

The following iterative sequence is defined for the set of positive integers:

   n → n/2 (n is even)
   n → 3n + 1 (n is odd)

Using the rule above and starting with 13, we generate the following sequence:

   13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1

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.

Which starting number, under one million, produces the longest chain?

NOTE: Once the chain starts the terms are allowed to go above one million.

What I want to do is to implement a cache, I want to use an integer array as the cache, the index will be the number and the count stored in each cell will be the length of the chain, when we hit a number for which the cache cell already has a positive number we skip further checking(break the loop), fetch the existing counter data from the loop and add it to the current counter value, and start from the next number, so here's the implementation:

Working brute force code removed due to Project Euler policy, down below is the faulty code.

public class Challenge14 {

public static void main(String[] args) {
    
    int[] collatzCache=new int[1000000]; //cache
    
    int count=0;
    long maxCount=0;
    int maxNumber=0;
    long number;
    
    int limit=1000000;
    
    for(int i=0;i<limit;i++)
    {
        int counter=0;
        number=i;
        while(number>1)
        {
            if(number%2==0)
            {
                number=number/2;
            }
            else 
            {
                number=3*number+1;
            }

            if(number<limit && collatzCache[(int)number]>0) //check
            {
                counter=collatzCache[(int) number];
                break;
            }
            counter++;
        }
        count=counter+1;
        collatzCache[i]=count;
    if(count>maxCount)
    {
        maxCount=count;
        maxNumber=i;
    }
    }
    System.out.println(maxNumber);


}
}

But it's not working, where am I going wrong here? Is it due to the long to int typecasting?

Jackson

At this line:

counter=collatzCache[(int) number];

you overwrite what was in counter with the cache value and so lose the extra chain steps.

Collected from the Internet

Please contact [email protected] to delete if infringement.

edited at
0

Comments

0 comments
Login to comment

Related