КОМПЬЮТЕРНЫЕ ПРЕДПОЛОЖЕНИЯ

  • Задача — Доказательство гипотезы Сиракуз
    — программирование на Pascal, Си, Кумир, Basic-256, Python

Задача — Доказательство гипотезы Сиракуз — программирование на Pascal, Си, Кумир, Basic-256, Python

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

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

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

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. 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

а = int(input())
б = int(input())
в то время как a<=b:
п = а
print(‘-> ‘,n, end=’ ‘)
пока n != 1:
если n%2 == 0:
п = п // 2
еще:
n = (n*3 + 1) // 2
print(n, end=’ ‘)
печать()
а += 1 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

алг гипотеза Сиракуз
нач
цел н,и,а,б
вводы а,б
нц для i от a до b
п := я
вывод «-> «,n,» »
нц пока n 1
если mod(n,2) = 0 то
п := дел(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

введите
вход б
для i = от a до b
п = я
напечатайте «-> » + n + » «;
в то время как n 1
если n%2 = 0, то
п = п2
еще
п = (3*n + 1) 2
эндиф
напечатайте n + » «;
в конце
распечатать «»
следующий мне 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

Вы нашли apk для андроида? Вы можете найти новые бесплатные игры для Android
и приложения.

Гипотеза Коллатца. Взгляд со стороны двойной системы вычислений

Время на прочтение

Дело было вечером, делать было нечего. Листал Ленту, увидев упоминание гипотезы Колатца, загуглил, заинтересовался своей простотой (как и все), решил поразвлекаться.

Мне ближе информатика и программирование, поэтому я решил зайти со стороны двойной системы вычислений.

Гипотеза Коллатца: возьмем любое натуральное число x. Если число чётное – делим его на два (х/2), если нечётное – умножаем на 3 и прибавляем 1 (3х+1). Повторяем все эти операции, пока число не станет равным единице. Любое натуральное число в итоге приходит в единицу.

y = x*2*2^n + (2^n – 1), где x,n ϵ N

Оно нечетное, поэтому произведем над ним это действие: 3n + 1

3*(x*2*2 n
+ (2 н
– 1)) + 1 =

3*х*2*2 н
+ 3*(2 n
– 1) + 1 =

3*х*2*2 н
+ 2 n+1
+ 2 н
– 3 + 1 =

3*х*2*2 н
+ 2 n+1
+ 2 н
– 2.

Нечетное число после 3n + 1 становится четным, и мы его делим на 2:

(3*x*2*2 n
+ 2 n+1
+ 2 n
– 2)/2 =

3*x*2 n
+ 2 n
+ 2 n-1
– 1 =

2 n
*(3*x + 1) + (2 n-1
– 1) =

(3*x + 1) * 2 * 2 n-1
+ (2 n-1
– 1).

Теперь взгляните на изначальное число и число, полученное после двух операций (одна для нечетного и одна для четного числа). Приведенные вычисления позволяют установить зависимость количества шагов от количества единиц на конце изначального числа в двоичной с.с. Не трудно догадаться, что следующее число будет:

(3*(3*x + 1) +1) * 2 * 2 n-2
+ (2 n-2
– 1).

(3*(3*(3*x + 1) +1) +1) * 2 * 2 n-3
+ (2 n-3
– 1).

Давайте обобщим формулу:

Вы можете видеть конечную сумму ряда степеней 3. Всё приводим к виду:

(x*3^n+ (3^n-1)/2)*2

Итого число x*2*2 n
+ (2 n
– 1), где x,n ϵ N
превращается в (x*3^n+ (3^n-1)/2)*2
за 2n шагов (n раз для нечетных числе и n раз для четных чисел).

Как вы могли заметить, на конце полученного числа присутствует множитель 2, следовательно число x*2*2 n
+ (2 n
– 1), где x,n ϵ N
 превращается в x*3^n+ (3^n-1)/2
за 2n + 1 шагов (n раз для нечетных числе и n + 1 раз для четных чисел).   

Пример, для наглядности:

КОМПЬЮТЕРНЫЕ ПРЕДПОЛОЖЕНИЯ

Теперь давайте эту формулу x*3^n+ (3^n-1)/2
представим для начального числа y.

y = x*2*2^n + (2^n – 1)


x= (y-(2^n-1))/(2*2^n )

(y-(2^n-1))/(2*2^n )*3^n+ (3^n-1)/2=


(y*3^n-6^n+3^n)/(2*2^n )+ (6^n-2^n)/(2*2^n )=


(y*3^n+3^n)/(2*2^n )+ (-2^n)/(2*2^n )=


(3/2)^n* ((y+1))/2- 1/2

Полученное число может быть как четным, так и не четным, то есть оно будет поделено на 2 m
, где m ϵ N.
Сразу встаёт вопрос величины m, как определить это число. Опять обратимся к нашей любимой двоичной системе счисления. Если число делится на 2, то в конце у него стоит 0 в двоичной с.с. Если оно делится на 2 m
, то в конце у него стоит m нулей в двоичной с.с.

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

Смотря на число 10100000111, человек без труда может определить сколько на конце единиц (в данном случае 3), но нужна строгая функция, определяющая это число. Опишем две функции: функцию нулей – f^0,
и функцию единиц – f^1.
Первая ставит в соответствие любому целому неотрицательному числу новое целое неотрицательно число, равное количеству 0 на конце данного числа в двоичной с.с., вторая делает все то же самое, но для единиц на конце данного числа. Опишем представление натуральных чисел в двоичной с.с.:

КОМПЬЮТЕРНЫЕ ПРЕДПОЛОЖЕНИЯ

Теперь опишем функцию нулей и функцию единиц:

f^1= a_0 (1+ a_1 (1+ a_2 (1+ a_3 (…))))


f^0= (1-a_0 )(1+ (1-a_1 )(1+ (1-a_2 )(1+ (1-a_3 )(…))))

Интересно то, что обе эти функции, применённые к одному и тому же числу не могут одновременно иметь значение больше 0 или одновременно быть равными 0. Одна из них равна 0, вторая целому числу больше 0. Также стоит обратить внимание на то, что функция нулей от числа 0 равна бесконечности (если использовать бесконечное количество разрядов для представление всех двоичных чисел, фактически это не значащие нули перед самим числом), или равна 1, если мы договариваемся не использовать не значащие нули перед числом.

Основная теорема арифметики утверждает, что каждое натуральное число, большее единицы, представимо в виде произведения простых чисел, причём единственным способом с точностью до порядка следования сомножителей.

Натуральные числа могут повторяться. Например, 12 = 2*2*3. То есть 2 присутствует во второй степени. Учитывая это вернемся к функции нулей, она возвращает степень двойки, которая присутствует в натуральном числе, переданном функции. Если в числе нет двойки в некой степени, функция вернёт ноль (хотя это 2 в 0 степени).

Ниже представлены графики для двух функций. Синий – функция единиц. Оранжевый – функция нулей. Первый график для промежутка от 1 до 15. Второй для промежутка от 501 до 515.

График 1

График 1
График 2

График 2

Как мы видим,
f^0
сдвинута относительно f^1
на единицу:

f^1 (x)= f^0 (x+1)


f^0 (x)= f^1 (x-1)

Рассмотрим элементарные математические операции с этими функциями:

f^0 (a)+f^0 (b)=f^0 (a*b)

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

<img source="f^0 (a)+1=f^0 (a)+f^0

= f^0 (a*2)” alt=”f^0 (a)+1=f^0 (a)+f^0

= f^0 (a*2)” src=”https://habrastorage.org/getpro/habr/upload_files/5c1/4b1/bbc/5c14b1bbce078d2f260d8224cce1b4e2.svg”>

f^0 (a)+b=f^0 (a)+f^0 (2^b)= f^0 (a*2^b )

Теперь для функции единиц. Но отталкиваться будет от функции нулей.

f^1 (a)+f^1 (b)=f^0 (a+1)+f^0 (b+1)=f^0 ((a+1)*(b+1))=


f^0 ((a+1)*(b+1))= f^0 (a*b+a+b+1)= f^1 (a*b+a+b)

f^1 (a)+f^1 (b)= f^1 (a*b+a+b)


f^1 (a)+b=f^0 (a+1)+f^0 (2^b )= f^0 (a*2^b+2^b )=f^1 (a*2^b+2^b-1)

f^1 (a)+b=f^1 (a*2^b+2^b-1)

Я рассмотрел лишь ограниченное число мат. операций, т.к. не хочу уходить в дебри определения всех возможностей этих функций, в частности умножение функции нулей от числа a на число b – это возведение в степень f^0 (a^b ).
Но самые важные вопросы по этим функциям в делении и вычитании. Там уже начинаются игры разума и много вопросов, т.к. появляются дробные числа, и отрицательные числа.

Вернемся к гипотезе Коллатца. Итак

первое число –

<img source="

y_0, ” alt=”

y_0, ” src=”https://habrastorage.org/getpro/habr/upload_files/34a/e94/a36/34ae94a36130483500627099719c17b3.svg”>

второе число –

КОМПЬЮТЕРНЫЕ ПРЕДПОЛОЖЕНИЯ

третье число –

КОМПЬЮТЕРНЫЕ ПРЕДПОЛОЖЕНИЯ

Или мы можем совместить y 1
и y 2
(т.к. y 1
может быть как четным, так и нечетным) –

КОМПЬЮТЕРНЫЕ ПРЕДПОЛОЖЕНИЯ

Итого, получен ряд нечетных чисел, где первое нечетное число –

, а второе –

. Используя формулу

, можно перефразировать гипотезу Коллатца
– В любой рекуррентной последовательности, заданной рекуррентным соотношением

и натуральным числом y 0


(без учета нуля) есть член – 1.

Я пробовал найти формулу общего члена последовательности, но тщетно. Может какой-нибудь математик это сделает. Т. к., мне кажется, что доказательство этой гипотезы через формулу общего члена последовательности элементарное, но нахождение этой формулы проблема (по крайней мере для меня).

Кстати, если в эту функцию

сразу подставить 1, то следующий член последовательности тоже будет 1. То есть эта функция (если гипотеза верна) в какой-то момент сходится к 1 и дальше каждый член равняется 1. Перефразирую, если бы была формула общего члена последовательности, то бесконечный член её последовательности был бы равен 1 (если гипотеза верна). Если гипотеза не верна, то бесконечный член был бы равен некому числу отличному от 1.

Так же в функцию

можно подставить четное число (хотя я все свои рассуждения вёл от нечетных чисел). В результате оно будет поделено на 2. Кроме того, при подставлении в неё нуля, она вернёт 0.

Я написал код программы на Python используя выведенные выше формулы:

 def zeroFunc(inpDegree): temp = bin(inpDegree) #функция возвращает двоичный код числа # но вначале он пишет 0b, пример: bin
= '0b11' temp = temp[2:] #поэтому здесь я обрезаю первые два символа строки temp = temp[len(temp)::-1] #здесь я переворачиваю строку задом на перёд, # так как считаем с конца нули (или единицы) counter = 0 #счетчик for i in temp: # выполняю цикл пока не кончится число или пока не встречу 1 if i == '0': counter += 1 else: break RealCounter = counter # считаю реальное количество шагов для достижения 1 return counter, RealCounter # возвращаю счетчик def oneFunc(inpDegree): # описание аналогичное функции нулей temp = bin(inpDegree) temp = temp[2:] temp = temp[len(temp)::-1] counter = 0 for i in temp: if i == '1': counter += 1 else: break RealCounter = int(2*counter + 1) return counter, RealCounter def stepFunc(inpDegree): RealCounter = 0 # Сначала делаю 3n + 1 некое количество раз One_K, tempCounter = oneFunc(inpDegree) RealCounter += tempCounter outDegree = int(((3/2) ** One_K) * (inpDegree + 1)/2 - 0.5) # Потом делаю n/2 некое количество раз Zero_K, tempCounter = zeroFunc(outDegree) RealCounter += tempCounter outDegree = int(outDegree/(2 ** Zero_K)) return outDegree, RealCounter def main(): degree = 9 #задаю нужное мне число counter = 0 # счетчик чисел полученных через выведенную формулу RealCounter = 0 # счетчик реального количества чисел while degree != 1: #print('-----' + str(counter) + '-----') degree, tempCounter = stepFunc(degree) #print(degree) RealCounter += tempCounter counter += 1 print(counter) print(RealCounter) print('-----------------') #print(RealCounter/counter) main() #Рисую графики функций нулей и единиц import matplotlib.pyplot as plt def drawFunc(): points = [] points0 = [] points1 = [] # Задаю интервалы рисования (501-516 в данном случае) for i in range(501, 516): points.append(oneFunc(i)[0]) points0.append(zeroFunc(i)[0]) points1.append(i) plt.plot(points1, points) plt.plot(points1, points0) plt.show() #drawFunc()

Эта программа позволяет подсчитать общее количество шагов до достижения единицы, и количество шагов при использовании моей формулы. Ниже привожу таблицу с числами с самым длинным путем до достижения единицы.

Как вы можете видеть, уменьшение количества шагов в 5 – 6 раз (для достижения единицы).

Все любят приводить в пример число 27. Поэтому не будем отходить от традиций. Ниже представлены числа и количество шагов, рассчитанные по формуле

.

Далее представлены графики:

<img src="https://habrastorage.org/getpro/habr/upload_files/14f/210/d5c/14f210d5c59b616bbbdc8163bc775111.png" alt="График для шагов по формуле

” title=”График для шагов по формуле

“>

График для шагов по формуле
График для всех шагов

График для всех шагов

         
Обязательно ли деление на 2? Если мы смотрим на задачу со стороны

двоичной с.с., то при делении на 2 мы просто отбрасываем 0 в конце. А если

прибавлять 1 не в последний разряд числа в двоичной с.с., а в первый не нулевой

с конца? То это уже не единица, а 2 m
, то последовательность

действий можно изменить с 3n + 1, n/2 на

КОМПЬЮТЕРНЫЕ ПРЕДПОЛОЖЕНИЯ

, и конечной точкой этих действий будет 2 k
.

Пример, для наглядности:

КОМПЬЮТЕРНЫЕ ПРЕДПОЛОЖЕНИЯ

Гипотезу Коллатца можно переформулировать так: любое целое число n, больше 0 при рекрусивном применении к нему формулы
График 1 рано или поздно должно прийти к числу 2 k
, где k – целое, не отрицательное число.

Это будет выглядеть так:

КОМПЬЮТЕРНЫЕ ПРЕДПОЛОЖЕНИЯ
КОМПЬЮТЕРНЫЕ ПРЕДПОЛОЖЕНИЯ

Теперь выразим отсюда число x, от которого мы и начали наши операции:

КОМПЬЮТЕРНЫЕ ПРЕДПОЛОЖЕНИЯ

Сократим эту многоэтажную дробь до нормального вида:

КОМПЬЮТЕРНЫЕ ПРЕДПОЛОЖЕНИЯ

Рассматривая эту гипотезу, ученые проверяют наличие циклов. Что такое цикл в данном случае? Это последовательность чередующихся четных и нечетных чисел. Четных – может быть сколько угодно (подряд стоящих), а нечетных – только одно число (подряд стоящее). Существуют ли числа, через которые априори не может проходить цикл?

Давайте попробуем описать все целые неотрицательные числа:

3n + 1

3n + 2

– этих трёх подмножеств достаточно, чтобы описать все числа.

Каждая формула описывает 1/3 всех целых неотрицательных чисел. На каждую их них приходится равное количество четных и нечетных чисел.

Используя операции, описанные в гипотезе (3n + 1, n/2), проверим эти три описанных подмножества на возможность к ним прийти.

1)    3x*2 m
= 3y + 1

