Java: Heap space error, Euler project 14

samtob

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?

Jeremy Stone

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.

Collected from the Internet

Please contact [email protected] to delete if infringement.

edited at
0

Comments

0 comments
Login to comment

Related

From Dev

Project Euler 14 Java

From Dev

Java Heap Space error is occurring

From Dev

Java Heap Space error is occurring

From Dev

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

From Dev

Project Euler 24 using java Logical Error

From Dev

Project Euler 24 using java Logical Error

From Dev

Project Euler #14 Tips in Haskell?

From Dev

An internal error occurred during: "Retrieving archetypes:". Java heap space when creating new Maven project

From Dev

Java Heap Space error while executing Mapreduce

From Dev

out of memory error, java heap space

From Dev

PIG using HCatLoader, Java heap space error

From Dev

Scala Android compile error - java heap space

From Dev

out of memory error, java heap space

From Dev

PIG using HCatLoader, Java heap space error

From Dev

Java Heap Space error while executing Mapreduce

From Dev

Mirth file reader - Java Heap space error

From Dev

Project Euler #23 in Java

From Dev

Project Euler 2 in Java

From Dev

Project Euler #8 in java

From Dev

Project Euler #23 in Java

From Dev

Project Euler #22 Java

From Dev

Project Euler 14th crashes

From Dev

project euler 14 using the state monad

From Dev

Questions regarding Haskell solution of Project Euler 14

From Dev

project euler 14 using the state monad

From Dev

Constant dspace error java.lang.OutOfMemoryError: Java heap space

From Dev

How to solve java.lang.OutOfMemoryError: Java heap space error

From Dev

Java - Altered Fibonacci Rabbits - Java Heap Space Error

From Dev

Error java.lang.OutOfMemoryError: Java heap space