Java: пространство ошибка Heap, проект Эйлера 14

Question

Я пытаюсь решить project Euler problem number 14:

Следующая итерационная последовательность определена для множества натуральных чисел:

• н → п/2 (п даже)
• п → 3n + 1 (п нечетно)

Используя правило выше, и, начиная с 13, мы генерируем следующую последовательность:

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

Можно видеть, что эта последовательность (начиная с 13 и заканчивая на 1) содержит 10 терминов. Хотя это еще не доказано (проблема Collatz), считается, что все стартовые номера заканчиваются на 1.

Какой стартовый номер, менее одного миллиона, производит самую длинную цепь?

ПРИМЕЧАНИЕ: После того, как цепь начнет, условия могут превысить один миллион.

Это мой подход:

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"); 
    }  
}  
} 

Однако при запуске этой программы я получаю эту ошибку при i = 113282:

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

Что я мог сделать, чтобы устранить эту ошибку , и как я могу улучшить свой код?

Answer 1

Причина, по которой вы получаете OutOfMemoryError, состоит в том, что размеры некоторых чисел в последовательностях слишком велики, чтобы их можно было хранить в 32-битном целочисленном Java. Поэтому происходит арифметическое переполнение, и цикл while не заканчивается (пока список не станет слишком большим и не превысит кучу пространства).

Если вы используете longs вместо целых чисел, ваш код должен работать до завершения.

Однако вам не нужно хранить все цифры. Все, что вам нужно отслеживать, это лучшая начальная точка и длина самой длинной последовательности, видимой до сих пор. Я был бы склонен извлечь метод/функцию, которая принимает начальное значение и возвращает длину последовательности Collatz, которая начинается там.

Answer 2

Можно увеличить размер кучи, выделяемую JVM, используя параметры командной строки:

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

Считают, что это будет двигаться только по вашей проблеме. SO вместо 113282, например, может достигнуть 1.000.000.

Answer 3

Там вы идете, а не изящно написано, но работает.:)

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); 
}