Java: Heap space error, Euler project 14

Question

I am trying to solve project Euler problem number 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.

This is my approach:

public class Euler14 {

public static void main(String[] args) {
    int temp = 0;
    ArrayList<Integer> numbers = new ArrayList<>();
    ArrayList<Integer> numberOf = new ArrayList<>();
    
    for(int i = 2; i<1000000; i++) {
       
        numbers.add(i);
        temp = i;
        
        while(i!=1) {   
            
            if(i%2==0) {
                i = i/2;
            }
            
            else{
                i = (3*i)+1;
            }                    
            
            numbers.add(i);                
        }
        
            numberOf.add(numbers.size());
            Collections.sort(numberOf);
        
            if(numberOf.size()>1) {
                numberOf.remove(0);
            }
            numbers.clear();
            i = temp;
            
            System.out.println("Starting number " + i + "\n" + 
                               "Size: " + numberOf + "\n");  
    }     
}    
}

However, when running this program I get this error at i = 113282:

Exception in thread "main" java.lang.OutOfMemoryError: Java heap space

What could I do to resolve this error, and how can I improve my code?

Your most immediate problem, is that you modify the i variable inside the the loop again. So you currently do not pass over all values between 2 and 1000000. Another hint: If you already know, that the collatz sequence starting at 13 is of length 10, couldn't you use that fact for computing the length for 26? — Sirko
– Sirko, Commented Jan 31, 2016 at 10:28
I get your point. Does this mean that it is unnecessary to check the numbers smaller than 500 000? Since a multiplication of 2 results in an increase in length by 1 => there are no numbers smaller than 500 000 that produces a longer collatz sequence than those larger than 500 000? — samtob
– samtob, Commented Jan 31, 2016 at 10:52
Nope. But you could use a lookup, where you save the result o your computation. So when you compute a sequence, for each new number, have a look at that lookup, if the number is already present. If yo, you can stop and use that existing result. Also you can add all numbers you came across in that single sequence with their respective results. — Sirko
– Sirko, Commented Jan 31, 2016 at 10:57

Jeremy Stone · Accepted Answer · 2016-01-31 12:27:08Z

1

The reason that you are getting the OutOfMemoryError is that the sizes of some of the numbers in the sequences are too big to be stored in a 32-bit Java integer. Therefore arithmetic overflow occurs and the while loop does not terminate (until the list grows too big and exceeds heap space).

If you use longs instead of integers your code should run to completion.

However, there is no need for you to store all of the numbers. All you need to keep track of is the best starting point and the length of the longest sequence seen so far. I would be inclined to extract a method/function that takes a starting value and returns the length of the Collatz sequence that starts there.

answered Jan 31, 2016 at 12:27

Jeremy Stone

1713 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Davide Lorenzo MARINO · Accepted Answer · 2016-01-31 10:43:46Z

0

It is possible to increase heap size allocated by the JVM by using command line options:

-Xms<size>        initial Java heap size
-Xmx<size>        maximum Java heap size

Consider that this will only move over your problem. SO instead of 113282 it could arrive at 1.000.000 for example.

answered Jan 31, 2016 at 10:43

Davide Lorenzo MARINO

27k4 gold badges45 silver badges58 bronze badges

Comments

Abhishek Anand · Accepted Answer · 2016-01-31 14:53:20Z

0

There you go, not elegantly written, but works. :)

public static void main(String [] args){
    long temp = 1;
    int MAX = 13;
    int count = 0;
    long maxCount = 0;
    long maxNumber = 0;
    for(long i = 1000000;i >= 1; i--){
        count = 0;
        temp = i;
        while(temp != 1){
            count++; 
            if(temp % 2 == 0){
                temp = temp / 2;
            }else{
                temp = temp*3 +1;
            }
        }
        if(maxCount <= count){
            maxCount = count;
            maxNumber = i;
        }
        System.out.println("Number : "+i+" count : "+count);
    }
    System.out.println("Max Number : "+maxNumber +" Count : "+maxCount);
}

answered Jan 31, 2016 at 14:53

Abhishek Anand

1,99215 silver badges30 bronze badges

Comments

user13780764 · Accepted Answer · 2020-06-20 17:37:12Z

0

you have a good approach but using an ArrayList will probably lead you to fail. instead of storing each possible results in your list try incrementing ( currentCount++) on both conditions. after finishing the loop do this if( currentCount >previousCount){ previousCount=current set your test number back to your iterator number =i }

answered Jun 20, 2020 at 17:37

user13780764

Collectives™ on Stack Overflow

Java: Heap space error, Euler project 14

4 Answers 4

Comments

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

Comments

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related