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?
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.
Comments