Гипотеза Коллатца

[Saxartur]

Для того чтобы доказать данную гипотезу, потребуется доказать 2 леммы :
Лемма 1) Любое число вида $2^n+1$; $\forall n \in \mathbb{N} $ представимо в виде следующей дроби

$$\frac{\frac{\frac{\frac{2^{k_1}-1 }{3}2^{k_2}-1}{3}2^{k_3}-1}{3}2^{k_4}-1}{3}...$$

$k_1, k_2, k_3 ...,k_i \in \mathbb{N} \cup \{0\}$
$i\in \mathbb{N} $ , причем $i$ - конечна

Будем называть такую дробь - дробью Коллатца

Лемма 2) Пусть $y\in\mathbb{N}, y \geqslant 3$ число представимое в виде дроби Коллатца, тогда y+1 тоже представимо в виде дроби Коллатца, исключая тот случай, когда , $y+1=2^n, \forall n \in \mathbb{N}$

1) База индукции : $y=3$ ;

$$3=\frac{\frac{2^{4}-1 }{3}2-1}{3}$$

2) Пусть $t\in\mathbb{N} , t \geqslant 3$ число представимое в виде дроби Коллатца, докажем, что $t+1$ так же представимо в виде дроби Коллатца, исключая тот случай, когда $t+1=2^n , \forall n \in \mathbb{N}$, если же $t+1=2^n$ , то индукция все равно будет работать в силу леммы 1

3) Нужно доказать, что

$$\frac{\frac{\frac{\frac{2^{k_1}-1 }{3}2^{k_2}-1}{3}2^{k_3}-1}{3}2^{k_4}-1}{3}...+1= \frac{\frac{\frac{\frac{2^{m_1}-1 }{3}2^{m_2}-1}{3}2^{m_3}-1}{3}2^{m_4}-1}{3}...$$

$k_1, k_2, k_3 ..., k_i, m_1, m_2, ..., m_z \in \mathbb{N} \cup \{0\} $
$i,z\in \mathbb{N} $ , причем $i,z$ - конечны

И вот тут наступает ступор, не получается доказать ни первую, ни вторую лемму.
Есть какие мысли ?

[Soul Friend]

Saxartur в сообщении #1379141 писал(а):

Лемма 2) Пусть $y\in\mathbb{N}, y \geqslant 3$ число представимое в виде дроби Коллатца, тогда y+1 тоже представимо в виде дроби Коллатца, исключая тот случай, когда , $y+1=2^n, \forall n \in \mathbb{N}$

Опровержение:
$y=5$; $y+1=6$;
$(6\cdot 3+1)=19$ ; $19$ на $2$ не делится без остатка.

[Saxartur]

Soul Friend в сообщении #1379409 писал(а):

Опровержение:
$y=5$; $y+1=6$;
$(6\cdot 3+1)=19$ ; $19$ на $2$ не делится без остатка.

Немного не понял о чем вы. Число 6 представимо в виде дроби Коллатца :

$$ 6=\frac{\frac{2^4-1}{3}2-1}{3}2$$

А если вы о оригинальной формулировке гипотезы, то 6 - четное число поэтому его надо было делить на 2 , то есть имеем следующий набор преобразований : $6 \to 3 \to 10 \to 5 \to 16 \to 8 \to 4 \to 2 \to 1$

-- 02.03.2019, 21:55 --

В общем-то, я просто переформулировал задачу в обратную сторону, то есть надо доказать, что любое положительное число может быть получено из 1

Да, наверное все-таки стоило расписать дробь до конца, чтобы не было вопросов, я о том, что дробь всегда оканчивается на степень двойки, в том числе и на нулевую, то есть "дробь Коллатца" - это дробь следующего вида :

$$\frac{\frac{\frac{\frac{\frac{2^{k_1}-1}{3}2^{k_2}-1}{3}2^{k_3}-1}{...}}{3}2^{k_{i-1}}-1}{3}2^{k_i}$$

[Soul Friend]

интересная и красивая дробь, как бы его реализовать на Pari/GP ? Пока получается только для таких нечётных чисел:

for(i=1, 1000, if(ispower(i*3+1)==log(i*3+1)/log(2), print(i) ) )

Нужно добавить перебор с двумя переменными.
Лучше рассматривать только нечётные числа.

Saxartur в сообщении #1379141 писал(а):

Лемма 1) Любое число вида $2^n+1$; $\forall n \in \mathbb{N} $

а с остальными числами как (раз уж тема называется гипотеза Коллатца) ?

[Saxartur]

Soul Friend в сообщении #1379492 писал(а):

а с остальными числами как (раз уж тема называется гипотеза Коллатца) ?

Выполнение Леммы 1, нужно для доказательства Леммы 2 , так как очевидно, что $2^n$ непредставимо в виде такой дроби ( если ,конечно, само число $2^n$ не считать дробью Коллатца), то есть, если при переходе от $ y$ к $ y+1, y+1=2^k$ , то из Леммы 1, индукция продолжится т.к. из нее будет следовать, что $y+2$ представимо в виде дроби Коллатца

-- 03.03.2019, 10:35 --

Soul Friend в сообщении #1379492 писал(а):

Лучше рассматривать только нечётные числа.

Кстати да, действительно, тогда можно будет избавиться от степени двойки на конце дроби, и просто говорить, что любое четное число может быть получено умножением определенного нечетного числа на $2^n$

[Soul Friend]

вычисление нечётных чисел вида $\frac{\frac{2^m-1}{3}\cdot 2^n-1}{3}$ от i=1..1000:

