Внезапный бесконечный цикл над определенным входным аргументом?

Question

Изучая Java, я переделываю некоторые проблемы с Project Euler. Речь идет о задаче 14 - Серия Коллатца последовательность: https://projecteuler.net/problem=14

Моя программа работает просто отлично для нижнего CEILING как 1000, но при выполнении, как он отправил петли бесконечно, я думаю? Что здесь не так?

public class Test { 
    public static void main(String[] args) { 
     int tempMax = 0; 
     final int CEILING = 1_000_000; 

     for (int j = 1; j < CEILING; ++j) { 
      tempMax = Math.max(tempMax, collatzLength(j)); 
     } 
     System.out.println(tempMax); 
    } 

    static int collatzLength(int n) { //computes length of collatz-sequence starting with n 
      int temp = n; 

      for (int length = 1; ; ++length) { 
       if (temp == 1) 
        return length; 
       else if (temp % 2 == 0) 
        temp /= 2; 
       else 
        temp = temp * 3 + 1; 
      } 
    } 
} 

Вызов System.out.println(collatzLength(1000000)); отдельно работает просто отлично, так что я думаю, что мы можем исключить ошибку здесь из.

Answer 1

Вы должны использовать long вместо int. int переполняется при выполнении вычислений в collatzLength, и это вызывает бесконечный цикл. Из описания проблемы:

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

число вызывает проблему: 113383

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

public static void main(String[] args) 
{ 
    int tempMax = 0; 
    final int CEILING = 1_000_000; 

    for (int j = 1; j < CEILING; ++j) 
    { 
     tempMax = Math.max(tempMax, collatzLength(j)); 
    } 
    System.out.println(tempMax); 
} 

static int collatzLength(long n) 
{ 
    long temp = n; 

    for (int length = 1;; ++length) 
    { 
     if (temp == 1) 
      return length; 
     else if (temp % 2 == 0) 
      temp /= 2; 
     else 
      temp = temp * 3 + 1; 
    } 
}