2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу 1, 2, 3  След.
 
 Гипотеза Коллатца
Сообщение28.02.2019, 23:37 


28/02/19
16
Для того чтобы доказать данную гипотезу, потребуется доказать 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$ - конечны

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

 Профиль  
                  
 
 Re: Гипотеза Коллатца
Сообщение02.03.2019, 17:09 
Аватара пользователя


12/10/16
637
Almaty, Kazakhstan
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$ не делится без остатка.

 Профиль  
                  
 
 Re: Гипотеза Коллатца
Сообщение02.03.2019, 20:45 


28/02/19
16
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}$$

 Профиль  
                  
 
 Re: Гипотеза Коллатца
Сообщение03.03.2019, 07:51 
Аватара пользователя


12/10/16
637
Almaty, Kazakhstan
интересная и красивая дробь, как бы его реализовать на 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} $

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

 Профиль  
                  
 
 Re: Гипотеза Коллатца
Сообщение03.03.2019, 09:31 


28/02/19
16
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$

 Профиль  
                  
 
 Re: Гипотеза Коллатца
Сообщение03.03.2019, 14:00 
Аватара пользователя


12/10/16
637
Almaty, Kazakhstan
вычисление нечётных чисел вида $\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}$

 Профиль  
                  
 
 Re: Гипотеза Коллатца
Сообщение03.03.2019, 15:05 
Аватара пользователя


12/10/16
637
Almaty, Kazakhstan
в последнем коде ошибка, должно быть:
Код:
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: нет, кажется здесь проблемы с копипастом, а код рабочий.

 Профиль  
                  
 
 Re: Гипотеза Коллатца
Сообщение03.03.2019, 16:08 
Аватара пользователя


12/10/16
637
Almaty, Kazakhstan
Saxartur в сообщении #1379500 писал(а):
и просто говорить, что любое четное число может быть получено

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

 Профиль  
                  
 
 Re: Гипотеза Коллатца
Сообщение03.03.2019, 17:40 
Заслуженный участник


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

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

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

 Профиль  
                  
 
 Re: Гипотеза Коллатца
Сообщение03.03.2019, 18:23 
Аватара пользователя


12/10/16
637
Almaty, Kazakhstan
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$ при котором из трёхэтажной дроби Коллатца получаются натуральные числа, обнаружил закономерность, сейчас думаю как это понятно записать. И эта закономерность работает для любых количеств этажностей (для любых количеств переменных и дробей)

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

 Профиль  
                  
 
 Re: Гипотеза Коллатца
Сообщение03.03.2019, 20:58 
Заслуженный участник


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

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

 Профиль  
                  
 
 Re: Гипотеза Коллатца
Сообщение03.03.2019, 21:52 


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

 Профиль  
                  
 
 Re: Гипотеза Коллатца
Сообщение04.03.2019, 08:07 
Аватара пользователя


12/10/16
637
Almaty, Kazakhstan
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$ разной чётности.
Но это ещё не те закономерности о которых я говорил в предыдущем посте, над его записью я ещё работаю.


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

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

 Профиль  
                  
 
 Re: Гипотеза Коллатца
Сообщение04.03.2019, 09:15 
Аватара пользователя


12/10/16
637
Almaty, Kazakhstan
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$ слишком разные степени двоек в дробях, да и количество дробей могут быть разные, но это никак не означает ложность гипотезы, а только то - что путём индукцией недоказуемо.

 Профиль  
                  
 
 Re: Гипотеза Коллатца
Сообщение04.03.2019, 13:11 
Заслуженный участник


20/08/14
11065
Россия, Москва
Учитывая формулировку - наверняка изучали, но что-то ссылок там всего парочка.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 35 ]  На страницу 1, 2, 3  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group