Доказательство гипотезы Сиракуз

Задача

Доказать гипотезу Сиракуз на диапазоне чисел. Гипотеза Сиракуз утверждает, что любое натуральное число сводится к единице в результате повторения следующих действий над самим числом и результатами этих действий.

  • Если число четное следует разделить его на 2.
  • Если нечетное, то умножить его на 3, прибавить 1 и разделить на 2.

Пояснение к задаче и алгоритм решения

  1. Запросить нижнюю и верхнюю границы диапазона чисел.
  2. Последовательно перебрать все числа от нижней до верхней границы включительно.
    1. Вывести на экран само число.
    2. Повторять до тех пор, пока число не будет сведено к единице:
      1. если число четное, то разделить его на 2,
      2. иначе умножить на 3, прибавить 1 и разделить на 2,
      3. вывести полученное значение на экран.

Если гипотеза Сиракуз верна, то программа рано или поздно завершится и зацикливания не произойдет, т.к. все числа будут сведены к единице.

Исходный код на языке программирования Pascal

var
    n, i, a, b: word;
 
begin
    readln(a,b);
    for i:=a to b do begin
        n := i;
        write('-> ', n, ' ');
        while n <> 1 do begin
            if (n mod 2) = 0 then
                n := n div 2
            else
                n := (3*n + 1) div 2;
            write(n,' ');
        end;
        writeln;
    end;
end.

Пример(ы) выполнения программы на языке Pascal

10
14
-> 10 5 8 4 2 1
-> 11 17 26 13 20 10 5 8 4 2 1
-> 12 6 3 5 8 4 2 1
-> 13 20 10 5 8 4 2 1
-> 14 7 11 17 26 13 20 10 5 8 4 2 1

Исходный код на языке программирования C

#include <stdio.h>
 
main() {
    int a,b,i,n;
    scanf("%d%d", &a, &b);
    for (i=a; i<=b; i++) {
        n = i;
        printf("-> %d ", n);
        while (n != 1) {
            if (n%2 == 0)
                n = n / 2;
            else
                n = (n*3 + 1) / 2;
            printf("%d ", n);
        }
        printf("\n");
    }
}

Пример(ы) выполнения программы на языке C

110
113
-> 110 55 83 125 188 94 47 71 107 161 242 121 182 91 137 206 103 155 233 350 175
263 395 593 890 445 668 334 167 251 377 566 283 425 638 319 479 719 1079 1619 2429
3644 1822 911 1367 2051 3077 4616 2308 1154 577 866 433 650 325 488 244 122 61 92
46 23 35 53 80 40 20 10 5 8 4 2 1
-> 111 167 251 377 566 283 425 638 319 479 719 1079 1619 2429 3644 1822 911 1367
2051 3077 4616 2308 1154 577 866 433 650 325 488 244 122 61 92 46 23 35 53 80 40
20 10 5 8 4 2 1
-> 112 56 28 14 7 11 17 26 13 20 10 5 8 4 2 1
-> 113 170 85 128 64 32 16 8 4 2 1

Исходный код на языке программирования Python

a = int(input())
b = int(input())
while a<=b:
    n = a
    print('-> ',n, end=' ')
    while n != 1:
        if n%2 == 0:
            n = n // 2
        else:
            n = (n*3 + 1) // 2
        print(n, end=' ')
    print()
    a += 1

Пример(ы) выполнения программы на языке Python

1533
1537
->  1533 2300 1150 575 863 1295 1943 2915 4373 6560 3280 1640 820 410 205 308 154
77 116 58 29 44 22 11 17 26 13 20 10 5 8 4 2 1
->  1534 767 1151 1727 2591 3887 5831 8747 13121 19682 9841 14762 7381 11072 5536
2768 1384 692 346 173 260 130 65 98 49 74 37 56 28 14 7 11 17 26 13 20 10 5 8 4 2
1
->  1535 2303 3455 5183 7775 11663 17495 26243 39365 59048 29524 14762 7381 11072
5536 2768 1384 692 346 173 260 130 65 98 49 74 37 56 28 14 7 11 17 26 13 20 10 5 8
4 2 1
->  1536 768 384 192 96 48 24 12 6 3 5 8 4 2 1
->  1537 2306 1153 1730 865 1298 649 974 487 731 1097 1646 823 1235 1853 2780 1390
695 1043 1565 2348 1174 587 881 1322 661 992 496 248 124 62 31 47 71 107 161 242
121 182 91 137 206 103 155 233 350 175 263 395 593 890 445 668 334 167 251 377 566
283 425 638 319 479 719 1079 1619 2429 3644 1822 911 1367 2051 3077 4616 2308 1154
577 866 433 650 325 488 244 122 61 92 46 23 35 53 80 40 20 10 5 8 4 2 1

Исходный код на языке программирования КуМир

алг гипотеза Сиракуз
нач
  цел n,i,a,b
  ввод a,b
  нц для i от a до b
    n := i
    вывод "-> ",n," "
    нц пока n <> 1
      если mod(n,2) = 0 то
        n := div(n,2)
       иначе
        n := div(n*3+1,2)
      все
      вывод n, " "
    кц
    вывод нс
  кц
кон

Пример(ы) выполнения программы на языке КуМир

3 10
-> 3 5 8 4 2 1
-> 4 2 1
-> 5 8 4 2 1
-> 6 3 5 8 4 2 1
-> 7 11 17 26 13 20 10 5 8 4 2 1
-> 8 4 2 1
-> 9 14 7 11 17 26 13 20 10 5 8 4 2 1
-> 10 5 8 4 2 1

Исходный код на языке программирования Basic

input a
input b
for i=a to b
        n =  i
        print "-> " + n + " ";
        while n <> 1
                if n%2 = 0 then
                        n = n\2
                else
                        n = (3*n + 1) \ 2
                endif
                print n + " ";
        endwhile
        print ""
next i

Пример(ы) выполнения программы на языке Basic

31
36
-> 31 47 71 107 161 242 121 182 91 137 206 103 155 233 350 175 263 395 593 890
445 668 334 167 251 377 566 283 425 638 319 479 719 1079 1619 2429 3644 1822
911 1367 2051 3077 4616 2308 1154 577 866 433 650 325 488 244 122 61 92 46 23
35 53 80 40 20 10 5 8 4 2 1
-> 32 16 8 4 2 1
-> 33 50 25 38 19 29 44 22 11 17 26 13 20 10 5 8 4 2 1
-> 34 17 26 13 20 10 5 8 4 2 1
-> 35 53 80 40 20 10 5 8 4 2 1
-> 36 18 9 14 7 11 17 26 13 20 10 5 8 4 2 1

Тема

Вложенные циклы

Уровень сложности

Средний

Дата публикации