Меню
Берется любое натуральное число. Если оно нечетное — то умножается на 3 и прибавляется 1, если четное — делится на 2. Таким образом получается последовательность.
Гипотеза заключается в том, что такая последовательность обязательно придет к 1. А если быть точнее, то к бесконечному циклу 1, 4, 2, 1.
Корректировка определения:
Возьмем число К такое, что все натуральные числа, от 1 до К, соответствуют гипотезе Коллатца. Рассмотрим К+1, число для которого гипотеза еще не подтверждена.
Если при постановке К+1 в начало последовательности хотя бы один элемент в ходе последовательности станет Кх меньшее чем К+1, то дальнейшая последовательность совпадет с последовательностью этого числа Кх, а значит и для К+1 гипотеза подтверждается.
Итак, теперь нужно доказать, что любое К+1 станет меньше самого себя по ходу последовательности.
Доказательство:
Начнем с простого.
Каждое число заканчивается на одну из десяти цифр.
У любого натурального числа бесконечное количество разрядов, например число 5 можно рассмотреть как бесконечность нулей с 5 в разряде единиц.
Дальше сложнее, хотя все еще очевидно:
При умножении большие разряды не могут влиять на меньшие, но меньшие на большие могут влиять.
При делении меньшие разряды не могут влиять на большие, но большие на меньшие могут влиять.
Рассматривая последние разряды, неизвестно каким является число в целом.
Поэтому, чтобы учесть все варианты нужно несколько шагов, которые будут объяснены позже:
Если при умножении окончание числа вышло за рамки рассматриваемого разряда, то излишек нужно отсекать, так как не важно что в следующем разряде, потому что все варианты и так будут рассмотрены.
Если при делении окончание числа не оказалось меньше исходного, то создается два варианта, каждый из которых нужно рассмотреть.
При делении на 2**N, r [tex]\le[/tex] N, где r – количество рассматриваемых разрядов, окончание числа откладывается для рассмотрения в больших разрядах.
Индикатором отношения Кх к К+1 будет не визуальное отношение нынешнего окончания к исходному, а соотношение 3**V1/2**V2. Где V1 - количество шагов 3n+1, а V2 - количество шагов n/2.
Рассмотрим разряд единиц:
Если К+1 заканчивается на четную цифру, то оно сразу делится на 2 и становится меньше К+1, а значит для любого четного К+1 гипотеза Коллатца подтверждается.
Нечетные окончания рассматривать бессмысленно, так как после умножения на 3 будет нельзя разделить на 4, так как для этого необходимо минимум 2 последних разряда, а сейчас рассматривается только 1.
Разряд единиц рассмотрели, теперь рассмотрим десятки:
Возьмем для примера 01:
Любое число заканчивающееся на 01, после шага будет заканчиваться на 04, а значит делиться на 4, и если это число не 1, то применимо примерное соотношение ¾, а значит любое К+1 заканчивающееся на 01, также соответствует гипотезе Коллатца.
Как пример окончания, которому нужно дальнейшее рассмотрение возьмем 03:
3, 10, 5, 16. Соотношением оказывается 9/2 и если разделить на 8, то число станет меньше исходного, но неизвестно делится ли все число на 8, так как известны только 2 последних разряда. Так что можно разделить на 4, и получив 9/8 появляется неразрешимая проблема: некоторые полученные окончания делится на 2, но это делать нельзя, так как неизвестно, делится ли все число на 8.
Рассмотрим немного подробнее для пояснения одного из шагов выше. Допустим, после умножения 03, получается число оканчивающееся на 310, тогда после закономерного деления на 2 получается 155, то есть два последних разряда — 55 а не 05, то есть для подробного рассмотрения необходимо продолжить оба варианта. И для каждого варианта нужно чтобы соотношение было меньше 1. А убрать число из рассматриваемых можно только если соотношение меньше 1, или если число уже столкнулось с неразрешимой проблемой, а значит его в этом разряде уже бессмысленно рассматривать.
В продолжение темы окончания 3 возьмем 0003:
0003 - 1
0010 - 3
0005 / 5005 - 3/2
0016 / 5016 - 9/2
0008 // 5008 / 2508 // 7508 - 9/4
0004 /// 5004 // 2504 /// 7504 / 1254 /// 6254 // 3754 /// 8754 - 9/8
0002 5002 /// 2502 7502 /// 1252 6252 /// 3752 8752 / 0627 5627 /// 3127 8127 /// 1877 6877 /// 4377 9377 - 9/16
Как видно, рассмотрены любые варианты окончаний, которые могут появиться при взаимодействии с окончанием 0003 в контексте Гипотезы Коллатца.
И таким образом необходимо рассматривать все больший и больший разряд.
Например такой код:
- Код: Выделить всё
#packing of basic elements of further calculations.
def preparation(x_1, x_2):
for i in x_1:
y_1 = i
y_2 = i
y_3 = i
y = [y_1, y_2, y_3]
x_2.append(y)
def step(initial, final):
for j in initial:
#constant basic element.
primordial = j[0]
#element that change with rule of Collatz conjecture.
going = j[1]
#element whose changing depends on "going".
#and element being compared with "primordial".
checking = j[2]
#if element in "next_step" check is not needed.
if primordial not in next_step:
if going % (2**n) == 0:
going = going // (2**n)
checking = checking / (2**n)
if primordial < checking:
next_step.append(primordial)
elif going % 2 == 1:
going = 3*going+1
check = 3*checking+1
while going > 10**n:
going = going - 10**n
y = [primordial, going, check]
final.append(y)
elif going % 2 == 0:
going = going//2
check = checking/2
if primordial < check:
y = [primordial, going, check]
final.append(y)
going = going+((10**n)/2)
while going > 10 ** n:
going = going - 10 ** n
y = [primordial, going, check]
final.append(y)
next_step = []
n = 1
zero = [1]
numbers = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
initial = []
preparation(zero, initial)
final = []
for i in range(1, 100):
step(initial, final)
initial = final
final = []
print(len(next_step), next_step)
zero = []
#increasing of massive in 10 times
for i in numbers:
for j in next_step:
y = j + i*(10**n)
zero.append(y)
n = 2
next_step = []
initial = []
preparation(zero, initial)
final = []
for i in range(1, 100):
step(initial, final)
initial = final
final = []
print(len(next_step), next_step)
zero = []
for i in numbers:
for j in next_step:
y = j + i*(10**n)
zero.append(y)
n = 3
next_step = []
initial = []
preparation(zero, initial)
final = []
for i in range(1, 100):
step(initial, final)
initial = final
final = []
print(len(next_step), next_step)
zero = []
for i in numbers:
for j in next_step:
y = j + i*(10**n)
zero.append(y)
n = 4
next_step = []
initial = []
preparation(zero, initial)
final = []
for i in range(1, 100):
step(initial, final)
initial = final
final = []
print(len(next_step), next_step)
zero = []
for i in numbers:
for j in next_step:
y = j + i*(10**n)
zero.append(y)
n = 5
next_step = []
initial = []
preparation(zero, initial)
final = []
for i in range(1, 100):
step(initial, final)
initial = final
final = []
print(len(next_step), sorted(next_step))
В промежуточном итоге имеем, что после 1 шага оказывается что для 50% К+1 гипотеза подтверждена, после 2 — 75%, и хотя после 3 все еще 75%, после четвертого и пятого шагов процент продолжал увеличиваться. Если на каком-то из шагов удастся достичь 100%, то гипотеза будет доказана.
К 8-9 разряду уже остается 7.3%, только вот это 7.3 миллиона (из 100 000 000) 9-значных окончаний, которые надо прогнать через программу. Тем не менее 7.3 - примерное значение, полученное из первых 1000 окончаний, однако на данном этапе точность не имеет значения, так как даже для них к 100% прийти не удалось, а если бы и удалось, то все равно было бы нужно посчитать для остальных тоже. Попытка провести несколько чисел через 16 разряд окончилась тем, что вычисления заняли более 10 часов, после чего были остановлены. Чистый Python - не самый подходящий язык для настолько крупных вычислений, да и предложенный код наверняка не самый эффективный, тем не менее что-то подсказывает, что даже на Фортране для просчета даже 16 разряда потребуется слишком много времени. И, опять что-то подсказывает, 16 разрядом все не ограничится.
Ключевой вопрос, который я хотел задать в данной теме - существуют ли логические ошибки в самом способе доказательства.