Гипотеза Колатца07.07.2022 12:32

Доказательство гипотеза Колатца, Проблемы 3n+1,
Проблемы Какутани

Введение и результаты

Привет, Хабр! В данной статье мы рассматриваем гипотезу Колатца, которая заключается в следующем. Если мы возьмём произвольное число, то нам нужно посмотреть на то, чётное ли оно. Если чётное, то делим на два, если не чётное, то умножаем на 3 и прибавляем 1. Потом с получившимся числом делаем тоже самое. Например возьмём 5. 5 нечётное, значит умножаем на 3 и прибавляем 1. Получаем 16. 16 чётное, значит делим на 2, получаем 8. И так далее. 16→8→4→2→1. А дальше следующее 1→4→2→1→4… . Получаем цикл. Гипотеза Колатца заключается в том, что любое число после некоторого конечного числа операций, превратится в 1, то-есть войдёт в этот цикл. На данный момент методом компьютерного перебора было изучено 2 в степени 64 чисел. Все они приходили к циклу 1→4→2→1. В данной статье я докажу что все числа приходят к циклу 1→4→2→1, подтвердив гипотезу Колатца. Так же в данной статье будет рассмотрен вариант опровержения гипотезы. По сути гипотеза неверна в двух случаях, если есть другой цикл, кроме, 1→4→2→1. Или же существует число, которое бесконечно растёт.

Доказательство

Докажем, что каждое число, кроме 1, в последовательности содержит число меньше данного. В таком случае взяв произвольное число, и применив к нему доказательство мы получим число меньше данного. Применив к полученному числу доказательство, мы получим опять число меньше данного и т.д. В итоге мы придём к 1, что и требовалось доказать.

Рассмотрим натуральный ряд:

N={1,2,3,4,5,6,7,8,9,10,11,12,13,…}

Начнём последовательно применять правило для каждого числа:

N={1,2,3,4,5,6,7,8,9,10,11,12,13,…}

{1,10,2,16,3,22,4,28,5…}

После первого шага видно что для чётных чисел гипотеза верна, ведь они стали числами меньше исходного. Значит дальше следует рассматривать то что получилось от нечётных чисел. Применим правило для них. Так как получились все чётные (Ведь мы к нечётному прибавили 1, то дальше все будем делить на два):

{10,16,22,28,34,40,46,52}

{ 5 , 8, 11,14,17,20,23, 26}

Дальше опять, чередующийся в плане чётности ряд. На данный момент, мы один раз воспользовались правилом 3n+1 и один раз правилом n/2 для исходных нечётных чисел. Продолжим использовать правило:

{5,8,11,14,17,20,23,26,29,32,…}

{16,4,34,7,52,10,70,13,88,16,…}

Заметим, что числа: 7, 10, 13, 16. Изначально были: 9, 13, 17, 21. То-есть все они стали меньше изначального. Докажем, что для всего этого ряда верно утверждение о существовании числа меньше данного.

Действительно: Числа имеют вид: $K_{n}=K_{1}+4n, K_{1}=9$ . То-есть сначала умножаем на 3 и прибавляем 1. Получим: $3*K_{n}+1$ потом делим на 2, $(3*K_{n}+1)/2$ . Так как опять получилось чётное, опять делим на 2. Ведь мы берём каждое второе число, увеличив шаг в два раза. Получаем $(3*K_{n}+1)/4$ . Проверим когда получившееся число меньше данного:

$(3*K_{n}+1)/4<K_{n},\Leftrightarrow 3K_{n}+1=4K_{n}, \Leftrightarrow K_{n}>1» src=«https://habrastorage.org/getpro/habr/upload_files/06c/b2f/19c/06cb2f19c1aa848265913db24727407f.svg» /> То-есть, в случае если исходное число больше 1, мы получим число меньше данного. Лемма доказана. Заметим что для данной последовательности, мы один раз использовали 3n+1 и два раза n/2. Обозначим количество раз использования 3n+1, за X. Количество раз использования n/2 за Y. То-есть тут X=1, а Y=2. Заметим так-же, что тенденция пока следующая. Часть чисел из {5,8,11,14,17,20,23,26,29,32} после деления станет числом меньше данного, а часть чисел пойдёт дальше для следующего изучения. Дальше доказательство гипотезы сводится к следующему. Если доказать что на каждом шаге (При передачи ряда чисел), часть из них станет числом меньше данного, а часть передастся дальше, то получим следующее: Любые первые n натуральных чисел на каком-то шаге станут числом меньше данного. Что и требовалось доказать. Доказательство: Рассмотрим общий вид числа после шагов, он следующий <img alt=$ . Соответственно число станет меньше изначального если (3^xn+m)/2^y<n (1), где m это число вида (3 * (3* … (3*(3*(3×1 +1))+1×2)+1×4)+1×8) … +1×2y).

Лемма: m всегда меньше 3^x . Действительно m содержит степень тройки, однако начинает умножение на шаг раньше, с 1, а прибавление степени двойки меньше, чем умножение на 3, сравнивая темпы роста производных.

Лемма, докажем что 3^x<2^y . Доказательство от противного: если , 3^x>2^y» src=«https://habrastorage.org/getpro/habr/upload_files/764/e58/71a/764e5871a6bc729d34f0b301e8051c40.svg» />то неравенство 1 не выполняется.

Докажем что для любого числа над которым было X использований 3n+1 операций, достаточно что-бы было Y либо 2*Y шагов использования операций n/2. И тогда число обязательно станет меньше исходного. Где <img alt= . Где [] это функция округления вниз.

