Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 35
Лучше бы задачу Антигидры рассмотрели.
И легче Коллатца, и принесёт пользу — поможет найти значение BB(6).
Я не математик, и большую часть статьи сходу понять у меня не получается, но финал доказательства у меня вызывает вопрос. Вы утверждаете, что некая метрика D у бескорневой подсети должна быть строго меньше 3.5. А средний D по всем подсетям ~4. И это вы считаете противоречием, которое доказывает гипотезу от противного. Но вы сравниваете среднее значение со строгим - если среднее D ~ 4, это не значит, что какое-то из них не может быть меньше 3.5, разве нет?
dxdy.ru
Изложите своё решение там, послушайте что Вас скажут, это будет полезнее
Стандартный тест: если заменить 3n+1 на 5n+1, что именно в вашем доказательстве сломается? Потому что для этой модификации есть нетривиальные циклы, не содержащие 1. Прямо в первой сотне чисел - они руками даже находятся на бумажке.
Более того, в статье вроде как утверждается, что для 5 гипотеза верна:
5n−1/2 — аналог алгоритма Коллатца: единственный корень (1).
Что абсолютно не верно.
Так что где-то у вас в рассуждениях косяки.
Косяков нет. Просто Вы невнимательны:
страница 9
"при a = 5 противоречия не возникает"
Это значит, у алгоритмов 5n−1/2 и 5n+1/2 запрета на бескорневую подсеть нет.
Доказательство работает - делает правильный вывод о присутствии расходимости.
страница 11
5n−1/2 — аналог алгоритма Коллатца: единственный корень (1). Наличие
одного корня делает обязательным корневое дерево, критерий разрешает
бескорневую подсеть, последовательности в корневом дереве сходятся, в
бескорневой подсети расходятся.
5n+1/2 — 3 циклических корня (1, 3), (13, 83, 33), (17, 27, 43). Наличие
трех корней делает обязательным 3 корневых дерева, критерий разрешает
бескорневую подсеть, последовательности в корневых деревьях сходятся, в
бескорневой подсети — расходятся.
5n−1/2 — аналог алгоритма Коллатца по единственности корня.
Перечитал статью. Косяки есть:
Сходимость любого алгоритма типа Коллатца гарантирована в случае
односвязной сети с единственным корнем.
Не гарантированна а эквивалентна. Это просто переформулировка гипотезы.
Напомним постановку задачи по итогу первой статьи [1]. У алгоритма
Коллатца единственный корень 1, порожденный тривиальным циклом.
У вас еще первая статья с ошибками в доказательстве. Там как раз все аргументы ложатся на 5n+1 точно так же как для 3n+1. То, что никто пока перебором нетривиальные цикл для 3n+1 не нашел - не является математическим доказательством.
И аргументы вида "наиболее благоприятным для существования циклов является значение D = ±1". Не доказательство, что при |D| != 1 циклов нет, а просто "наиболее благоприятное". Я вам к прошлой статье контр-пример ваших аргументов даже привел (при D != 1 циклы есть в 5n+1 например), вы на него так и не ответили по существу: https://habr.com/ru/articles/870220/#comment_27724232
В этой статье вы рассматриваете односвязность сети, если типа единственный корень уже доказан. Но и односвязность вы тут не доказали.
Темп прогрессии Az при любом конечном стартовом ключе n1 монотонно убывает с ростом числа шагов
Ну, допустим, но только потому что мы зачем-то кроень z-ой степени извлекаем.
Расчетная проверка для алгоритма 3n+1 показывает, что делимость сети Δ вначале волатильна, затем дрейфует с затуханием вблизи 4 (см. Рис. 4
Расчетная проверка - это не "однозначное" доказательство. Так-то расчетная проверка для чисел до 10^18 а то и больше показала, что они все сходятся в 1. Но гипотеза Коллатца все еще считается не доказанной.
Поэтому без ущерба для сути можно принять, что делимость сети равна 4
Нет. 4 - это средняя делимость всех чисел. Но бесконечная нисходящая сеть может проходить только по каким-то особенным числам и иметь делимость как угодно отличающуюся от 4.
А из сохраняющегося неравенства делаем вывод, что нарушающая гипотезу Коллатца бескорневая подсеть должна иметь среднюю делимость D < 3.5, и эту оценку можно ужесточать вплоть до 3+, увеличивая длину цепочек.
Да, и вы пока нигде не доказали, что таких нет.
Далее вы почему-то переходите от этих цепочек к их обратным, что вообще-то не то, чтобы эквивалентно, и пытаетесь доказать, что уж там-то делимость достигает примерно 4.
Далее, основа аргумента - что строки типа альфа и бета чередуются и вроде как поэтому среднее близко к 4, ведь среднее по всем альфа - 3 а по бета - 7. Но! А что если внутри этих типов строк все не равномерно и среди альфа 2^1 встречается сильно чаще чем должно, а в бета - 2^2. Тогда среднее будет (2+4)/2 = 3, если именно эти делители доминируют.
Вам чтобы передел найти надо доказать вероятности всех делиетей, а не групп альфа и бета.
Другим «убийственным» аргументом в пользу существования инварианта
является наша Таблица для алгоритма 3n+3
Таблица - не доказательство в математике. Я вам могу привести таблицу: 3 - простое, 4 - не простое, 5 - простое, 6 - не простое, 7 - простое, 8 - не простое. Эта таблица "убийственно" доказывает, что все нечетные числа, больше 1 - простые.
Не собираюсь разбирать всю эту мешанину. Это бесполезно.
Первая статья не содержала в названии слова "доказательство",
она была о новом подходе, с демонстрацией его продуктивности.
Строго гипотеза Коллатца верна, если корень 1 единственный.
Именно это написано в новой постановке задачи - см. страницу 9.
Выискивая "косяки", Вы даже не поняли главного в новой статье:
независимо от того сколько корней и какие корни у алгоритма,
доказано, что все алгоритмы этого типа сходятся к своим корням,
если выполнен критерий a<Δ(c), запрещающий бескорневую подсеть.
Т.е. статья, озаглавленная "Однозначное доказательство и расширение гипотезы Коллатца" не является доказательством собственно гипотезы? А лишь доказывает одну ее часть в предположении, что вторая ее часть верна?
доказано, что все алгоритмы этого типа сходятся к своим корням, если выполнен критерий a<Δ(c)
Не доказано же. Я вам указал на проблему. Конкретно, не верно вот это утверждение:
Единственное возможное объяснение для D < 3.5 — перераспределение в пользу бескорневой подсети «плохих» указателей с наименьшей делимостью 2^1
Нет, не единственное. Можно оставить количество 2^1 неизменным и увеличить количество 2^2 за счет всех остальных, которые еще больше. Тогда среднее станет меньше.
Более того, вы не доказали, что нет перераспределения в пользу 2^1, вы лишь доказали, что совокупно 2^1,2^3,2^5,... дают половину вхождений, как и должны. То, что внутри между собой они не перераспределены вы не доказали.
Вот на последний вопрос действительно стоит ответить.
Дело в том, что мы имеем дело с сетью. Чтобы было понятнее,
придется загрузить картинку - визуализацию сети 3n+1/2.
Любой ключ (нечетное число) принадлежит какой-то подсети и неизбежно
вовлекает в ту же подсеть ВСЕ другие ключи, на которые ведет
вся серия указателей (четные числа 3n+1) в его строке.
Серия указателей дает ряд делителей (2 типа - альфа и бетта).
Обе сущности ассоциированы одному ключу и НЕРАЗРЫВНЫ.
Поэтому перераспределение делителей в строках невозможно.
Перераспределяться между разными подсетями могут только
строки целиком - они же ключи, серии указателей, ряды делителей.
У вас дырка в логике. Вам надо доказать что нет бескорневых подсетей, т.е. нет бесконечных прямых цепочек. Для этого вы пытаетесь доказать, что нет бесконечных цепочек со средним делителем меньше 3. Вот тут вы утверждаете, что средний делитель по всей сети такой, ведь каждая строка входит в подсеть вся. Но вам же не надо считать средний делитель всей подсети, а лишь по одной цепочки в ней. Вся подсеть может иметь средний делитель хоть 1000, но в ней все еще может быть одна единственная цепочка со средним делителем 2.5 и вся сеть будет бескорневой. Вы обратного не доказали.
Далее, вы неаккуратно работаете с бесконечными множествами. Вот вы утверждаете, что в каждую подсеть попадает вся строка целиком. И поэтому распределение делителей фиксированно. Но в каждой строке, где есть делитель 2^1, есть и делитель 2^3 и 2^1005001. Т.е. делителей 2^1005001 в сети столько же, сколько и 2^1 по вашей логике. Но если попытаться подсчитать среднее геометрическое всех этих чисел - вы получите бесконечность. Ибо вот та заветная 4 в вашей статье получается из суммы 1*1/2+2*1/4+3*1/8+... Т.е. делителей 2^1 - ровно половина всех, делителей 2^3 - 1/8 и т.д. Но ведь во всех строках они идут вместе - их одинаковое количество же! Как так?
Все просто - их всех бесконечное количество - счетное. Но их пропорции в общем бесконечном котле разные. Из того, что вы их выписываете в строки никак эти пропорции не следуют. Так что даже если бы вам надо было считать среднее по всей подсети, вы ничего не доказали.
Терпеливо объясняю.
Абзац 1 - нелепица. В сети НЕТ ИЗОЛИРОВАННЫХ ЦЕПОЧЕК И НЕТ СМЕШЕНИЯ СХОДЯЩИХСЯ И РАСХОДЯЩИХСЯ.
По стандартному алгоритму Коллатца: в корневом дереве ВСЕ последовательности сходятся, а в бескорневой сети ВСЕ последовательности не сходятся (расходятся).
Если ВСЕ последовательности расходятся, то средняя делимость по гипотетической бескорневой сети должна быть меньше 3.5 до 3+. (Часть 1 доказательства)
Но средняя делимость по ЛЮБОЙ реальной бесконечной подсети (в т.ч. бескорневой) около 4. Это инвариант для сетей с делением на 2 в алгоритме. (Часть 2)
Поэтому для алгоритма Коллатца существование гипотетической бескорневой сети НЕВОЗМОЖНО. Поэтому вся сеть - корневое дерево, все последовательности сходятся.
Абзац 2 - непонимание. Посмотрите на картинку ниже и поймите как считается делимость всей сети и подсетей. И почему это не бесконечность, а 4.
ПОДСКАЗКА. Считается она точно так же как делимость ряда четных натуральных чисел через среднее геометрическое, но с заменой членов ряда на указатели из алгоритма (картинка выше).
В сети НЕТ ИЗОЛИРОВАННЫХ ЦЕПОЧЕК И НЕТ СМЕШЕНИЯ СХОДЯЩИХСЯ И РАСХОДЯЩИХСЯ.
Как нету? Вот берете любое число, это будет первое число в цепочке. Применяете к нему правила Коллатца (3n+1, сократить все делители двойки) - получите второе число в цепочке. Повторяйте счетное количетсво раз. В безкорневой сети это будет бесконечная цепочка, НЕ ПРОХОДЯЩАЯ, по всем числам в подсети. Поэтому ее состав делителей может быть другим. Там в некоторых строчках берется только один конкретный указатель. И она может сходиться даже если сеть расходится.
То, что каждая из цепочек сходится, не занчит, что их объединение тоже должно сходиться. Потому что все эти цепочки могут иметь начало с большими делителями, которые в данной конкретной цепочке ни на что не влияют, потому что их конечное количество по сравнению с бесконечным хвостом, в котором полно маленьких делителей. Но когда вы скопом берете всю подсеть - объединение всех цепочек - у вас эти короткие начала начинают иметь значение, потому что бесконечный общий хвост во всю подсеть входит ровно один раз.
Вот вам упрощенный пример: бескорневая сеть состоит из одной бесконечной цепочки из вершин имеющих вес 1, в каждую вершину входит цепочка извершин с весами 10. Вес каждой цепочки всегда в среднем равен 1, потому что там конечное начало из 10, а потом бесконечный хвост из 1. Но во всей сети вершин с весом 10 бесконечно больше чем с весом 1, так что там среднее будет 10.
Каждая цепочка имеет вес 1, но их объединение имеет вес 10. Потому что общий хвост в объединении считается только один раз суммарно, а не подному разу от каждой цепочки.
В более сложном примере по мере движения плотность 1 растет. Эффект будет точно таким же.
Судя по этому сумбурному комменту, Вы не понимаете что такое Сеть.
Тогда для начала задумайтесь, что такое Дерево Коллатца. Различные траектории спуска по этому Дереву - это и есть стандартные нисходящие последовательности, заканчивающиеся корнем 1. И все они СВЯЗАНЫ и, как и все полное Дерево, порождаются ветвящимся восходящим алгоритмом, обратным стандартному алгоритму Коллатца.
После этого ответьте себе на вопрос: может ли хоть одна последовательность в Дереве не придти к корню. Аналогично, но наоборот, в Бескорневой подсети ни одна последовательность не сходится (корня-то нет, остановиться не на чем) и все они СВЯЗАНЫ тем же восходящим алгоритмом.
Судя по вашему комментарию вам не хватает логики понять простые аргументы.
Хорошо, упрощу совсем.
Вот рассмотрите процес 2n+4. Тут A будет сходиться к 2, но среднее С по сети будет все то же 4. 4>2 - так что по вашему аргументу все цепочки должны сходиться, а они все, очевидно, расходятся. Кстати, вам же очевидно, что все целые числа тут часть одной бескорневой сети?
Что именно в вашей статье не применимо к 2n+4?
В статье на странице 10 написано, что "Некоторые сочетания параметров a, b, c (алгоритмы вида "an+b/c") могут давать приводимые и вырожденные алгоритмы, порождающие неинтересные варианты сети. По этой причине параметры a и c должны быть взаимно простыми." Ваш надуманный пример "2n+4/2" НЕЛЬЗЯ автоматически считать алгоритмом типа Коллатца. Выводы статьи относятся к алгоритмам, выделенным цветом на картинке ниже.
порождающие неинтересные варианты сети
Вы этим "неинтересные варианты" просто замели свой фейл под ковер.
Еще раз, ваши аргументы, если их применить к 2n+4 "доказывают", что сеть корневая, что там все цепочки сходятся, потому что у всей сети средняя делимость 4, а 4>2, значит каждая цепочка достигает средней делимости 2 и поэтому сходится к 1.
Это очевидно ошибка. Почему? Что в ваших аргументах не работат? Вы нигде в ваших рассуждениях не опираетесь на то, что a,b и c взаимнопросты.
"неинтересные варинты" - это не ответ. Либо вы укажете, что именно в вычислении средней делимости применимо к 3n+1 но не применимо к 2n+4, либо ваши аргументы просто ошибочны.
И я утверждаю что на самом деле они ошибочны. Из того, что средняя делимость всей подсети равна 4 никак не следует, что делимость всех цепочек в ней не может быть меньше 3. Сеть образуемая 2n+4 это явно показывает.
Ответ очень простой (но судя по комментам вряд ли вам доступный): взаимно простые a и c дают регулярные Таблицы с ротацией указателей, подобные той, что на первой картинке выше. Вырожденные алгоритмы такого не гарантируют, их нужно рассматривать отдельно и конкретно.
Что не так с таблицей 2n+4? Там в каждой строке есть указатель во втором столбце. Куда уж регулярнее? Чем отсутствие указателей в других ячейках ломает вашу логику?
Еще раз. Вы утверждаете, что бескорневой подсети в 3n+1 нет, потому что если бы она была, то средняя делимость в этой подсети была бы болье 3.5 (потому что альфа/бета и бла-бла-бла). Но раз она бескорневая, то все цепочки в этой подсети должны иметь средний делитель меньше 3.5, потому что цепочки с большим делителем сходятся к 1 когда C сравнивается с A. И это у вас в голове - противоречие. Вроде не может вся сеть целиком быть > 3.5 когда как каждая цепочка < 3.5, как будто свойства цепочек переносятся на сеть, которая из них состоит. Я же правильно понял суть вашего аргумента?
Но это не противоречие. Возьмите сеть для 2n+4. Да, там в таблице желтые клетки по другому расставлены. Но это все еще сеть. У нее все еще средний делитель 4. Но все цепочки в ней имеют средний делитель 2. И тут нет никакого противоречия.
И ротацию вы используете там, где вы доказываете что среднее значение в подсети больше 3.5, потому что альфа/бета. Но это не нужно в случае 2N+4. Легко доказать, что все числа образуют там одну связную подсеть. А значит ее среднее значение 4 и не надо использовать ротацию.
Нет 2n+4/2 - ЭТО НЕ ОДНА СВЯЗНАЯ СЕТЬ, а набор расходящихся линейных цепочек (начинающихся с 1, 5, 9, 13...). Это вообще НЕ АЛГОРИТМ типа Коллатца. И правильно, что такие случаи выведены из рассмотрения.
Поправка: утверждение выше для алгоритма 4n+2/2.
Для 2n+4/2 - это ОДНА расходящаяся линейная цепочка, начинающаяся с 1. Остальное без изменений: Это НЕ АЛГОРИТМ типа Коллатца. Делимость вырожденной сети (цепочки) равна 2.
Эм... 2n+4/2 из нечетного числа 1 получает 3, потом из 3 получает 5, из 5 получает 7 и т.д. Все нечетные числа - одна цепочка. Все четные числа дают какое-то одно нечетное число. Это одна сеть.
Продолжаете не понимать как считается делимость сети.
Она считается по схеме указателей алгоритма. Поэтому делимость вырожденных "подсетей" (если считать таковыми линейные цепочки) будет 2, а не 4.
Но повторяю, это не предмет обсуждаемой статьи.
Хорошо, вот вам пример более похожий на вашу сеть, если вы что-то хоть немного от него отличающееся по форме не воспринимаете как объект той же категории. Алгоритм таков:
Четные числа делятся на 2. Числа вида n=4k+1 заменяются на 2n+2. Числа вида n=4k+3 заменяются на 2n+8.
Переход 2n+2 всегда будет иметь делитель 2^2 и даст 2k+1. Переход 2n+8 всегда даст делитель 2^1 и перейдет в 4(k+1)+3.
Не возражайте мне, что не константный параметр b, зависящий от остатка числа по модулю 4, тут на что-то влияет. Нет, это все еще сеть и значение A тут все равно будет сходится к 2 в длинных цепочках. Но даже это не важно, ибо тут мы обсуждаем лишь одно ваше утверждение: что среднее по все подсети не может быть больше X, когда как среднее в каждой цепочке в сети - меньше X.
Тут есть корень 1 (2*1+2 = 4 -> 2 -> 1). И вообще вся ваша статья к этому алгоритму применима и показывает, что тут все сходится к 1. Вся часть про альфа/гамма выбрасывается и делимость сети считается проще. но не будем на этом фокусироваться. Сфокусируемся лишь ваших рассуждениях про делимость.
Все числа кроме 1 образют одну расходящуюся подсеть. Числа вида 4k+3 опять образуют цепочку в бесконечность, числа 4k+1 переходят в какое-то меньшее число, дающее или остаток 1 или остаток 3 при делении на 4, пока не встретится остаток 3, а дальше будет бесконечная цепочка из увеличивающихся на 4 чисел. А остаток 3 встретится, потому что бесконечно уменьшаться число не может.
Постройте свою таблицу, раскрасьте указатели, если вам так понятнее, и увидите, что строки вида 4k+1 имеют ровно один указатель 2^2 (полученный из числа 4(2k)+1, а строки вида 4k+3 имеют 2 указателя: 2^1 полученный из числа 4(k-1)+1 и 2^2 от числа 4(2k+1)+1.
Делимость в этой сети будет sqrt(2*4) = 2.82, потому что делителей 2^1 тут ровно столько же, сколько 2^2, потому что каждое число 4k+3 дает в какой-то строке 2^1, а число 4k+1 - 2^2. А в подсеть входят вообще все числа (кроме 1, но оно единственное погоды не делает), и чисел дающих остатки 1 и 3 по модулю 4 там одинаково. Значит 2 и 4 идиально сбалансированны. Тут я парадирую по аналогии ваши же аргументы.
Однако делимость каждой цепочки тут ровно 2, ибо там сначала конечное количество делителей 4, а потом бесконечное количество делителей 2. А вся подсеть имеет делимость 2.82, напоминаю.
Таким образом нет никакого противоречия в том, что вся подсеть имеет делимость >4, а каждая цепочка имеет делимость <3.5. Вот выше пример подсети которая таким свойством обладает. Так что ваша статья не доказывает остутствие бескорневых подсетей.
Я не буду заниматься вашим примером, поскольку потратил на вас уже слишком много времени. Данный фантазийный алгоритм НЕ ПОДХОДИТ под рассмотренные в статье, хотя бы потому что умножение на 2 и деление на 2 - не взаимно простые. Занимайтесь им сами, пользуясь предложенными инструментами, разрешаю.
НАПОСЛЕДОК (потому что сколько можно!) об ошибках. Мелочь: 1 здесь - не корень, а изолят, она ни с одним другим ключом не связана. Следующая ошибка ФУНДАМЕНТАЛЬНАЯ. Это сравнение делимости цепочек и делимости всей сети БЕЗ УЧЕТА многократной повторности прохождения указателей в цепочках (в данном фантазийном случае при попадании на расходящуюся ветку 3-7-9-…).
О необходимости бесповторности ясно и прямо написано в статье! То есть получается, вы не поняли в доказательстве ГЛАВНЫХ ВЕЩЕЙ. Но пытаетесь придумать хоть какие-то возражения. Ваш уровень меня не устраивает. (Заодно извиняюсь перед читателями за качество анонимного оппонента.) Доказательство опубликовано, прозрачно объяснено. Оно устоит и перед более квалифицированной критикой.
Слив засчитан. Не буду впредь ваши статьи читать и пытаться вам указать на ошибки в них. Вы ведь в своем экзтазе от того, как утерли мировой математике нос никакие аргументы воспринимать не будете. Правда, математика этого не заметила, и вам все просто ставят минусы только видя нелогичность и дилетанство с первых страниц ваших текстов.
И да, напомню, что 3 и 2, 5 и 2, 7 и 2 (фигурирующие в статье) - взаимно просты.
Не собираюсь разбирать всю эту мешанину.
А вообще обидно. Я, вот, не поленился вашу мешанину разобрать. Потрудитесь и вы.
Автор, я мало что понимаю в сути вопроса, и тем более ни в коем случае не собираюсь вас воспитывать, просто скажу свое мнение. Допустим, вы правы и вам удалось найти доказательство. Согласитесь, выглядит это маловероятным, потому что, к примеру, теорему Ферма не могли доказать лучшие умы триста лет, а сейчас гипотезу Коллатца так же пока не доказали лучшие умы нашего времени (во всяком случае, общепризнанные), стоящие на плечах тех титанов. Но все же, предположим, вы правы. Во-первых, мало объяснить, как правильно. Надо еще уметь объяснить, почему неправильно - это неправильно. Иногда это даже сложнее, но по-моему это золотое правило дискуссии. Во-вторых, непонятно, почему вы реагируете так резко. Подавляющее количество постов и публикаций где бы то ни было не вызывают вообще никакой реакции. Ни положительной, ни отрицательной, просто равнодушие и полное отсутствие интереса. В вашем случае это не так - ваши статьи вызывают живой отклик и, казалось бы, грех этим не воспользоваться, чтоб еще раз донести свое мнение. Люди часто нарочно оставляют в своих статьях недосказанности, чтоб привлечь к ним внимание и развернуто описать спорные моменты. Мне кажется, это удача, что с вами спорят и задают вопросы о каких-то белых пятнах.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Гипотеза Коллатца как фейл мировой математики (продолжение)