Почему цикл умирает? (Коллатца гипотеза)

Question

я пытаюсь некоторые математические-операции с Java, что делает проверить номер, если его (не) даже и изменить его до тех пор, как он получает 1.

Я пытаюсь запустить мой цикл для 999999times , он, кажется, застревает примерно в ~ 120000 раз. Ну, это не останавливается с Исключением, похоже, что компилятор застрял.

Я не так хорош с Java, может кто-нибудь объяснить мне, что здесь происходит?

public static void main(String[] args) { 

    int n = 0; 
    int highestNumber = 0; 
    int highestCounter = 0; 
    int counter = 0; 
    for (int i = 2;i<1000000;i++) { 

     if (i%10000==0) { 
      System.out.println(i); 
     } 
     n = i; 
     while (n!=1) { 
      if (n%2==0) { 
       n = n/2; 
      } else {  
       n=3*n+1; 
      } 
      counter++; 
     } 
     if (counter>highestCounter) { 

      highestCounter = counter; 
      highestNumber = i; 
      System.out.println("HIGHEST "+highestNumber+" | counter = "+counter); 
     } 
     counter = 0; 
     n = 0; 
    } 
    System.out.println("final "+highestNumber); 
} 

Answer 1

У вас переполнение, потому что 3 * n + 1 стало больше, чем Integer.MAX_VALUE. Таким образом, n получает отрицательный результат, и цикл while никогда не останавливается.

Используйте long вместо int для n!

Если вы хотите, чтобы проверить переполнение вместо:

while (n != 1) { 
    if (n % 2 == 0) { 
     n = n/2; 
    } else { 
     if (n > (Integer.MAX_VALUE - 1)/3) { 
      throw new RuntimeException("overflow!"); 
     } 
     n = 3 * n + 1; 
    } 
    counter++; 
} 

Дополнение для Java 8

Поскольку Java 8, Math класса предоставляет дополнительные статические методы для 'точной' арифметики (сложение, вычитание, умножение, деление), которые бросают ArithmeticException в случае переполнения. Используя эти методы, код может быть упрощена:

while (n != 1) { 
    if (n % 2 == 0) { 
     n = n/2; 
    } else { 
     n = Math.addExact(Math.multiplyExact(3, n), 1); 
    } 
    counter++; 
} 

Answer 2

Хм, ваш код выглядит хорошо. Вы решаете довольно типичную проблему

Является ли n целым? Если это коротко, вы можете переполнить его.

Кроме этого, максимальное значение целых чисел превышает 2 миллиарда, поэтому вы не должны его бить. Только в случае, попробуйте установить п на долго, чтобы увидеть, если это помогает

Edit: Возьмем, к примеру, число 77671 Согласно блоге я прочитал (читай: непроверенные) наивысший п для г = 77671 является 1047216490

Итак, я думаю, что n должно быть длинным, теперь, когда я думаю об этом подробнее

Answer 3

У вас проблема с переполнением. Измените код, как это и вы видите его:

while (n!=1) { 
     if(n < 0) throw new IllegalStateException("n should not become < 0" + n + "-" + counter); 
     if(n > ((Integer.MAX_VALUE -1)/3)) System.out.println("n too large. " + n); 
     if (n%2==0) { 
      n = n/2; 
     } else {  
      n=3*n+1; 
     } 
     counter++; 
    } 

если вы сделаете n к long он прекрасно работает.

Answer 4

Эта коррекция работы:

public static void main(String []args){ 
    long highestCounter = -1; 
    long highestNumber = -1; 
    for (long i = 2;i<1000000;i++) { 

     if (i%1000==0) { 
      System.out.println(i); 
     } 
     long n = i; 
     long counter = 0; 
     while (n!=1) { 
      if (n%2==0) { 
       n = n/2; 
      } else {  
       n=3*n+1; 
      } 
      counter++; 
     } 
     if (counter>highestCounter) { 

      highestCounter = counter; 
      highestNumber = i; 
      System.out.println("HIGHEST "+highestNumber+" | counter = "+counter); 
     } 
     counter = 0; 
     n = 0; 
    } 
    System.out.println("final "+highestNumber); 
} 

Answer 5

Вы просто работаете в бесконечный цикл внутри пока блок, добавьте System.out.println(counter); после counter++, чтобы увидеть, что происходит ..