Comments 110
Слишком много воды, статью можно было бы сократить до пары абзацев.
Действительно, можно построить дерево, в каждый узел которого можно попасть одним или двумя путями. Дело за малым - доказать что это дерево содержит все натуральные числа. Вот где-то на этом этапе обычно и начинаются проблемы.
Не получится сократить до пары абзацев, потому что в математике всё, абсолютно всё нужно доказывать. Уникальность этой статьи в том, что мы наконец-то понимаем, что гипотеза Коллатца – это частный случай алгоритма. Эта статья посвящена полной версии алгоритма. И поэтому, по моему мнению, это прорыв в области 3n+1, т.к. более общий алгоритм наконец-то впервые дает нам представление о сути задачи. В статье подробно доказывается, что гипотеза Коллатца – это развернутая в обратном направлении рекурсия от рекурсии прародителя, и вычисляется шаг рекурсии прародителя. Такое доказательство опубликовано впервые.
Уникальность этой статьи в том, что мы наконец-то понимаем, что гипотеза Коллатца – это частный случай алгоритма.
Мы всегда это понимали.
И поэтому, по моему мнению, это прорыв в области 3n+1
Нет, увы. Все что изложено в статье - тривиально. Надеюсь в части 2 будет лучше.
Как правило, если в голову приходит какая-то гениальная мысль, точно такая же мысль приходила кому-то лет 100 назад, и этот кто-то умудрился проработать вопрос глубже чем вы могли себе даже представить. Нам же остается только прочитать то что написано до нас и надеяться что это вдохновит нас на следующее озарение, которое будет отставать от переднего края науки не на 100 лет, а хотя бы на 70.
Приведите пример математика и его работы, который это уже публиковал. На arxiv.org, где сидят спецы в области 3n+1, я не нашел такой работы.
И даже скажу вам больше, месяц назад я опубликовал эту работу на самом популярном в России математическом форуме dxdy.ru, и мне написали, что эта статья не может быть правдой, потому что здесь слишком всё легко и где-то есть ошибки.
и мне написали, что эта статья не может быть правдой, потому что здесь слишком всё легко и где-то есть ошибки.
Сформулируйте защищаемый тезис, пожалуйста. Из текста статьи он не очевиден.
Доказательство гипотезы Коллатца возможно лишь только при переходе от ограниченной версии алгоритма 3n+1 к более полной версии 
, потому что только тогда нам открывается шаг рекурсии, который охватывает все числа, не имеет циклов, и имеет только одного прародителя - единицу. Над этими вопросами бьются все исследователи проблемы 3n+1. Но безуспешно. Потому что решают не ту задачу.
охватывает все числа
Докажите.
И насчёт «лишь только» это вы тоже погорячились. Слишком сильное утверждение и в статье доказательств ему нет.
То есть, как я понял ваш ответ, вы открыли, что гипотеза Коллатца всё-таки доказуема, и вот эти парни
В 2007 г. математики S. Kurtz и J. Simon пришли к выводу, что в такой постановке вопроса задача 3n+1 не доказуема.
оказались неправы, так?
Тут и архив не нужен, вот вам википедия:
https://en.wikipedia.org/wiki/Collatz_conjecture#In_reverse
Обратите внимание на "The first 21 levels of the Collatz graph generated in bottom-up fashion"
Это дерево сгененировано из корня тем самым рекурсивным алгоритмом, который является кульминацией вашей статьи.
flx0, конечно, я это читал. Но то, что вы привели, это констатация факта, что можно шагать из N до 1, а можно шагать из 1 до N.
Статья не о том, в какую сторону мы шагаем. Статья о том, почему мы так шагаем. В статье подробно доказывается, почему шаг рекурсии именно такой, а не другой.
На основе доказанного нами шага рекурсии мы уже можем построить дальнейшее доказательство. И объяснить, почему рекурсия:
Не имеет циклов, повторов, зацикливания.
Есть только один прародитель – единица.
Почему рекурсия охватывает все натуральные числа.
Затея доказать т.н. "Гипотезу Коллатца", впрочем, как и подобную по "простоте" т.н. "Великую Теорему Ферма" (см. "Ферматисты"), - похвальна. Но Ваш материал сложен для чтения. Этот Ваш комментарий поясняет основные идеи работы. Если бы статья была написана столь же кратко и ясно, то, возможно, её приняли бы с меньшим скептицизмом.
Плохо искали.
Хотелось бы спросить у тех, кто в теме - есть ли физический или любой другой нематематический смысл в описаной задаче? Другие великие задачи из списка нерешённых проблем относятся к практическим проблемам топологии, геометрии и т.п. А эта?
Задача Коллатца сама по себе практического смысла не имеет, но еë ценность состоит в указании на то, что существующих инструментов для еë решения не хватает. Метод решения, если будет найден, даст новые инструменты для анализа динамических систем, теории графов и теории разрешимости. А эти области уже имеют массу практических применений.
"даст новые инструменты для анализа динамических систем, теории графов и теории разрешимости" - а откуда такие сведения?
Потому что 1) постановка задачи — это описание дискретной динамической системы и вопрос о еë аттракторах и притягивающем множестве, 2) к дискретным динамическим системам легко свести задачи на ориентированные графы (как это сделал автор статьи и многие другие) , 3) дискуссия о решении гипотезы быстро привела к дискуссии об условиях еë разрешимости.
Идея отобразить данную задачу дискретной динамической системой достаточно оригинальна и интересна (т.к. динамические системы отображают пространством состояний и системами дифференциальных уравнений на нём).
Первые мысли, которые пришли после прочтения условий задачи - это было решение её через исследование множеств на сходимость: доказать, что в получаемом ряде, начиная с некоторого элемента, последующие элементы меньше его, и этот ряд не переодичен.
Но это поверхностный взгляд, и мне кажется, это первая идея, которая приходит в данном случае в голову любому математику. :)
есть ли физический или любой другой нематематический смысл в описаной задаче?
Некоторый смысл есть в решении. Люди перестанут тратить время на попытки её решить (а потом ещё и испытывать разочарование от фиаско).
Безусловно. Механизм Коллатца - основа многих алгоритмов генерации псевдослучайных чисел, например, основанных на "seed" - числе и количестве итераций вызова.
Так что она служит нам буквально каждый день :)
вот тут
https://www.youtube.com/watch?v=QgzBDZwanWA
про это же, только более понятно и наглядно...
То есть, я, например, о задаче знал давно, но статья настолько ужасно написана, что даже зная о задаче, я с трудом дочитал это до конца...
я думаю, что все статьи\заметки\видео и т.д. должны обязательно начинаться с фразы
"простым перебеором были проверены все числа меньше 2^68 степени - и они все сходятся к циклу 4-2-1"
чтобы те, кто наивно думал что "там все просто" - были немного мотивированы так не думать :)
>>ужасно написана…
Математически строгий стиль не нравится ни кому. Вы правы. Но это математика. Я не мог бросаться выводами, как в этом видео, и не подтверждать их доказательствами.
То видео, которое вы привели, это всё-таки визуализация задачи 3n+1. Но статья посвящена не визуализации, а доказательству, почему последовательности Коллатца ведут себя так, а не по-другому.
Я всё же надеюсь что это была неудачная пятничная шутка.
1С программист :)
"Я нашел крайне интересное и простое решение этой задачи, но места в комментарии не хватит на его изложение "© П. Ферма
А почему вы собственно все не выложили на https://arxiv.org/ ? Тут то вы кому что хотите доказать?
До этого на хабре были статью про эту гипотезу и под одной я уже писал, постановка задачи вводит в заблуждение тем, что 3>2, но в алгоритме не просто 2, а 2^x. Я думаю не нужно опять расписывать, что среднее между всеми возможными 2^x будет всегда больше чем 3. Просто банальная теория вероятности говорит, что так как степеней двойки в бесконечном множестве чисел будет бесконечное число, то из этого ясно,что бесконечность>3 и число которое всегда будет расти по алгоритму не существует (точнее бесконечно исчезающая вероятность существования такого числа)!
Вот в этом и беда, что интуитивно задача понятна и элементарна. Но тут как в том выпуске Ералаша с параллельными линиями "Тут не пересекаются, а дальше?". Вероятность появления такого числа очень мала. Но как доказать, что его нет? Вот тут-то и ударяемся о стену головой, потому что "ды это очевидно" не является доказательством в силу того, что вероятность существования такого числа не ноль, а лишь стремится к нулю. А это, на бесконечном отрезке чисел, бесконечно большая разница. Нам же хватит всего одного числа из бесконечности, которое сломает-таки гипотезу.
Все мы понимаем, что эта штука работает. Но мы не понимаем, на каком моменте она сломается, если может сломаться. И подстава лишь в том, что найти этот момент, пока что, нет никаких вариантов, кроме брутфорса. Брутфорса бесконечного числового ряда... У нас есть квинтиллионы частных решений, но нет общего.
Ну, да вы правы! Даже зная, что выиграть в "русское лото" не возможно, искушение купить билет остается. Но это в лотерею сложно понять (она специально так устроена), а тут у нас обратная ситуация "не проиграть" постоянно играя. Это как летать на самолете для нас (быстро стареющих) безопасно, но для вечно живущего существа гарантированное самоубийство. С каждым шагом алгоритма встретить после шага 3*n+1 число вида c*2^x которое перечеркнет все наши потуги до этого стремится к 1.
Все мы понимаем, что эта штука работает. Но мы не понимаем, на каком моменте она сломается, если может сломаться. И подстава лишь в том, что найти этот момент, пока что, нет никаких вариантов, кроме брутфорса.
Достаточно представить, что каждое 4-е число в бесконечности будет кратно 4-м, и так на каждую 2^x и видно, что у нас половина чисел нечетных не "скатиться" к 1, но на шаге 3*n+1 все нечетные отображаються в четные. Теперь перед нами стена с безконечно чередующимися числами степеней двоек которых с ростом числа будет больше. как по мне тут очевидно, что даже брутфорс сломаеться.
... наконец то я понял что Вы сделали... Не знаю даже что сказать, но кажется это насмешка над математиками, которые до этого пытались доказать эту гипотезу :) Бывает, что профессионалы терпят фиаско
единственная статья (в мире), раскрывающая истинную природу гипотезы Коллатца.
Офигеть у автора самомнение. Корона нигде не жмет?
Все, что вы сделали, это посмотрели на дерево задом наперед. Настолько тривиальная идея, что я абсолютно уверен — она уже рассмотрена тысячу раз.
А вообще в вашем "алгоритме" ошибка.
Почему вы не нарисовали стрелочку от 13 в 4, ведь 13-1 делится на 3 и дает 4!
Т.е. ваш алгоритм пораждает цикл 4->8->16->5->10->20->40->13->4.
Поздравляю, вы опровергли гипотезу Коллатца (нет).
Почему вы не нарисовали стрелочку от 13 в 4, ведь 13-1 делится на 3
Во-первых, это не я рисовал. Это компьютер рисовал. Я программист. Не математик. Могу скинуть вам программу, которая рисует стрелочки.
Но вы на форуме программистов. И написать рекурсию из 10 строк кода, вы как бы по определению должны уметь.
Во-вторых, шаг рекурсии прописан строго и в нём нет такой операции, как 
.
В нём есть операции 
В параграфе 3 про алгоритм еще нет никаких (2n-1)/3. Только (n-1)/3 и 2*n
§3. Полная версия алгоритма
Сформулируем это так: Возьмем любое натуральное число n; Если оно нечетное, тогда умножаем на 2. Если чётное, тогда отнимем из него единицу.
Число 13 - нечетное. Его нужно умножить на 2.
Проблема в том, что в прямом процессе Коллатца решение об операции принимается в зависимости от начального числа, а в вашем обратном процессе — в зависимости от конечного (это самое n, из которого вы считатет (n-1)/3). Чтобы показать, что эти процессы действительно эквивалентны, надо показать, что начальное число будет обладать теми же свойствами, что и в прямом процессе. Это действительно так, но это надо бы доказать.
wataru, кстати, во второй части публикации, я выложил исходный код программы (для запуска рекурсии из единицы). Если что-то вам надо, может быть, чем-то помочь, какие-то вопросы, пишите.
Смотрите, я не претендую ни на какие доказательства. Если у вас есть идеи – публикуйте, можете здесь в комментариях.
Но, вот, что хочу сказать, рекурсия 
– это основная сущность. Гипотеза Коллатца - это урезанный алгоритм, и на него не стоит ровняться. 3n+1 – это производная форма от 
.
Как вы генерируете дерево, я уже понял. Код мне не нужен. Вы просто развернули все стрелочки в итеративном процессе, а потом исключили четные числа. Это ничем не помогает доказательству гипотезы коллатца.
Так-то без всех этих хитростей с нечетными числами, вот вам "шаг рекурсии":
Всегда можно домножить на 2. Если n == 1 (mod3), то еще есть "шаг рекурсии" (n-1)/3, если n четное.
И тут также можно доказать, что нет циклов в этом дереве (2a = (b-1)/3 => b=6a+1 => b — нечтное. Противоречие). И каждое число "цепляет какое-то другое число".
Принципиально от вашего дерева с нечетными числами не отличается ничем, но это все сильно проще.
Но основной вопрос остался тем же, а вдруг какое-то число из 1 не получается?
Но, вот, что хочу сказать, рекурсия \frac {n-1}{3} – это основная сущность
Офигеть, глубокое филосовское утверждение. Оказывается (n-1)/3 сильно связано с формулой 3*n+1.
Но основной вопрос остался тем же, а вдруг какое-то число из 1 не получается?
Я на него для себя ответил так.
Первое, предположим, такое число
есть.Второе, мы отталкиваемся от того, что повторов, циклов и зацикливания в рекурсии нет.
Третье, подставив такое число
в рекурсию 
мы получим противоречие. Потому что, прародитель (итерация назад) и рекурсия (итерация вперед) оба должны уйти в бесконечность. Смотрите, если прародитель не идет к единице, и не зацикливается, то у него остается только один вариант - уйти в бесконечность. Но это невозможно. Это противоречит самой сути алгоритма. Нельзя получить две бесконечности из одного и того же алгоритма (с тем шагом рекурсии, который мы установили).
Потому что, прародитель (итерация назад) и рекурсия (итерация вперед) оба должны уйти в бесконечность.
Нет. Почему нет чисел a->b->c->a? Ясно, почему нет последовательности 1->...->x->a->b->c->a, потому что не могут оба c и x привести к одному и тому же a. Но недостижимое из 1 a вполне может существовать. И прародитель и рекурсия проходят один и тот же цикл в разных направлениях.
Это противоречит самой сути алгоритма. Нельзя получить две бесконечности из одного и того же алгоритма
Почему? Вот контр пример. Шаг алгорима n -> n+2. Тут есть 2 бесконечности 1->3->5->… и 2->4->6->…
Пример тривиальный, конечно, но вы не привели никаких рассуждений, которые бы не были применимы к нему.
нужен строгий математик, очень строгий :)
Почему нет чисел a->b->c->a
Потому что мы имеем дело с рекурсией. В ваших рассуждениях вы апеллируете термином "последовательности". Но как вы себе представляете рекурсию? Её вообще-то нельзя остановить. Она бесконечна :)
Она бесконечна в любую сторону: 1 
1 
1 
1 
1 
... – это также движение по рекурсии.
Акцентирую. Для рекурсии нет такого понятия как отдельно взятая "последовательность" a->b->c->a.
Для рекурсии любое число имеет прародителя и потомков. Рекурсия с чего-то там начинается и куда-то продолжается. Перед а нужно ставить x:
…->x->a->b->c->a->…
Но как мы уже доказали, рекурсия не может так зациклиться. Тогда остается только один вариант: рекурсия уходит в бесконечность и слева, и справа. Но это невозможно, это противоречит нашему алгоритму:
Для 
движение к бесконечности – это просто формула 4x+1.
Для 3n+1 приземление – это просто формула 
.
При таком шаге рекурсии, при таком движении, алгоритм 
не может уйти в бесконечность и слева, и справа.
Алгоритм 3n+1 – это вообще обрубок, которому суждено только приземляться. Он просто следует по дереву, которое для него уже построили.
Потому что мы имеем дело с рекурсией.
Если вы хоть раз писали рекурсию, то должны понимать, что она отлично может бесконечно зацикливаться.
В ваших рассуждениях вы апеллируете термином "последовательности".
последовательность каких-то конкретных чисел, по которым ваша рекурсия "шагает". Один из путей в этом бесконечном "дереве".
Для рекурсии любое число имеет прародителя и потомков.
Но ничто не мешает иметь единственного потомка на том же цикле. Вы доказали, что перед a не может быть 2 разных потомков. Но x = c вполне возможно.
Еще раз, все ваши рассуждения применимы и к обычному дереву коллатца с четными числами. И там есть цикл 1->2->4->1.
Ответил вам во второй части публикации.
Из доказательства утверждения о том, что любое натуральное число достижимо из единицы с помощью процесса, названного Вами "рекурсия ", тривиальным образом следует доказательство гипотезы Коллатца.
@wataru задал совершенно правильный вопрос. Я лишь хочу его перефразировать, поскольку мне кажется, что суть вопроса осталась Вами непонятой.
Пусть 
- натуральные числа, не равные единице. Стрелка на картинке ниже обозначает применение шага рекурсии. Причём у каждого из чисел 
существует только один "прародитель" и только один "потомок" (в Вашей терминологии), т.е. не существует такого числа 
, после применения к которому "шага рекурсии" получалось бы число 
.
Какие из Ваших выкладок доказывают, что таких чисел не существует?
К сожалению, автор статьи на все вопросы отвечает:
Потому что мы имеем дело с рекурсией.
wataru:
Недостижимое из 1 число «a» вполне может существовать.
Ничто не мешает иметь единственного потомка на том же цикле.
NeOleg:
У каждого из чисел
существует только один "прародитель" и только один "потомок".
Давайте по порядку. Во-первых, двигаемся мы из единицы в бесконечность. И строго по тем правилам, которые прописаны в рекурсии.
Во-вторых, родитель у всех чисел может быть только один. Мы это доказали во второй публикации.
В-третьих, у «хвоста» всегда только 1 потомок, потому что он хвост. Уравнение: 
, не имеет решения. Единственный потомок для хвоста – это формула 4x+1.
У всех остальных чисел всегда два потомка: это комбинация 4x+1 и 
или комбинация 4x+1 и
.
Т.е. хвост не раздваивается. Остальные раздваиваются. Это надо понимать. Это прописано в шаге рекурсии.
Перейдем к вопросу.
Предположим, что число 
– недостижимо из единицы. Это значит, что помимо того, что оно зацикливается на самом себе, оно еще и рождает новое дерево:
Это дерево полностью состоит из циклов (что невероятно), либо уходит в бесконечность. Ну, допустим, это так.
Пройдемся по структуре циклов.
Правила не могут рождать цикл, потому что они образуют тривиальный сдвиг числа n на его величину 
.
, – в зависимости от того, какой сдвиг победит в этой «борьбе», число очень быстро достигнет единицы, либо бесконечности. Но без циклов.
Таким образом, цикл в гипотезе Коллатца возможен лишь в комбинации всех правил вместе взятых.
Итак, что мы имеем? Число 
– недостижимо из единицы. Отсюда следует, что абсолютно всё наше дерево 
тоже недостижимо из единицы. Тогда нам уже без разницы, какое из этих чисел находится в начале цепочки, а какое в конце. Они все для нас недостижимы.
Для простоты будем полагать, что 
– это первое применение правила 4x+1. В нашей терминологии – это хвост. У него один потомок и один родитель. Тогда:
Цикл – это такой случай в гипотезе Коллатца, когда число порождает само себя через правило 4x+1 и последующих сдвигов на 
со всевозможными их комбинациями 4x+1.
В моем понимании, это невозможно. Это нужно доказать. Я пока не готов. Скоро выйдет третья часть публикации. Ждем автора.
Недостижимое из 1 число «a» вполне может существовать.
Ничто не мешает иметь единственного потомка на том же цикле.
Ну так вот. Гипотеза коллатца вполне может не выполнятся. Ведь если она выполняется, то все числа должны приходить к 1. Или же в вашем развернутом процессе — все числа должны быть достижимы из 1.
Далее по вашему доказательству:
Во-вторых, родитель у всех чисел может быть только один. Мы это доказали во второй публикации.
Это не надо доказывать вообще. прородитель у числа — это следующее число в прямом процессе. Процесс однозначно задан — у каждого числа только одно следующее (3n+1 или n/2). Значит и прородитель в вашем развернутом процессе только один. Не надо никаких выкладок и рассуждений вообще.
В-третьих, у «хвоста» всегда только 1 потомок, потому что он хвост.
Там вы просто доказали, что у некоторых чисел млогут получатся только четные числа, которые вы исключили.
В моем понимании, это невозможно. Это нужно доказать. Я пока не готов. Скоро выйдет третья часть публикации. Ждем автора.
В этом и состоит основная сложность гипотезы коллатца.
Что значит "ждем автора"? Разве не вы автор?
В прямом смысле, ждем меня.
Потому что мне нужно время всё проверить. Не успеваю.
это следующее число в прямом процессе. Процесс однозначно задан — у каждого числа только одно следующее (3n+1 или n/2)
Гипотеза Коллатца, в моем понимании, – это "фальшивая" задача, с фальшивой (ограниченной) постановкой вопроса.
Не нужно использовать прямой процесс (3n+1 или n/2). Надо сразу переходить к обратной схеме. Потому что обратная схема охватывает всё дерево целиком, все последовательности сразу.
Такой процесс как 3n+1 или n/2 — он недоказуем. Мы это видим по другим работам математиков.
Гипотеза Коллатца, в моем понимании, – это "фальшивая" задача, с фальшивой (ограниченной) постановкой вопроса.
Бред какой-то, простите за грубость. Что значит "фальшивая" задача?
Это одна и та же задача, с какой стороны на нее не смотри. Какие-то подходы могут позволить легче доказать какой-то факт, но этот факт — это свойство заданного в задаче объекта.
Надо сразу переходить к обратной схеме.
Нет. Например, факт того, что у числа один "прародитель" гораздо легче доказывается в прямой постановке (он там дан уже!).
Вы выдумали какое-то глубоко филосовское обоснование, почему вы смогли доказать то, что не смогли миллионы очень умных математиков с очень глубокими познаниями и серъезным образованием. Оно у вас состоит в том, что вы единственный додумались развернуть процесс (что не правда). Чтобы придать этому какую-то значимость, вы просто отвергаете все существующие знания, как "фальшивые". Это непродуктивно и неоправданно.
Гипотеза Коллатца, в моем понимании, – это "фальшивая" задача, с фальшивой (ограниченной) постановкой вопроса.
Наверно, можно было бы рассмотреть какое-то расширение проблемы. Если при этом из доказательства некоторого утверждения в расширенной версии следовало бы доказательство гипотезы Коллатца, как частного случая.
Но проблема в том, что Вы не сделали никакого расширения. Ваш "обратный" процесс полностью идентичен "прямому" процессу. В "прямом" случае утверждается, что любое натуральное число приходит в единицу. В "обратном" случае единица должна порождать любое натуральное число.
Выбрасывание чётных чисел ничего не даёт. При желании это элементарно делается и для "прямого" процесса.
Так в чём же состоит "фальшивость (ограниченность)" прямой задачи по сравнению с обратной, если они полностью эквивалентны?
Видимо в том, что в гипотезе Коллатца мы от некоторого числа N упадем в единицу по некоторой фиксированной траектории (одной ветке дерева), а в случае обратной задачи мы из единицы покрываем весь ряд натуральных чисел, ветвясь как дерево :)
а в случае обратной задачи мы из единицы покрываем весь ряд натуральных чисел, ветвясь как дерево :)
Вы не доказали, что это дерево покрывает все числа. Я вот уже какой раз притащу сюда процесс 5n+1. Там точно такое же дерево растет из 1, но покрывает не все числа.
В обратном процессе вы покрываете только те числа, которые в прямом процессе уходят в 1. Что очевидно, ведь по этому же дереву можно взять и из далекой-предалекой вершины спускаться к прорадителям к 1.
Да я понимаю что строгого доказательства нет... Процесс 5n+1, вероятно, имеет более "слабую" природу, чем 3n+1, потому что деление на 3 более затратно деления на 5.
Что за бред вообще? Что значит "деление затратно"?
Вот если вы какие-то особые свойства деления на 3 докажете, то тогда да — о чем-то можно будет говорить.
Нет, здесь четко. Деление на 3 можно выразить как итерации:
def iter_div_3(x, xi):
xi = (x - xi) >> 1
xi = (x - xi) >> 1
return xiДля 32-битного x требуется не более 16 итераций.
Деление на 5 можно выразить как итерации:
def iter_div_5(x, xi):
xi = (x - xi) >> 2
return xiДля 32-битного x требуется также не более 16 итераций, но для деления на 5 одна итерация содержит три микрооперации (одно вычитание, два сдвига), а для деления на 3 -- четыре микрооперации.
Причем эти итерации несмещённые, т.е. дают точный результат деления. Это показывается полным перебором по x, например, от [1 до 2**32).
Что здесь за x, xi?
Какое отношение реализация деления на 3 через побитовые сдвиги и итерации имеет к обсуждаемой задаче? При чем тут 32-битные числа?
xi - итерируемая переменная, которая приближается к частному от деления x на 3 или 5. В процессе итераций x - константа, а xi - изменяется.
Я просто хотел показать, что деление на 3 сложнее деления на 5. Значит, потенциально, дерево для процесса 3n+1 будет самое богатое - и поэтому трудно доказать гипотезу Коллатца.
Весьма слабый аргумент. Очень субъективная метрика "сложности". Вы лишь показали, что они разные, ну так 3 != 5.
Вы зачем-то в делении на 3 "развернули цикл" и засунули сразу 2 итерации в цикл. Так что алгоритмы тут одинаковые. Хотя нет, для 5 там сдвиг на 2, что больше, чем сдвиг на 1 для 3 — значит деление на 5 сложнее!
И если рассматривать числа не до 2^32, а на другом промежутке, то итрация для 3 может сходится и быстрее, чем для 5.
Две подитерации в функции - это потому что исходной посылкой являются разложения в ряд Тейлора "сверху" и "снизу", чтобы обеспечить несмещенность процесса. Одна функция - одна итерация. Правда деления на 3 и 5 - как особые случаи - подобраны экспериментально (так получилось, хотя ряды использовались для ориентира). Деление на 7 -- уже полноценное (не особый случай):
def iter_div_7(x, xi):
xi = ((x + xi) >> 2) - xi
xi = (x + xi) >> 3
return xiКстати, я несколько ошибся по поводу сдвига. Сдвиг в терминах CPU - это одна операция, хоть на 2 бита хоть на 3 (там всё равно не больше 32-х при 32-битном регистре).
Битности я рассматриваю как раз-таки из-за ограничений CPU. То есть если мы проверили для 32-битных аргументов, то можно строго ничего не доказывать и использовать готовый результат. Эти итерации не очень очевидным образом следуют из рядов Тейлора. Здесь как бы смешиваются аналитика и интуиция (опыт) -- полуаналитические методы тоже имеют место в науке.
Всё-таки, я считаю, что на другом промежутке, в среднем, деление на 3 будет сходиться медленнее деления на 5 - монотонность, в среднем, сохраняется. Деление на 7 посложнее деления на 5, но деление на 3 всё равно сложнее. Примерная градация по кол-ву операций: деление на 3 требует 64 операции, деление на 5 -- 32, деление на 7 -- 50.
Две подитерации в функции — это потому что исходной посылкой являются разложения в ряд Тейлора "сверху" и "снизу", чтобы обеспечить несмещенность процесса.
Во-первых, а дайте-ка определение "несмещенного процесса". А заодно разложения в ряд тейлора "сверху" и "снизу".
А почему для 5 только одна итерация? Чем он несмещенный итак?
Нет тут никакого тейлора. Что вы в ряд раскладываете? x/3?
Сдается мне, что вы просто умными словами бросаетесь их даже не понимая. В прочем, это не новость, если вы вот эту вот статью защищаете.
Обе итеративные функции получаются преобразованием уравнений y = x/3 и y = x/5 к форме y = f(x,y). Тогда решение исходного уравнения будет неподвижной точкой функции F(y) = f(x,y), и при некоторых условиях (F — сжимающее преобразование), итерации y=F(y) будут к ней сходиться.
Преобразования элементарные и одинаковые что для 3, что для 5:
y = x/3
3y = x
2y+y = x
2y = x-y
y = (x-y)/2Что для 3, что для 5 тип неподвижной точки одинаковый и поведение будет одинаковое. Если у больше x/3 (x/5), то после одной итерации значение будет уже меньше x/3 (x/5) и наоборот.
Кстати, для 7 так в лоб сдвигами не получается, потому что будет y = (x-y)/6, ведь в отличии от 3 и 5, 7 не является 1+степень двойки. Но оно является степенью двойки-1. Поэтому можно преобразовать y = x/7 к y = (x+y)/8
Тут есть некоторый ньюанс с тем, что деление на 2,4,8 происходит нацело. Но можно доказать, что это на сходимость тут не влияет, только в случае с 7 из-за +y надо округлять вверх, чтобы преобразование осталось сжимающим.
Проверьте сами, эта итарация (xi = (x + xi + 7) >> 3) точно также сходится к ответу. Не надо никаких извращений вроде xi = ((x + xi) >> 2) - xi
Кстати и количество необходимых итераций доказывается — логарифм по основанию 2,4,8 от максимальной изначальной ошибки (2^32), потому что ошибка после такого преобразования меняет знак и сжимается в 2/4/8 раз. Вот поэтому вам и пришлось впендюрить 2 итерации для тройки, чтобы с той же скоростью сходилось. Но это не значит, что 3 "сложнее" 5. Просто 2 меньше 4.
Несмещенный процесс дает точное решение задачи, то есть с нулевой ошибкой. Не требуются никакие коррекции после основных итераций.
Дробь 
можно разложить в ряд Тейлора, если представить 
в виде суммы степени двойки и некоторой ошибки:
или
Первое выражение определяет ряд "снизу", второе - "сверху". Здесь 
. Выносим за скобки степень двойки и далее, например, дробь 
раскладываем в ряд по степеням малого параметра.
То, что Вы вывели итерации исходя из теории о сжимающих преобразованиях -- это, естественно, верно. Но я по натуре -- практик с хорошим радиотехническим образованием, поэтому мне трудно давать точные определения и док-ва :) Спорить с Вами не буду.
Два ряда Тейлора позволяют получить, соответственно, два итеративных выражения для произвольного 
.
xi = (x + xi + 7) >> 3, вообще не сходится.
Все сходится: https://godbolt.org/z/PaW5Ga8sj
Выводит "All good".
Это C++, правда, на питон сами перепишите?
Правда, да, оно работает, только если деление происходит нацело без остатка. Но формулы для деления на 3 и 5 тоже не сходятся, если деление идет не нацело (например при делении 5 на 3 будет осцилляция между 1 и 2)
А, да, сходится, но в том-то и дело что осцилляции. Я для этого две подитерации и сделал в одной итерации (функции).
правда насчет деления на 5 я ошибся, должно быть также две подитерации:
def iter_div_5(x, xi):
xi = (x - xi) >> 2
xi = (x + 3*xi) >> 3
return xiНу тогда и для деления на 3 должны быть 2 другие итерации:
def iter_div_3(x, xi):
xi = (x - xi) >> 1
xi = (x + xi) >> 2
return xiА не
def iter_div_3(x, xi):
xi = (x - xi) >> 1
xi = (x - xi) >> 1
return xiкак у вас изначально. Тут та же логика — "округляем" до ближайшей степени 2 вверх и вниз, делим на нее.
В итоге приходим к тому, что деление на 3 выглядит даже проще, чем деление на 5 (там нет никаких *3, а только сумма). И ваш изначальный аргумент, что вот итерации для 3 сложнее выглядят — не работает.
И вообще, я не понимаю, зачем делать 2 итерации "снизу" и "сверху". Итерация, которая с +xi — она поделит ошибку на 2/4/8. Итерация с -xi — она поменяет знак у ошибки, и опять же поделит ее на 2/4/8.
Сойдется в итоге и та и другая итерации, их не обязательно перемешивать. "Осцилляции" есть во всех ваших примерах.
Без осцилляции можно брать только итерации с +xi. Или два раза выполнять итерацию с -xi. тогда ошибка два раза поменяет знак, но это лишь заметание осцилляции под ковер. Она там все-равно внутри есть.
Но осцилляция-то все-равно сходящаяся, ведь ошибка по модулю делится на 2/4/8 всегда. Она ничего не портит, а наоборот решает проблемы с округлением из-за деления нацело. Когда ошибка большая по модулю, то округление ничего не портит — ошибка из-за деления на 2 становится меньше по модулю. Но когда ошибка +-1, то округление может создать проблему — ошибка не изменится по модулю. Если ее знак не меняется, то итерация "повиснет". Осцилляция же гарантирует, что на следующей итерации округление будет уже в другую сторону, ближе к 0, и итерация всегда сойдется.
Да, верно, для 3 надо поменять.
Я выразил деления через некоторый шаблон и попытался нормировать среднее количество итераций, чтобы оно меньше зависело от кол-ва тестируемых чисел [0, N]. По количеству итераций всё равно выигрывает деление на 3. Мне кажется, это фундаментальная причина. Понятное дело, что итерация деления на 3 не содержит умножений, но по шаблону там умножение на 1.
У 3 больше итераций потому что там ошибка сокращается каждый раз в 2 раза, а не в 4, как при делении на 2. Ну просто потому что 3 меньше 5. Никакая это не фундаментальная причина чего-то.
Потом, если брать только итерацию (x+xi) >> 2 для трех, то она тоже сойдется (если +3 еще добавить для округления вверх) с той же скоростью, что и деление на 5 "снизу".
NeOleg:
"обратный" процесс полностью идентичен "прямому" процессу.
Это не так. У нас есть два дерева. Одно дерево с чётными числами, другое без чётных.
Кто сказал, что они одинаковы!?
Я открываю Теорию графов, и там написано, что если деревья отличаются, то и алгоритмы их воспроизводящие отличаются.
Но мы ведь знаем, что не может быть двух гипотез Коллатца, верно?
Тогда вопрос уже к вам, какой алгоритм истинный, а какой «фальшивый» (переработанный)? Откуда ноги растут?
Дерево с нечетными числами натянуто на дерево со всеми числами. Оно по нему строится. Грубо говоря, вы смотрите на исходное дерево, но закрываете пальцами некоторые вершины, чтобы их не видеть. Структура дерева от этого не поменялась. Оно покрывает все те же нечетные числа. Новые туда не добавились, никакое число не исчезло.
Я открываю Теорию графов, и там написано, что если деревья отличаются, то и алгоритмы их воспроизводящие отличаются.
ГДЕ это написано? Опять вы аппелируете к умным терминам, вообще их не понимая.
Но мы ведь знаем, что не может быть двух гипотез Коллтаца, верно?
Бессмысленный набор слов, никак не связанный с остальным комметиарием.
Тогда вопрос уже к вам, какой алгоритм истинный, а какой «фальшивый» (переработанный)?
В математике нет общепринятых терминов "истинный" и "фальшивый". Может быть какой-то исходный объект и производные от него объекты. Ни один из них фальшивым не является.
Дерево с нечетными числами натянуто на дерево со всеми числами.
Давайте в ваших терминах. Итак, кто кого «натянул»?
Какой алгоритм исходный?
Исходно дан итеративный процесс 3n+1 и n/2. В постановке задачи. Он фундаментально ничем не лучше всех других процессов, но просто вот так получилось, что вот эта формулировка задачи "завирусилась".
Вы этот процесс развернули и выкинули из рассмотрения четные числа. При этом, если какое-то нечетное число в исходном процессе приходит к 1, то оно в вашем дереве из 1 получается. И наоборот. 1 к 1 соответствие — это эквивалентные процессы. Изоморфные, если хотите.
Вот Terence Tao в своей работе, на которую тут уже ссылались, во введении, в п. 1.2. вводит прямой процесс на нечётных числах. Дерево, полученное при такой формулировке гипотезы Коллатца, будет полностью идентично Вашему обратному графу.
Поставлю вопрос иначе.
Мы знаем, что в гипотезе Коллатца существует 2 дерева с чётными числами. Они используют разные вершины (узлы, точки) для прихода в единицу.
Можем ли мы тогда условно называть одно дерево "истинным", а другое "фальшивым"?
Вот нашёл картинку в интернете.
Это дерево в Вашем понимании "истинное" или "фальшивое"?
Для меня очевидно, что нет никаких "двух деревьев". Есть один граф на нечётных числах. По нему можно двигаться от какого-то числа в единицу (прямой процесс), или от единицы к какому-то числу (обратный процесс). Траектории будут абсолютно одинаковыми, изменится только направление.
Это дерево в Вашем понимании "истинное" или "фальшивое"?
Давайте, вот так. Мы "знаем" (на самом деле только я знаю), что есть 2 дерева с чётными числами.
Да, я понимаю, что веду себя нечестно. Потому что не выкладываю все карты на стол. Но скоро будет публикация, и вы поймете, о чем я говорю.
Итак, мы знаем, что в гипотезе Коллатца существует 2 дерева с чётными числами. Они используют разные вершины (узлы, точки) для прихода в единицу.
Можем ли мы тогда условно называть одно дерево "истинным", а другое "фальшивым"? Ведь дерево с нечетными числами оно одно, а деревьев с чётными несколько.
wataru:
Это одна и та же задача, с какой стороны на нее не смотри.
Процесс однозначно задан — у каждого числа только одно следующее (3n+1 или n/2)
wataru, а это уже комментарий для вас.
Что если помимо процесса 3n+1 или n/2 можно использовать другой процесс и построить совершенно другое дерево с чётными числами?
И оба они будут спускаться к единице, без циклов, только другим маршрутом.
Тут есть о чём подумать. Но слово рекурсия, оно какое-то непонятное. Терминология не раскрыта.
Что вам непонятно в рекурсии?
А что вы под этим подразумеваете?
Рекурсия – это описание (определение) какого-либо объекта (процесса) через самого себя.
Это ситуация, когда объект является частью самого себя, потому что он как бы сам себя породил (рекурсивно). В контексте нашей задачи, это значит, что все натуральные числа сами себя породили.
Простите, но разве в математике есть такой термин?
Да, конечно. Смотрите книгу С.Клини, «Введение в математику», 1952 год. На тот момент все виды рекурсий уже были описаны.
Я в каком-то комментарии уже разбирал это. Вы не используете термины из этой книги. Вы используете какие-то свои, никому непонятные термины. Там рекурсия — "рекурсивная функция". Функция — "соответствие между двумя элементами множеств" — заданная рекурсивно.
Вы так формально и не определили объект (процесс) и через самого себя его не задали.
Вообще, в википедии, откуда вы это определение (не вникая в него) скопировали, перечислены следующие примеры объектов, заданных рекурсивно:
- рекурсивная функция
- числовая последовательность заданная рекуррентной формулой
Вы не используете ни то ни другое.
Можно было бы рекурсивно определить, например, F(N) — "минимальное число, достижимое из N по формулам Коллатца". Тогда гипотезу можно было бы сформулировать так: "F(N) = 1 для всех натуральных N". Обратите, внимание, сам процесс, описанный в гипотезе коллатца (N/2, 3N+1) — не рекурсия. Это просто повторяющийся процесс.
Всё так! Вы правы. Я действительно, назвал алгоритм 3n+1 развернутой в обратном направлении рекурсией от рекурсии 
, хотя 3n+1 – это вообще не рекурсия. Это алгоритм. Мое допущение.
Но не судите строго. Эти «опечатки» суть не изменили. Всё, что мы проделали в первой части публикации – это никем из математиков не оспаривается.
Нет, вы все время ссылаетесь на какие-то "хвосты рекурсии" и "суть рекурсии", которая "не может уйти в бесконечность" и все такое. На этом ваше доказательство основано. Поэтому это важно. Но при этом сам термин вы коверкаете, как хотите, а вот уж эти его свойства вообще сами придумали и нигде не доказали.
wataru:
В прочем, это не новость, если вы вот эту вот статью защищаете...
Год назад, я спросил у математиков, почему рекурсия из 10 строк кода генерирует все последовательности Коллатца?
До сих пор я не получил ответа.
wataru, может быть вы хотите встать на сторону математиков? И объясните нам, почему так происходит?
А это не вы супер ОМП разработали?
На Ютубе есть канал Onigiri, интересный ролик про гипотезу Коллатца.
Помогите, пожалуйста.
Есть следующий код:
n = 7
iteration = 0
while iteration < 10000:
iteration += 1
if n % 2 == 0:
n = int(n/2)
else:
n = int(5*n + 1)
print(n)Запускаю его на 1С.
Указываю количество итераций: 500, 1000, 1500, 10000.
Получаю результат:
2296044483657086
7014269785336732191339839511433
214281478306217493968467132507143409334475117166
3767224397324212625018959046670386296144783512683083100759912969
Запускаю его на Питон:
2296044483657086
7014269785348883
2142814783086916
3767224421976616
Что не так с Питоном? Python 3.11.4 (2023), PyCharm (2023).
Решил проверить задачу 5n+1. Там сказано, что число 7 при старте сразу уходит в бесконечность.
Что не так с Питоном? Python 3.11.4 (2023), PyCharm (2023).
Проблема вот в этом коде:
n = int(n/2)Там вещественное деление на 2. В питоне нет длинных вещественных чисел, только целые. Ответ получается в типе, который хранит ограниченное количество значащих цифр, поэтому там происходит переполнение и потом ответ неправильный.
Чтобы делить на 2 нацело надо пользоваться оператором целочисленного деления //:
n = n//2Ну, и заодно, int() для 5n+1 вообще не надо.
Гипотеза Коллатца, часть 1