for(i=3, 1000, for(m=0, 10, for(n=0, 10, if((((2^m-1)/3)*2^n-1)/3==2*i-1, print(i, "  ", m, "  ", n, "  ", ((((2^m-1)/3)*2^n-1)/3)*2^k-1)/3 ) ) )))

среди них присутствуют и числа вида $\frac{2^x-1}{3}$

для чисел вида трёхэтажной дроби:

for(i=3, 1000, for(m=0, 10, for(n=0, 10, for(k=0, 10,  if((((((2^m-1)/3)*2^n-1)/3)*2^k-1)/3==2*i-1, print(i, "  ", m, "  ", n, "  ", k, "  ", (((((2^m-1)/3)*2^n-1)/3)*2^k-1)/3 ) ) ))))

в этом случае при $m=2$, $n=2$ также получаются числа вида $\frac{2^x-1}{3}$

[Soul Friend]

в последнем коде ошибка, должно быть:

for(i=3, 100, for(m=0, 10, for(n=0, 10, for(k=1, 10,  if( (((((2^m-1)/3)*2^n-1)/3)*2^k-1)/3==2*i-1, print(i, "  ", m, "  ", n, "  ", k,"  ", (((((2^m-1)/3)*2^n-1)/3)*2^k-1)/3) ) ))))

хотя, кажется, они идентичны, но предыдущее выдаёт ошибку.

Upd: нет, кажется здесь проблемы с копипастом, а код рабочий.

[Soul Friend]

Saxartur в сообщении #1379500 писал(а):

и просто говорить, что любое четное число может быть получено

ну, пока что не любое а только вида $2^n+2$, которые ещё нужно доказать что они представимы дробью Коллатца.

[Dmitriy40]

А зачем вы перебираете i, если его можно получить из m,n,k? Просто проверив на (не)чётность то длинное выражение в скобках, что делается легко и просто?

Далее, если я правильно понял, то ищете числа, не приводящие к циклу 4-2-1, но минимальное такое число может иметь вид лишь $4n+3$, любые другие максимум за две итерации становятся меньше исходного минимального числа, что противоречие.

Ну и надо помнить что проверены все числа очень и очень далеко (говорят до $10^{20}$), так что индексы ваших степеней должны быть весьма большими, или циклов должно быть достаточно много.

[Soul Friend]

Dmitriy40 в сообщении #1379614 писал(а):

Далее, если я правильно понял, то ищете числа, не приводящие к циклу 4-2-1

нет, конкретно в последнем коде я ищу среди нечётных чисел от 3 до 199, числа, которые представимы в виде трёхэтажной дроби Коллатца $\frac{(\frac{(\frac{2^m-1}{3}\cdot 2^n-1)}{3}\cdot 2^k-1)}{3}$ . (они нашлись, и их много)

Изучая значения $m, n, k$ при котором из трёхэтажной дроби Коллатца получаются натуральные числа, обнаружил закономерность, сейчас думаю как это понятно записать. И эта закономерность работает для любых количеств этажностей (для любых количеств переменных и дробей)

код рабочий, только чтобы правильно скопипастить надо сначало её выделить, нажать на кнопку "вставка", а только потом из комментария скопировать.

[Dmitriy40]

Т.е. идёте от числа 1 в обратную сторону и ищете какие числа можно получить из него за максимум три шага (не считая степеней 2)? Искать то желательно какие числа нельзя так получить ...

И всё равно, при прямом ходе каждая итерация умножения увеличивает число не более чем в 1.5 раза (после умножения на 3 обязательно будет деление на 2). Значит для получения чисел порядка $10^{20}$ может потребоваться не менее $\log_{1{,}5}(10^{20})\approx120$ "дробей" обратного хода. Вы же пока ограничились тремя, это оставляет гигантские пропуски между найденными числами. Например число $27$ получается из 41 дроби.

[Saxartur]

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

[Soul Friend]

Dmitriy40 в сообщении #1379661 писал(а):

Т.е. идёте от числа 1 в обратную сторону и ищете какие числа можно получить из него за максимум три шага (не считая степеней 2)? Искать то желательно какие числа нельзя так получить ...

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

Итерируемая (повторяющаяся) часть дроби Коллатца - это $\frac{x\cdot 2^y-1}{3}$.
1)В этом случае, когда $x \equiv 0 \mod(3)$ нет целочисленных решений.
Целочисленные решения бывают только тогда, когда:
2) $\lceil\frac{x}{3}\rceil$ - чётное число, а $x$ и $y$ одинаковой чётности.
3) $\lceil\frac{x}{3}\rceil$ - нечётное число, а $x$ и $y$ разной чётности.
Но это ещё не те закономерности о которых я говорил в предыдущем посте, над его записью я ещё работаю.


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

И, интересно, изучал ли кто ранее такие дроби Коллатца, или же ТС первооткрыватель?

[Soul Friend]

Soul Friend в сообщении #1379722 писал(а):

Итерируемая (повторяющаяся) часть дроби Коллатца - это $\frac{x\cdot 2^y-1}{3}$.

то есть:
$x_{i+1}=\frac{x_{i}\cdot 2^y-1}{3}$

Saxartur в сообщении #1379670 писал(а):

На самом деле нужно доказать сложный индукционный переход (тогда все отлично), ну или доказать невозможность доказуемости таким образом

ИМХО: индукцией, возможно, недоказуемо, так как у чисел $y$ и $y+1$ слишком разные степени двоек в дробях, да и количество дробей могут быть разные, но это никак не означает ложность гипотезы, а только то - что путём индукцией недоказуемо.

[Dmitriy40]

Учитывая формулировку - наверняка изучали, но что-то ссылок там всего парочка.