Java：堆空间错误，欧拉计划14题

Question

我正在尝试解决项目欧拉问题第14号:

以下这个迭代序列是用于正整数集合的： - n → n/2 (n为偶数) - n → 3n + 1 (n为奇数)

使用上述规则，从13开始，我们生成以下序列： 13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1

可以看出，这个序列（从13开始，以1结束）包含10个项。虽然还没有被证明（考拉兹猜想），但认为所有起始数字最终都以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 我应该怎么做才能解决这个错误，并且如何改进我的代码？

- samtob

---

你最紧迫的问题是，在循环内部再次修改了“i”变量。因此，您目前未传递2到1000000之间的所有值。另一个提示：如果您已经知道从13开始的collatz序列长度为10，那么您是否可以利用这个事实来计算26的长度？ - Sirko

我明白你的意思。这是否意味着检查小于500,000的数字是不必要的？由于乘以2会使长度增加1 => 没有比大于500,000的数字产生更长的Collatz序列的小于500,000的数字吗？ - samtob

不行。但是你可以使用查找表，保存计算结果。因此，当你计算一个序列时，对于每个新数字，在查找表中查找是否已经存在该数字。如果是，则可以停止并使用现有的结果。此外，您还可以将在单个序列中遇到的所有数字及其相应的结果添加起来。 - Sirko

Answer 1

你遇到内存溢出的原因是，一些序列中的数字大小超过了32位Java整数的存储范围。因此，会发生算术溢出，while循环不会终止（直到列表变得太大并超出堆空间）。

如果你使用长整型而不是整数，你的代码应该可以完成运行。

然而，你没有必要存储所有数字。你只需要跟踪最佳起点和迄今为止看到的最长序列的长度。我倾向于提取一个方法/函数，它接受一个起始值并返回从那里开始的Collatz序列的长度。

- Jeremy Stone

Answer 2

可以通过使用命令行选项来增加JVM分配的堆大小：

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

请注意，这只是解决您的问题之一。例如，它可能会到达1,000,000，而不是113,282。

- Davide Lorenzo MARINO

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

- Abhishek Anand

Answer 4

你的方法很好，但使用ArrayList可能会导致失败。不要将每个可能的结果存储在列表中，而是尝试在两个条件上递增（currentCount++）。循环结束后执行以下操作： 如果（currentCount > previousCount）{ previousCount = currentCount; 将测试数字设置回迭代器 number = i }

- user13780764