2)    (3x + 1)*2 m
= 3y + 1

3)    (3x + 2)*2 m
= 3y + 1

y – нечетное число, которое мы проверяем на соответствие гипотезе, x – следующее нечетное число, полученное из y.

Рассмотрим подмножество 2:

(3×x×2^m)/3+(2^m-1)/3=y

Первую дробь при любых целых x можно поделить на 3 так, чтоб полученное число было целым.

Для рассмотрения второй дроби обратимся к нашей любимой двоичной с.с.

Условие делимости на 3 в двоичной с.с. – Число делится на 3 тогда и только тогда, когда сумма его цифр стоящих на четных местах отличается от суммы цифр, стоящих на нечетных местах, на число, делящееся на 3.

В 2 m
– 1 при всех четных mбудет равное количество единиц, стоящих на четных местах и единиц стоящих на нечетных местах, следовательно разница между ними равно 0, следовательно число делимо на 3.

В 2 m
– 1 при всех нечетных mразница между количеством чисел на четных не четных позициях будет всегда равна 1, следовательно число никогда не делимо на 3.

Рассмотрим подмножество 3:

(3×x×2^m)/3+(2×2^m-1)/3=y

Как вы можете видеть, ситуация аналогична подмножеству 2, следовательно рассуждения аналогичны, НО теперь при всех нечетных m мы получим целое число, а при всех четных нет.

Теперь рассмотрим подмножество 1:

(3×x×2^m)/3+(-1)/3=y

Как мы видим, при любых целых x, y всегда будет дробным, следовательно ни при каких условиях нельзя прийти в нечетное число из подмножества 3n, из другого нечетного числа. Это означает, что 1/3 всех целых положительных чисел априори на может попасть в цикл по гипотезе Коллатца.

Моя личная гипотеза: если гипотеза Коллатца верна, то нужно рассматривать только нечетные числа из подмножества 3n, т.к. к двум остальным подмножествам мы придём из этого. Это подмножество можно описать формулой 3 + 6*n.

P. S. Надеюсь мои рассуждения кому-то помогут

➤