Decadans 12 мая 2023 в 23:53

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

Простой

8 мин

11K

Пролог

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

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

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

Основная часть

Любое число в двоичной с.с. представлено последовательностью 0 и 1. Не однократно уже было сказано, что для гипотезы Коллатца достаточно рассмотреть все нечетные числа. Любое нечетное число в двоично с.с заканчивается как минимум на одну единицу: 100…01, но единиц в конце может быть и больше. Любая последовательность единиц в двоичной с.с. представима как 2ⁿ – 1 в десятичной с.с., где n – количество единиц. Следовательно любое нечетное число можно представить в виде:

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

3*(x*2*2ⁿ + (2ⁿ – 1)) + 1 =

3*x*2*2ⁿ + 3*(2ⁿ – 1) + 1 =

3*x*2*2ⁿ + 2ⁿ⁺¹ + 2ⁿ – 3 + 1 =

3*x*2*2ⁿ + 2ⁿ⁺¹ + 2ⁿ – 2.

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

(3*x*2*2ⁿ + 2ⁿ⁺¹ + 2ⁿ – 2)/2 =

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

2ⁿ *(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).

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

(x*3ⁿ + 3^n-1 + 3^n-2 + 3^n-3 + 3^n-4 +…+ 3⁰) * 2 * 2^n-m + (2^n-m – 1), где n-m = 0

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

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

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

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

Теперь давайте эту формулу представим для начального числа y.

Подставляем:

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

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

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

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

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

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

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

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

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

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

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

Общий случай:

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

Итого:

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

Взгляд №1

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

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

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

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

Или мы можем совместить y₁и y₂(т.к. y₁ может быть как четным, так и нечетным) -

Итого, получен ряд нечетных чисел, где первое нечетное число – (1), а второе – (3). Используя формулу (3), можно перефразировать гипотезу Коллатца – В любой рекуррентной последовательности, заданной рекуррентным соотношением (3) и натуральным числом y₀(без учета нуля) есть член – 1.

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

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

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

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

def zeroFunc(inpDegree):
    
    temp = bin(inpDegree) #функция возвращает двоичный код числа 
                # но вначале он пишет 0b, пример: bin(3) = '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()

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

Натуральное число	9	97	871	6171	77031
N полных шагов (проект «Collatz Conjecture»)	19	118	178	261	350
N полных шагов (моя программа)	19	118	178	261	350
N не полных шагов (по формуле (3))	4	19	27	42	53
N полных шагов / N не полных шагов	4.8	6.2	6.6	6.2	6.6

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

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

N шага (формула (3))	0	1	2	3	4	5	6	7	8
N шага	0	5	16	19	24	31	40	44	51
Число	27	31	121	91	103	175	445	167	283

N шага (формула (3))	9	10	11	12	13	14	15	16	17
N шага	56	70	81	84	87	92	96	106	111
Число	319	911	577	433	325	61	23	5	1

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

Взгляд №2

Обязательно ли деление на 2? Если мы смотрим на задачу со стороны
двоичной с.с., то при делении на 2 мы просто отбрасываем 0 в конце. А если
прибавлять 1 не в последний разряд числа в двоичной с.с., а в первый не нулевой
с конца? То это уже не единица, а 2^m, то последовательность
действий можно изменить с 3n + 1, n/2 на

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

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

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

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

Заменим эти громоздкие степени на k₁, k₂,… k_n

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

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

Стоит заметить, что k₁>= 0, и k₁< k₂< k₃<…< k_n< k.

Также, степень числа 3 растёт линейно, на 1 для каждой следующей дроби (кроме последней). В свою очередь степень числа 2 растёт, но не линейно. Фактически гипотеза Коллатца в данном случае сводится к вопросу: можно ли для каждого x подобрать такую m и такой набор k (k, k₁, k₂,…, k_n), чтобы равенство было действительно. Кстати, , где l - натуральное число больше нуля, иначе число 2^k - 2^k_nнельзя поделить на 3 нацело.

Циклы

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

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

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:

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

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

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

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

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

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

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

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

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

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

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

Теги:

Хабы:

Математика

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

Публикации

Истории

Ближайшие события