Почему программа java замерзает на 113882?

Question

Я написал программу java, которая находит длину цепочки числа, используя последовательность collatz. Последовательность collatz: если число четное, разделите его на два, если нечетно, умножьте на 3 и добавьте один. Последовательность заканчивается, когда число достигает 1. Additional Info on Collatz Sequence. Моя программа находит длину цепочки чисел от 1 до 1 миллиона, но она останавливается на 113382. Не отображается сообщение об ошибке, программа просто прекращает печатать номера.

* edit: Я протестировал его, и выяснилось, что когда программа находится на 113383, цепочка сходится к отрицательным значениям. Может кто-нибудь объяснить это?

Я включил полный код, так как он очень короткий.

public static void main(String[] args) { 
    int max =0, maxChain=0; 
    for(int i = 2; i <1000000; i++) 
    { 
     int c =i; 
     int counter = 0; 
     while(c != 1) 
     { 
      if(c%2 ==0) c/=2; 
      else c= 3*c+1; 
      counter++; 
     } 
     if(counter > maxChain) 
     { 
      maxChain =counter; 
      max = i; 
     } 
     System.out.println(i); 
    } 
    System.out.println(max +" has a chain length of " +maxChain); 

} 

Answer 1

Для числа 113383, итерационные # 120 дает 827370449. Следующая итерация дает число 2482111348, которое слишком велико, чтобы соответствовать переменной int, поэтому она вызывает arithmetic overflow, которая обтекает отрицательный номер.

Оттуда все итерации приводят к отрицательному числу, и хотя результат повторяет циклы через -1, условие завершения цикла результата 1 никогда не встречается, поэтому получается бесконечный цикл.

Однако, если вы измените тип переменной на long, вы избежите переполнения (для этого стартового номера в любом случае), и последовательность завершается после 247 итераций.

---

Кстати, я нашел это, просто распечатав каждую итерацию, и стало очевидно, что произошло. Вы могли бы сделать то же самое и сами решить это. Отладка столь же полезна, как и кодирование, потому что все мы сталкиваемся с ситуациями кодирования, которые удивляют нас и самим находят причину, всегда более приятными и запоминающимися (так что вы снова не попадаете в ту же ловушку).