Доказательство: Заметил что раз после операции 3n+1, нечётное число станет чётным, то следующая операция обязательно будет n/2. Таким образом, Y>=X. То-есть, нужно доказать что после дополнительных операций n/2, число станет меньше данного. (Количество которых t в пределах $t \geq Y-X$ )

Рассмотрим неравенство 1 для если m = 0. В таком случае количество операций Y и X не зависят от самого числа, а зависят только от X или Y (Одно выражается через второе). Выразим Y через X и получим Y=[(log_2 3)*X+1] . Однако m убирать нельзя. Ведь если убрать m и все числа на каком-то шаге станут меньше исходного, что с m в знаменателе оно может и не стать меньше исходного. В случае если m не 0, количество операций будут зависеть от самого n. Перепишем неравенство 1.

n(2^y- 3^x)>m» src=«https://habrastorage.org/getpro/habr/upload_files/919/6d7/193/9196d7193082ab3963367b45be26cebe.svg» /> (2)

<img alt= (2^y-3^x)/m» src=«https://habrastorage.org/getpro/habr/upload_files/fce/dc4/fd0/fcedc4fd0f66ea4c5bfff2fd528b292f.svg» />

То-есть, в случае достаточно большой разницы степеней двойки и тройки, может появится условие на большое n. В таком случае ряд чисел может не перейти в раздел меньше исходных, а расти бесконечно далеко.

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

Действительно, если число получилось чётное, мы обязаны его делить на два: В таком случае получим: (3^xn+m)/(2^y2^y)<n . Или в виде неравенства 2 n(2^y*2^y-3^x)>m» src=«https://habrastorage.org/getpro/habr/upload_files/10f/d0a/faf/10fd0afaf4dc6ddffe1830417b37b6d9.svg» />, <img alt= m, \Leftrightarrow» src=«https://habrastorage.org/getpro/habr/upload_files/d12/e91/96e/d12e9196edc9480fc735ed2a6292a1ea.svg» />, Так как 3^x<2^y , то t=2^y-3^x/2^y>1» src=«https://habrastorage.org/getpro/habr/upload_files/6da/728/ea9/6da728ea9865fe94f843400c37691a4d.svg» />, <img alt= m, n >m/(2^yt)» src=«https://habrastorage.org/getpro/habr/upload_files/991/29d/af9/99129daf95dce0cc3d7cc9a886cd3ae5.svg» />

Значит n больше числа, которое меньше единицы. То-есть, получаем что на этом шаге получилось число меньше исходного независимо от исходного числа. Мы доказали второе утверждение леммы. А если число нечётное, то мы используем 3n+1, повышая X, то-есть по определению передаем дальше. Лемма доказана.

Осталось доказать основную теорему: То-есть, что на каждый следующий уровень передаётся ряд чисел с шагом, который позволит нам часть передать дальше, а часть сделать числами меньше исходного. И доказать что те числа которые мы передаём дальше, имеют такую же структуру. Докажем по индукции. База индукции тривиальна, поэтому перейдем к шагу.

$f(n)\Longrightarrow f(n+1)$

Есть набор чисел ${K_{1},K_{2},K_{3},K_{4},K_{5},K_{6},K_{7}, ... }$ они обладают рядом свойств:

Все числа четные.
Их разница имеет вид: — натуральное число
Часть множества после ряда Y и X операций станет множеством чисел меньше исходного.
Часть передается дальше с свойствами 1 и 2.

Если все числа чётные то мы должны разделить их на 2, и получим числа с разнице в 3n. То-есть чередующееся чётные и не чётные. Значит для половины мы умножаем на 3 и прибавляем 1, а половину делим на 2. По нашему условия не важно какой Y нам передается из прошлого ряда, но он точно не меньше X.

Ту часть исходных чисел, для которых мы использовали 3n+1, переходит дальше. С разницей в 2*3^n*3 . Потому что выбрав половину чисел мы умножили разницу на 2, а потом операцией 3n+1, умножили разницу на 3.

Остаются числа ${K_{2}/2,K_{4}/2,K_{6}/2,K_{8}/2,K_{10}/2,K_{12}/2, ...}$

Так как мы опять же, убрали половину чисел и разделили на 2, разница остаётся 2*3^n , Если все числа четные, тогда опять делим на 2, если все нечётные умножаем на 3 и как доказано выше передаёт на следующий уровень.

Получим: ${K_{2}/4,K_{4}/4,K_{6}/4,K_{8}/4,K_{10}/4,K_{12}/4, ...}$ , здесь шаг уже 3^n значит получим очередь из чётных и нечётных чисел. Заметим что Y увеличился на 2 от исходного множества, ведь мы два раза делили на 2. Если после этого Y стал равен Y=2*[(log_2 3)*X+1] то как уже доказано число гарантировано станет меньше исходного для всех чисел. Если нет, то продолжаем алгоритм с шага про числа чередующейся чётности, пока Y не дойдёт до нужной величины. Шаг Индукции доказан. Гипотеза доказана.

Вот и всё. Пару слов о значении данной работы. Данная работа относится к теории чисел. Теория чисел, наука которая изучает числовой ряд и его закономерности, являются одной из фундаментальных дисциплин в математике. История показывает, как часто фундаментальная математика находит своё применение в более прикладных сферах знания или даже в создании новых гаджетов.

Спасибо что уделили внимание, надеюсь что не ошибся.