Как стать автором
Обновить

Комментарии 113

Возможно, людей отпугивают фразы типа "хвост рекурсии", "шаг рекурсии". Я не спец. в терминологии по алгоритмам, но почему-то мне интуитивно не хочется употреблять эти фразы. "Ограниченная система координат" - тоже что-то странное. Вам надо бы найти рецензента (руководителя) и вычитать статью, если в ней действительно есть зерно истины. А то я переварю Вашу статью, перепишу её на нормальный лад и опубликуюсь первым :) (шутка, конечно)

С радостью берите и публикуйте :).
Хоть по частям, хоть целиком. Я взял эту задачу на принцип. Я не математик. Я программист.
"Ограниченная система координат" – это метафора.
Пусть здесь повесит. Если будет дискуссия, я вступлю, объясню, что и как.
Как говорится, чем смог, тем помог научному сообществу РФ. Если кто-то найдет ошибку, буду рад. Если нет, то буду двигаться дальше, с публикацией в каком-то более серьезном ресурсе.

  1. Вы обернули последовательность (очевидно многозначно) и заявили что в любой такой нет циклов. А нужно доказать что в подобных последовательностях есть все числа. Даже есть вы доказали что в перевернутых последовательностях не существует цикла (нет), то все ещё может быть бесконечная последовательность, с неограниченным ростом, в этом случае перевернутая последовательность не имеет начала, и не имеет циклов. Такие последовательности очевидно есть (например {2**i}, в нумерации с конца), нужно доказать что они все такие заканчиваются на 4, 2, 1.

  2. Какая-то странная терминология (рекурсия...). Может вам нужна Математическая индукция? Тогда аккуратно сформулируйте базу и шаг, и это можно будет читать.

  3. Отсутствует какая то прорывная идея, рассматривание нескольких конечных вычетов не может привести к решению задачи, иначе бы она уже была решена ранее.

Рекомендую к решению задачу https://projecteuler.net/problem=494 прежде чем делать подобные громкие заявления (и нет, там ответ не числа Фибоначчи).

Сейчас 3 часа ночи в Оренбурге. Отвечу только лишь по поводу рекурсии.
Да, это рекурсия. Причем не простая, а возвратная рекурсия. В английской литературе возвратная рекурсия именуется как "Course-of-values recursion".

Нужно доказать что в подобных последовательностях есть все числа.

Доказательство.

Любое натуральное число можно подставить в рекурсию \frac {n-1}{3}. Таким образом, рекурсия охватывает все числа. Нет такого числа, которое нельзя подставить в рекурсию.

Даже если вы доказали, что в перевернутых последовательностях не существует цикла, то все ещё может быть бесконечная последовательность, с неограниченным ростом, в этом случае перевернутая последовательность не имеет начала.

То, что вы написали, противоречит самому смыслу рекурсии. Рекурсия "без начала" не существует. Извините, но как вы себе представляете старт рекурсии с некоего числа n, у которого нет прародителя? Это невозможно.

3n+1 – это развернутая в обратном направлении рекурсия от рекурсии \frac {n-1}{3}. Как только мы это заявляем (минуточку! внимание! а мы это уже заявили), то мы сразу же соглашаемся с тем, что 3n+1 не может уходить в бесконечность. Потому что это противоречит самому определению «развернутой в обратном направлении рекурсии».

Отсутствует какая то прорывная идея.

Гипотеза Коллатца – это классическая возвратная рекурсия. Это уже сама по себе мега прорывная идея. Всё остальное тривиально. Потому что на этом, в принципе, можно всё заканчивать.

Рекурсия придумана Тьюрингом, как констатация того факта, что не все математические задачи могут быть решены через формулы. И это правда. Нельзя доказать гипотезу Коллатца в рамках классической математики, без привлечения сюда понятия рекурсии из теории алгоритмов.

Смотрите! Вот, что выясняется. Никто не видит, что гипотеза Коллатца – это классическая рекурсия. 3n+1 на данный момент классифицируется математиками как некий алгоритм. Но не рекурсия. Никто даже не пытается определить шаг рекурсии и использовать его для доказательства. Почему?

Тогда вопрос к вам, как классифицировать гипотезу Коллатца на принадлежность к возвратной рекурсии?

У меня есть три варианта ответа. Во-первых, это можно сделать на математически строгом языке, как сделал это я, в первой части публикации. Но, допустим, кто-то не согласен.

Во-вторых, это можно сделать на компьютере, запустив фрагмент кода из первой части публикации, как это сделал «Soul Friend» 5 лет назад. Он предложил распространить этот шаг рекурсии на все натуральные числа и поставить точку в гипотезе Коллатца, но дальше дело не пошло.

В-третьих, мысленно прогнать ветку рекурсии на соответствие доказанному нами ранее шагу рекурсии:

1 \rightarrow 5 \rightarrow 3 \rightarrow 13 \rightarrow 53 \rightarrow 35 \rightarrow 23 \rightarrow 15 \rightarrow 61 \rightarrow 81 \rightarrow 325 \rightarrow 433 \rightarrow 577 \rightarrow 769 \rightarrow 3077 \rightarrow 2051 \rightarrow 1367 \rightarrow 911 \rightarrow 607 \rightarrow 2429 \rightarrow 1619 \rightarrow 1079 \rightarrow 719 \rightarrow 479 \rightarrow 319 \rightarrow 425 \rightarrow 283 \rightarrow 377 \rightarrow 251 \rightarrow 167 \rightarrow 111 \rightarrow 445 \rightarrow 593 \rightarrow 395 \rightarrow 263 \rightarrow 175 \rightarrow 233 \rightarrow 155 \rightarrow 103 \rightarrow 137 \rightarrow 91 \rightarrow 121 \rightarrow 161 \rightarrow 107 \rightarrow 71 \rightarrow 47 \rightarrow 31 \rightarrow 41 \rightarrow 27.

И убедиться в том, что то, что вы видите, это результат работы рекурсии \frac {n-1}{3}. Это ни какая-то там "последовательность". Это обычная рекурсивная ветка. Она часть рекурсии. Её нельзя вынуть из рекурсии и сказать, вот, смотрите, есть какая-то там последовательность.

Любое применение 3n+1 к любому нечетному числу – это уже часть рекурсии.

Любое натуральное число можно подставить в рекурсию n*7. Означает ли это что из предка 1 можно получить число 9?

flx0, давайте сразу перейдем к конкретике. Что вы хотите сказать? Я не понял вашу мысль. Какая рекурсия n*7? Какой шаг рекурсии в вашем примере?

n_{i+1} = 7*n_{i}
Вместо n_i можно подставить любое натуральное число. Цитируя вас, "Таким образом, рекурсия охватывает все числа. Нет такого числа, которое нельзя подставить в рекурсию."
Если вам не нравится, что она возрастающая, можете развернуть. Означает ли это что любое натуральное число можно получить из 1?

flx0, во-первых, контекст этой цитаты был в рамках всего обсуждения, всей статьи целиком.

Шаг рекурсии \frac {n-1}{3} включает в себя все комбинации по модулю 3, n ≡ 0 mod(3), n ≡ 1 mod(3), n ≡ 2 mod(3).

Во-вторых. Ваша рекурсия:

n_{i+1} = 7*n_{i}

охватывает только числа n ≡ 0 mod(7), потому что вы прописали в ней шаг рекурсии n ≡ 0 mod(7):

1 \rightarrow 7 \rightarrow 49 \rightarrow 343 \rightarrow 2401 \rightarrow ...

Вы не можете при таком шаге рекурсии получить какое-либо другое число, отличное от n ≡ 0 mod(7).

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

Любое натуральное число можно подставить в рекурсию \frac {n-1}{3}. Таким образом, рекурсия охватывает все числа. Нет такого числа, которое нельзя подставить в рекурсию.

Вот это утверждение не доказывает, что именно из единицы, последовательно применяя шаги рекурсии, можно прийти в любое число.

Мы отталкиваемся от задачи 3n+1, верно? Тогда открываем Википедию:

Statement of the problem
«If the conjecture is false, it can only be because there is some starting number which gives rise to a sequence that does not contain 1. Such a sequence would either enter a repeating cycle that excludes 1, or increase without bound.»

«Гипотеза Коллатца может оказаться неверна только лишь в том случае, если существует такое число n, которое зацикливается или уходит в бесконечность. В противном случае, число n всегда достигает единицы.»

Вы согласны с этим?

Да.

На протяжении 100 лет математики «вязли в болоте» Коллатца только лишь потому, что не могли описать задачу 3n+1 через элементарную теорию алгоритмов

Все эти годы такое простое и очевидное решение лежало на поверхности, и из миллиардов людей не нашлось ни одного математика-любителя, который бы его обнаружил. Вы первый. Вы сами в это верите?

ВСЕ простые способы решить задачу исчерпаны много лет назад. Остался один способ доказать проблему — найти более общую теорему и доказать уже её. И скорее всего, как с теоремой Ферма, доказательство теоремы будет очень сложным.

Попробуйте на компьютере запустить рекурсию \frac {n-1}{3}, и вы будете поражены тем фактом, что эта рекурсия строит все те самые графы и последовательности Коллатца, о которых так много пишут в книгах.
Это будет лучшим доказательством моих слов.

Я на своем компьютере прогнал триллионы последовательностей Коллатца, и все они оказались частью рекурсии \frac {n-1}{3}.

Если вам нужен исходный код программы для проверки является ли та, или иная последовательность Коллатца частью рекурсии \frac {n-1}{3}, я вышлю вам на почту исходный код программы на языке 1С. Вы сможете сами всё легко проверить.

Уверен, после первого миллиона последовательностей Коллатца, ваш пыл поубавиться. А после первого миллиарда вам станет скучно, и вы поймете насколько всё банально и просто в гипотезе Коллатца.

Триллионы оказались. А одна из квинтиллионных или центиллионных не окажется. А может быть, окажутся все — пока ни один математик не смог доказать того или другого.

Оо! Я вам скажу больше! На сегодняшний день ни один математик не набрался смелости признать гипотезу Коллатца классической возвратной рекурсией, которой она является.

Откройте англоязычную Википедию. Вы видите там хоть одно упоминание о рекурсии? О шаге рекурсии? О хвосте рекурсии? О причине, по которой в рекурсии нет повторов? О фальшивости чётных чисел в гипотезе Коллатца? То-то же и оно.

Кого вы защищаете? Математиков? Великий миф о гипотезе Коллатца?

Я вообще термин "шаг рекурсии" никогда не встречал раньше. Что он вообще значит? В абстрактной рекурсии нет никакого шага. Какое-то понятие "шаг" может появиться только в конкретном алгоритме и это совершенно необязательно.

Шаг рекурсии - это правило, по которому рекурсия шагает, продолжает выполняться, условие её выполнения.

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

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

Но, пожалуйста, не говорите об этом математикам. Это нокдаун. Они сейчас молятся, чтобы найти ошибку в этой работе.

Шаг рекурсии — это правило, по которому рекурсия шагает, продолжает выполняться, условие её выполнения.

Применение термина "шаг" к "условию", это слишком произвольный ввод терминологии. Не говорю что нельзя так делать. Но надо аргументировать и дать более подробную дефиницию. А то "шаг, шаг", а что это именно значит?


И вообще-то понятие шаг применимо к итеративным алгоритмам, а не к рекурсивным, а точнее к итератором, если таковой имеется. Например в конструкциях цикла типа "for i = 0 to 100 step 3". К итеративным алгоритмам без итератора (например "while do") термин "шаг" тоже неприменим в общем случае.

Когда я делал перевод этой статьи на английский язык, то я использовал устоявшийся термин:

The iteration of the recursion.

Может быть, это как-то поможет нам с вам в терминологии.

А можете привести код и то место, где Вы его используете?

Вот сюда я выложил код программы. Код рабочий. Отпишитесь, пожалуйста, в личку, если есть какие-то вопросы.

Спасибо, проверил. Код рабочий. По терминологии затрудняюсь ответить... Тут требуется комплексная проработка вопроса. Остаётся Вам пожелать удачи!

А хабр просто не стоит того, чтобы там публиковаться - так, для затравки только.

Спасибо! Вы третий человек, который проверил этот код. Сначала был «Soul Friend», потом я, теперь вы. Так, глядишь, четвертого найдем :)

Код-то тривиальный, что там проверять. Только он ничего не доказывает.

Опыт программирования на 1С пригодился:)

А я вот доказал, что все нечетные числа простые - на компьютере проверил несколько штук, например 3 - простое, 5 - простое, 7 - простое. Неужели этого не достаточно?

С точки зрения математики, что 3 числа проверить, что 3 триллиона, что 3 триллиона в триллионной степени - это совершенно одинаково означает, что оставшееся бесконечное количество чисел вы не проверили. А доказать нужно, что гипотеза верна не для триллиона чисел, а для всех.

Вот пример простой задачи, у которой очень большое решение:

Найти решение в целых положительных числах:

Количество проверенных чисел в гипотезе Коллатца даже близко не подошло к таким значениям.

Я хотел бы пояснить, почему я погружаться в вашу статью не буду.

Во-первых, в ней нет доказательства гипотезы Коллатца. Доказательство должно начинаться с "Возьмем произвольное натуральное число n ...", а заканчиваться тем, что "... получаем 1". Зачем читать что-то, что не является доказательством?

Во-вторых, вы должны понимать, что вы рассказываете ситуацию близкую к такой - "я совершил географическое открытие - зашел в браузере на сайт maps.google.com, поскроллил спутниковую карту и нашел в океане неподписанный остров - прошу внести его в базу географических объектов и назвать в честь меня как первооткрывателя". Ну то есть, всему географическому сообществу ясно, что времена таких открытий уже прошли и все острова известны, идея найти новый остров на карте - глупость, потому что всю карту тысячи людей уже просмотрели и вручную и проанализировали компьютерными алгоритмами, а если какой-то остров не подписан, то это может быть по разным причинам, но только не по той, что он никому не известен. В такой обстановке вы не можете просто вбросить какой-то текст и понадеяться, что кто-то будет тратить на него время. Вам как минимум придётся избавить читателя от всех возможных препятствий при его прочтении - т.е. использовать только общепринятые термины, все новые понятия, которые вам понадобились, ясно и понятно определить через известные понятия из учебников, и структурировать текст именно как доказательство гипотезы в её известной формулировке, а не как какой-то набор свойств каких-то "рекурсий".

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

Да, необходимо согласование с математиками

Идея тривиальная — посмотреть, какие числа получаются из 1, если процесс развернуть. Дальше криво расписано, как рассматривать только нечетные числа в этом дереве. И на этом все. То, что это дерево покрывает все натуральные числа — нигде не доказано.

То, что это дерево покрывает все натуральные числа — нигде не доказано.

Доказательство.

Предположим, такое число n есть, которое не покрывается рекурсией.
Но, как мы уже доказали, циклов, повторов и зацикливания в рекурсии нет.
Из этого следует, что подставив такое число n в рекурсию \frac {n-1}{3} мы получим противоречие. Потому что, прародитель (итерация назад) и рекурсия (итерация вперед) оба должны уйти в бесконечность. Это невозможно.

Если прародитель не идет к единице, и не зацикливается, то у него остается только один вариант – уйти в бесконечность. Но это невозможно. Это противоречит самой сути алгоритма. Нельзя получить две бесконечности из одного и того же алгоритма с тем шагом рекурсии, который мы установили (см. комментарий ниже).

Но, как мы уже доказали, циклов, повторов и зацикливания в рекурсии нет

Вот тут ошибка. Вы доказали, что нет цикла, в которой что-то входит снизу. Но из него может что-то выходить вверх.


Потому что, прародитель (итерация назад) и рекурсия (итерация вперед) оба должны уйти в бесконечность. Это невозможно.

Тут тоже косяк. Почему не может рекурсия из бесконечности уменьшаться, пока не достигнет x, а потом увеличиваться по другим числам в бесконечность? Шаги-то есть увеличивающие в любом направлении.


Вот вам триваильный пример: Делящеся на 2 число, делится на 2. Иначе умножается на 3. Тут есть бесконечная в обе стороны последовательность ...->16->8->4->2->1->3->9->27->...


Какое особое свойство у вашего "шага рекурсии" такое поведение запрещает вы не указали.

Вот тут ошибка. Вы доказали, что нет цикла, в которой что-то входит снизу. Но из него может что-то выходить вверх.

Откуда такие выводы? Давайте по порядку.
Статья посвящена полной версии алгоритма \frac {n-1}{3}, где шаг рекурсии:

\frac{2n-1}{3} для случая n ≡ 2 mod(3),

\frac{4n-1}{3} для случая n ≡ 1 mod(3),

n=n для случая n ≡ 0 mod(3),
и постоянное применение к уже полученным числам 4x+1.

Таким образом, числа n ≡ 1 mod(3), n ≡ 2 mod(3) всегда порождают двух потомков. Числа вида n ≡ 0 mod(3) всегда порождают только одного потомка.

Родитель один. Потомков много.

Но если рекурсия породила два одинаковых числа, неважно на каком шаге, и неважно кому и кем они приходятся, то это зацикливание.

С точки зрения рекурсии не существует никаких верхов, низов, последовательностей, и прочей такой вот терминологии. Рекурсия – это шаг рекурсии. Всё, что мы можем, это взять число, которое уже когда-то было получено рекурсией, подставить его в рекурсию, получить новое число, снова его подставить в рекурсию и т.д.

Мы доказали, что этот процесс не подразумевает повторов. Где повторы? Объясните, пожалуйста, ваш ход мысли.

Тут тоже косяк. Почему не может рекурсия из бесконечности уменьшаться, пока не достигнет x, а потом увеличиваться по другим числам в бесконечность? Шаги-то есть увеличивающие в любом направлении.

Извините, но где вы увидели шаги "увеличивающиеся в любом направлении"? Для рекурсии \frac {n-1}{3} есть только один увеличивающий шаг, это 4x+1. Никакое другое действие не увеличивает рекурсию. Я говорю именно про действие. Не про какие-то конкретные числа, которые, допустим, вы подставляете в рекурсию, и вам кажется, что вот, смотрите, число увеличилось. Нет. Я говорю именно про движение в сторону бесконечности. Оно единственное. Это 4x+1. Нет других движений.

Какое особое свойство у вашего "шага рекурсии" такое поведение запрещает вы не указали.

Указал. Это как раз центральный момент исследования.

Я процитирую:

Как сейчас уже очевидно, возрастание с единицы до бесконечности по алгоритму \frac {n-1}{3}, основано только лишь на одном правиле 4x+1. Применение же формул \frac{2n-1}{3}, \frac{4n-1}{3} – это просто ветка "вправо-влево", которая ни на что не влияет, потому что каждая такая ветка всегда заканчивается хвостом рекурсии n ≡ 0 mod(3).

Акцентирую. Любое действие в рекурсии \frac {n-1}{3} всегда заканчивается хвостом рекурсии n ≡ 0 mod(3). И с этим ничего нельзя сделать. На то он и хвост. Уравнение: 2^kz - \frac {1}{3} не имеет целочисленного решения.

Таким образом, у рекурсии \frac {n-1}{3} нет другого выбора, как расти в бесконечность по правилу 4x+1, потому что вся рекурсия фактически сводится (упрощается) только лишь к применению этого правила.

Еще раз, все ваши рассуждения применимы к изначальной "рекурсии"


n = 2n (всегда)
n = (n-1)/3 (если n = 6k+4)


Это изначальный процесс Коллатца.


Но там ЕСТЬ цикл! 1->2->4->1->...


Родитель один. Потомков много.

Выполняется для рекурсии выше.


Но если рекурсия породила два одинаковых числа, неважно на каком шаге, и неважно кому и кем они приходятся, то это зацикливание.

Но цикл-то есть! Я его весь привело вышще. Тут нет противоречия, потому что у 1 только один потомок! Но он в том же цикле.


звините, но где вы увидели шаги "увеличивающиеся в любом направлении"?

(n-1)/3 — увеличивает в обратном направлении. 4x+1 — увеличивает в прямом. Поэтому теоретически отматывая рекурсию назад можно тоже уйти в бесконечность, если начать с какого-то очень большого числа (недостижимого с 1, естественно. Вдруг такое есть? Вы не доказали обратного)

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

Простите. Но нет. Еще раз нет. И снова нет.
Рекурсия \frac {n-1}{3} умеет разветвлять числа, а рекурсия 3n+1 - нет, потому что это неполноценный алгоритм (обрубок).
В рекурсии \frac {n-1}{3} мы прописали шаг на разветвление, а в рекурсии 3n+1 мы его убрали.
Это разные задачи. Именно поэтому, мыслив категориями 3n+1, вы ограничены в своих суждениях.

Но там ЕСТЬ цикл! 1->2->4->1->

Тогда,
я процитирую первую часть публикации:

...Единица не может иметь другого прародителя, кроме самого себя, потому что \frac {n-1}{3} и 3n+1 дают для единицы – единицу.
...Чётные числа являются ширмой в гипотезе Коллатца.
...Мы выкинули все чётные числа из рекурсии.
...Рекурсию нельзя остановить. Она бесконечна в любую сторону: 1 \rightarrow 1 \rightarrow 1 \rightarrow 1 \rightarrow 1 \rightarrow – это также движение.

Поэтому, 1 \rightarrow 1 \rightarrow 1 \rightarrow– не может быть циклом в рамках того, что мы с вами здесь обсуждаем: a->b->c->a->...

n = n, это вообще не цикл. Это старт рекурсии. Прародитель сам себя создал и продолжает создавать бесконечно много раз.

Не надо мучить единицу. Пожалуйста, оставьте её в покое.
Давайте условимся, что первую "прародительскую" итерацию мы не будем называть циклом. И вообще не будем её рассматривать. Иначе, как это уже было, прибежит секта свидетелей нуль-функции и всем нам кирдык (шутка). :)

\frac {n-1}{3} — увеличивает в обратном направлении. 4x+1 — увеличивает в прямом.

wataru, вот здесь мы с вами уже друг друга не понимаем. Не только мы, но и читатели, наверное, тоже.

Далее, вы пишите:

Теоретически отматывая рекурсию назад можно тоже уйти в бесконечность, если начать с какого-то очень большого числа (недостижимого с 1).

Но как? Как вы собираетесь отмотать рекурсию? Как вы собираетесь получить бесконечность там, где её нельзя получить?

Шаг рекурсии \frac {n-1}{3} настолько простейший, что всё доказательство гипотезы Коллатца сводится только лишь к нему. Не нужно больше ничего делать. Надо только его осмыслить.

Алгоритм 3n+1 - может двигаться только по тем числам, которые уже были проложены до него рекурсией \frac {n-1}{3}, других вариантов нет.

Давайте определимся с определениями. Прямой процесс — это то, что в задаче коллатца (n/2 для четных или 3n+1 для нечетных). Он однозначный. Кажому числу ставится в соответствие одно следующее.


Обратный процесс, это то, что вы ввели: обратные операции (2n всегда, (n-1)/3 для n=6k+4). Он уже не однозначный, но каждый результат получается ровно одним способом — по построению. Вы просто развернули стрелочки в дереве коллатца. Если изначально из каждого числа выходила ровно одна стрелочка, то теперь в каждое число входит ровно одна стрелочка.


Это разные задачи. Именно поэтому, мыслив категориями 3n+1, вы ограничены в своих суждениях.

Это одна и та же задача. Одна и та же картинка, только двигаемся мы или по стрелочкам или против них.


я процитирую первую часть публикации:
… Единица не может иметь другого прародителя, кроме самого себя, потому что \frac {n-1}{3} и 3n+1 дают для единицы – единицу.

Это, кстати, бред. К единице (N-1)/3 не применяется, потому что вы его только к четным числам применять разрешили (иначе процесс не будет обратным к прямому процессу). Но если бы применялось, то там получился бы 0, а не 1.


Вообще, когда вы избавились от четных чисел у вас там следующие "шаги" получились: 4x+1 всегда; (2n-1)/3, если n%3 ==2; (4n-1)/3, если n%3==1. Так вот для 1 есть два хода: 4*1+1=5 и (4*1-1)/3=1.


Почему вы исключаете шаг 1->1, мне непонятно. Потому что этот элементарный пример цикла является ярким контрпримером к вашему утверждению?


Алгоритм 3n+1 — может двигаться только по тем числам, которые уже были проложены до него рекурсией \frac {n-1}{3}, других вариантов нет.

Да, если двигаться по стрелочкам вперед, то вы пойдете ровно по тем же числам, по которым бы вы прошли двигаясь по этим же стрелочкам назад. Если вести пальцем по линии слева-направо или по той же линии справа-налево, вы проведете по тем же точкам, только в обратном порядке. Но это ничего не доказывает.

Почему вы исключаете шаг 1->1, мне непонятно. Потому что этот элементарный пример цикла является ярким контрпримером к вашему утверждению?

Нет смысла обсуждать то, что дано нам по условию задачи. Мы можем прописать в рекурсии условие, чтобы она создавала бесконечные циклические ветви n=n для всех n, не только для единицы. Это на вас окажет эффект? Нет, конечно. Ничего в задаче не изменится.

Но ответьте, пожалуйста, на следующие вопросы:

...Откуда такие выводы? Давайте по порядку.
...Где вы увидели шаги "увеличивающиеся в любом направлении"?
...Где повторы? Объясните, пожалуйста, ваш ход мысли.
...Как вы собираетесь отмотать рекурсию? Как вы собираетесь получить бесконечность там, где её нельзя получить?

Нет смысла обсуждать то, что дано нам по условию задачи.

нет, условие задачи (изначальное) n->n/2 или n->3n+1.


Если вы решаете эту задачу, то все ваши построения должны на ней основываться. Как вы из нее вывели, что 1->1 запрещено?

Вот статья в Википедии «Collatz conjecture»:

Цикл — это последовательность (a_{0}, a_{1}, ..., a_{q}) различных положительных целых чисел, где f(a_{0}) = a_{1}, f(a_{1}) = a_{2}, ..., и f(a_{q}) = a_{0}.

Единственным известным циклом является (1,2), называемый тривиальным циклом.

k-циклы.
k-цикл — это цикл, который можно разбить на k непрерывных подпоследовательностей, каждая из которых состоит из возрастания и убывания.

Например, если цикл состоит из одной возрастающей и одной убывающей последовательности, он называется 1-циклом.

Штайнер в 1977 г. доказал, что не существует 1-цикла, кроме как тривиального (1; 2). Саймонс в 2005 г. доказал, что 2-циклов тоже не существует. Вегер расширил это доказательство до 68 циклов. Герчер расширил метод до k≤91.

Но поиски на компьютере продолжаются и на данный момент вопрос с циклами длиной более 91 не закрыт.

Как вы из нее вывели, что 1->1 запрещено?

Цикл — это последовательность (a_{0}, a_{1}, ..., a_{q}) различных положительных целых чисел, где f(a_{0}) = a_{1}, f(a_{1}) = a_{2}, ..., и f(a_{q}) = a_{0}.

1->1->1 – это не цикл. Это бесконечная ветвь рекурсии. О чем я вам и толкую.

Ну, и как мы видим, уже доказано в 1977 г., что такая ветвь в рекурсии может быть только одна – прародительская.

Кстати, раз уж вы в википедию полезли — там есть целый раздел in reverse. Не вы первый додумались смотреть на задачу задом-на-перед.


Единственным известным циклом является (1,2), называемый тривиальным циклом.

Но поиски на компьютере продолжаются и на данный момент вопрос с циклами длиной более 91 не закрыт.

Ключевые слова "вопрос не закрыт". Никто не доказал пока, что не может быть каких-то очень длинных циклов на очень больших числах. Кроме вас, естественно. Но ваше доказательство — ошибочно.


Цикл — это последовательность (a{0}, a{1}, ..., a_{q}) различных положительных

{1} — вполне себе последовательность из одного различного числа. Повторений никаких нет. Вполне себе цикл. Все-равно не понял, почему вы цикл {1} запрещаете.


Ладно, давайте с другой стороны зайдем. Давайте рассмотрим последовательность n/2, 5n+1. Смутно помню, что вы упоминали эту последовательность в первой статье раньше, но сейчас ее там нет. Там есть цикл без 1: (13->66->33->166->83->416->208->104->52->26->13), т.е. аналог гипотезы Коллатца для нее не выполняется.


Но все ваши рассуждения отлично применимы и к этой последовательности! Значит, из них не следует, что не может быть циклов, т.е. гипотеза Коллатца не доказана вами.


По шагам:
Прямой процесс: n->n/2, если n четно; n -> 5n+1 иначе.


Развернули. "Шаг рекурсии":
n -> 2n всегда;
n-> (n-1)/5, если n четно и дает остаток 1 (mod 5).


Выкинули "ничего не значащую ширму" — четные числа:
n = 0 (mod 5): "Хвост рекурсии".
n = 1 (mod 5): (16n-1)/5
n = 2 (mod 5): (8n-1)/5
n = 3 (mod 5): (2n-1)/5
n = 4 (mod 5): (4n-1)/5


И "особая связь" 16x+3.


Точно также "не может быть циклов", потому что, например:
(2a-1)/5 = (4b-1)/5 => b = 2a: противоречие, ведь b — нечетно.
(8a-1)/5 = 16b+3 => a = 10b + 2: противоречие, ведь a — нечетно.
и т.д. (остальные 8 случаев абсолютно аналогичны этим двум).


Итак, или вы должны признать, что ваши рассуждения ничего не доказывают, или вы должны указать, чем 5n+1 принципиально отличается от 3n+1.

Я скоро опубликую третью часть работы. Осталось немного.

Вы там разбираете случай 5n+1?

Все-равно не понял, почему вы цикл {1} запрещаете.

wataru, пусть нас рассудят авторитеты в области 3n+1, публикуемые на международном портале Arxiv.org.

Смотрите, вот в этой работе профессор математики утверждает, что тривиальный цикл в гипотезе Коллатца (1,2,4) дан нам по условию самой задачи, и его рассматривать не нужно.

Я вам пишу тоже самое, но вы игнорируете. Тогда будет справедливо (с вашей стороны по отношению ко мне), если мы оба найдем какие-то общие точки соприкосновения.

Например, будем рассматривать самые престижные работы математиков на портале Arxiv.org. Вы согласны со мной? И согласны ли вы с профессором?

авторитеты в области 3n+1, публикуемые на международном портале Arxiv.org.

arxiv — нерецензируемый портал для препринтов. Умные люди туда дублируют свои работы для большей публичности, но наличие работы там не гарантирует ничего. Вы можете свои некорректные рассуждения туда же залить без проблем.


вот в этой работе профессор математики утверждает,

Приведите цитату, где автор это утверждает. Я вижу там на странице 3 вверху:


For instance the evolution pattern of the odd number 1 is given by the following trivial periodic sequence 1,1,1,...

Т.е. автор не только не относит этот цикл к "данному по условию", а приводит его в качестве возможной "эволюции", которые он в работе рассматривает. Так что вот "профессор математики" нас уже рассудил.


Например, будем рассматривать самые престижные работы математиков на портале Arxiv.org.

Нет. Престижные работы вы найдете в поиске в scholar.google.com а не на arxiv.org


Вы согласны со мной? И согласны ли вы с профессором?

С вами — нет. С профессором — да.


Потом, можно ради изучения какой-то интересной подструктуры и отказаться рассматривать цикл 1->2->4. Вы, например, отказались рассматривать четные числа в вашей статье. Это значит, что их нет в гипотезе коллатца?
Поэтому уверен, если вы долго будете рыться в арХиве, то вы найдете парочку статей, где этот цикл отдельно исключается. Но это ничего не доказывает.


Жду следующей статьи и там буду смотреть только ваши аргументы, почему 5n+1 чем-то отличается от 3n+1 в ваших рассуждениях.

Приведите цитату, где автор это утверждает.

1.Introduction

Conjecture 1.1 (Collatz). For any positive integer m ∈ N the sequence of numbers... reaches the number 1 and then repeats periodically as 1, 4, 2, 1.

Первая страница работы. В самом начале.

И при чем тут автор тогда? Это общепринятая формулировка гипотезы. Ну, потому что вот этот цикл есть и в него все упирается. В этом и вопрос — есть ли другие циклы? Вы так могли бы и на википедию дать ссылку. Однако ваши рассуждения (как вам кажется) опровергают вообще все циклы (на самом деле нет, и поэтому они бесполезны).


Где там сказано (ваши слова):


дан нам по условию самой задачи, и его рассматривать не нужно.

И я вам уже привел цитату, где автор этот цикл рассматривает!

Я вообще ни на что не претендую. Но есть понятие справедливости.

Должно было быть так. 5 лет назад «Soul Friend» открывает для себя абсолютно случайно, что гипотеза Коллатца – это рекурсия. Он делится со всеми шагом рекурсии. Математики восхищаются изящностью его открытия и в тот же день доказывают гипотезу Коллатца.

Произошло так. Математики посылают его на три буквы, и он уходит.

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

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

sci_nov, спасибо вам за добрые слова. Доброе слово и кошке приятно!

Мой эмоциональный настрой (и в некоторых случаях агрессивность) - это следствие общения с математиками. Извините, если что не так. :)

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

Получится, что приходит какой-то человек и рассказывает, что он открыл, что гипотеза Коллатца - это трамвай! И делится со всеми шуршанием трамвая. И удивляется, что математики не восхищаются. Хотя казалось бы, очевидно, что зная шуршание трамвая, можно за 5 минут доказать гипотезу.

Или давайте я вам расскажу, что в ваших рассуждениях - гладиолус, поэтому они все неверны. Готовы ли вы будете после этого признать свою ошибку? (Конечно же, пояснять, что такое гладиолус я не буду - это и так ведь должно быть понятно). Если вы такой аргумент воспринять не готовы, то почему вы ожидаете, что математики готовы воспринимать вас?

Согласен.
«Soul Friend» сам балбес. Надо было доводить дело до конца, еще 5 лет назад. Кто знает, сколько бы бессонных ночей он бы спас :)

Нокдаун? Вы тут всех убрали в своих мыслях и рассуждениях? Вы высокомерны, а ещё используете терминологию которую никто не знает и не слышал. И люди не хотят вникать в чей-то птичий язык, потому что времени нет. Дам подсказку - когда число нечётное то надо умножить сразу на 3/2*n+1/2. Надо решать проблему с точки зрения теории графов, возможно. И вообще я не понял ваш переход от 3*n+1 к чему то там другому, еще в первой части.

Общение в интернете мне дается с трудом. Это правда. Что-то надо с этим делать. При личном общении, на той же кафедре математики с докторами математических наук я веду себя по-другому. Спасибо вам за критику. Я ценю это. Поверьте.

я веду себя по-другому

По какому?

Доброжелательно.

они могут не спорить так сказать с болваном и поддакивать или говорят уважительно о вас?

Вы перешли на личности? :(

да я помню был у нас один студент - ходил кругами что-то вычислял в уме(видно было) улыбался и ни с кем не говорил и выглядел как шизик

Насколько мне известно, гипотеза 3n+1 алгоритмически неразрешима. Если найду ссылку, приложу. Однако данный факт можно найти чуть ли не в Википедии. Кажется, что гипотеза Коллатца, в целом, должна решаться иными методами. Возможно, стоит придумать какой-нибудь аппарат унарной алгебры (т.е. рассматривать множества с унарной операцией)...

гипотеза 3n+1 алгоритмически неразрешима.

Да, вы правы, Википедия ссылается на работы S. Kurtz и J. Simon, которые пришли к выводу, что в такой постановке вопроса задача 3n+1 не доказуема.

Но 3n+1 - это алгоритм обрубок. Его в принципе не нужно было исследовать. Нужно было сразу переходить к полной версии алгоритма.

Нет такого нечетного числа, которое бы рекурсивно не цепляло другое.

И что? Надо доказать, что все числа получаются из 1, применением ваших правил. Вы никак это не доказали


И ваше доказательство отсутствия циклов работает только если этот цикл — атрактор — т.е. какие-то другие числа не на цикле в него втыкаются. Но ведь может быть изолированный цикл, в который ничто извне не ведет (и он недоступен из 1), вроде a->b->c->d->a, но никакое другое число, кроме d не ведет в a. Так что можете сконцентрироваться в вашем доказательстве того, что все числа достижимы из 1.

Но ведь может быть изолированный цикл, в который ничто извне не ведет.

Не может быть изолированного цикла. Потому что мы имеем дело с рекурсией. В ваших рассуждениях вы апеллируете термином "отдельная последовательность". Но как вы себе представляете рекурсию? Её вообще-то нельзя остановить. Она бесконечна.

Она бесконечна в любую сторону. 1 \rightarrow 1 \rightarrow 1 \rightarrow 1 \rightarrow 1 \rightarrow ... – это также движение по рекурсии.

Акцентирую. Для рекурсии нет такого понятия как отдельно взятая "последовательность" a->b->c->a.

Для рекурсии любое число имеет прародителя и потомков. Рекурсия с чего-то там начинается и куда-то продолжается. Перед а нужно ставить x:

…->x->a->b->c->a->…

Но как мы уже доказали, рекурсия не может так зациклиться. Тогда остается только один вариант: рекурсия уходит в бесконечность и слева, и справа. Но это невозможно, это противоречит нашему алгоритму:

Для \frac {n-1}{3} движение к бесконечности – это просто формула 4x+1.

Для 3n+1 приземление – это просто формула \frac {n}{4}.

При таком шаге рекурсии, при таком движении, алгоритм \frac {n-1}{3} не может уйти в бесконечность и слева, и справа.

Алгоритм 3n+1 – это вообще обрубок, которому суждено только приземляться. Он просто следует по дереву, которое для него уже построили.

В общем-то, центральная мысль, которую я отстаиваю больше года:

  • Любое применение 3n+1 к любому нечетному числу – это уже рекурсия. Если вы согласились так сделать, то вы вошли в рекурсию и уже не сможете из неё выйти.

Вот и весь фокус Коллатца.

Ну вот применение 3n+1 к 1 даст 4, которое даст 2, которое даст 1. Рекурсия циклится!

Вся суть в том, как вы воспринимаете задачу 3n+1, и под каким углом на нее смотрите?

  • Как алгоритм, в котором вашей же инструкцией сказано, что на единице нужно остановиться?

  • Как рекурсию, которая порождает единицу через саму себя?

  • Как сиракузскую последовательность, в которой тривиальный цикл (1,2) дан вам по условию задачи?

Уточните, пожалуйста.

Обратите внимание на эту статью:
Гипотеза Коллатца "гласит, что эта последовательность всегда заканчивается циклом (1,2,1…)"

Как алгоритм, в котором вашей же инструкцией сказано, что на единице нужно остановиться?

Если не останавливаться на 1, то все ваши рассуждения все так же применимы. Так что давайте не будем рассматривать этот случай.


Как рекурсию, которая порождает единицу через саму себя?

Тривиальный цикл — все-равно цикл.


Как сиракузскую последовательность, в которой тривиальный цикл (1,2) дан вам по условию задачи?
Гипотеза Коллатца "гласит, что эта последовательность всегда заканчивается циклом (1,2,1…)"

Я не понимаю, под каким углом вы это читаете, но это ровно то, что я говорю. Вот есть цикл. Его даже упоминают в гипотезе коллатца, потому что он есть и в него все известные пока последовательности упираются.


Ладно, забейте про цикл 1-2-4. Скажите, в чем разница между 5n+1 и 3n+1. Уж там-то уже куча циклов. Тут вы никакими извращениями не отвертитесь.

wataru, я вас так и не поблагодарил. В общем, все ваши вопросы, легли в основу третьей статьи. Это очень важно для меня, общение с вами. Вы даже не представляете, как тяжело с кем-то на форумах обсуждать гипотезу Коллатца. Спасибо вам, что задаете вопросы.

В третьей статье я перевожу гипотезу Коллатца на язык теории алгоритмов. Это не математическая задача. Это алгоритм. Всё, что было нужно для доказательства, по моему скромному мнению, я, и другие люди, например, «Soul Friend», уже опубликовали. Теперь только теория алгоритмов.

10-го, или 11-го мая я опубликую.

В чем разница между 5n+1 и 3n+1.

Они настолько сильно отличаются, что даже нет смысла их сравнивать. Это будет опубликовано в следующей работе.

10-го, или 11-го мая я опубликую.

И поформальнее, пожалуйста, распишите. Приведите ваши определения, они у вас немного нестандартные. И оформите, пожалуйста в виде "теорема, лемма и т.д".


Они настолько сильно отличаются, что даже нет смысла их сравнивать. Это будет опубликовано в следующей работе.

Все ваши рассуждения элементаро переносятся на 5n+1, я их в одном из комментариев приводил уже. Желательно указать конктренто, вроде "вот это вот увтерждение не выполняется для 5, а для 3 — да".

Спасибо! Еще раз вам спасибо! Обязательно сделаю упор на терминологию. И приведу примеры из теории алгоритмов, к какому классу задач относится 3n+1.

Для рекурсии любое число имеет прародителя и потомков. Рекурсия с чего-то там начинается и куда-то продолжается. Перед а нужно ставить x:

Ну вот сама развернутая гипотеза коллатца ((n-1)/3, n*2), без исключения четных чисел — точно такая же рекурсия. Но там есть цикл 1->2->4->1. И перед 1 нет никакого другого x. Там только 4 в том же цикле. Ваши слова противоречат этому.


Но как мы уже доказали, рекурсия не может так зациклиться.

Вы доказали, что нет последовательности, которая циклиться в конце, но начианется не на цикле. Иными словами, доказали что нет цикла "вперед". Отсутствие цикла "назад" вы никак не доказали. 1-2-4-1 — как раз пример такого цикла.

И перед 1 нет никакого другого x.

Как это возможно? Ну ей богу.
Что значит в вашем понимании такие слова как "вперед", "назад"?

Рекурсия движется только в одном направлении, вперед.

Что значит в вашем понимании такие слова как "вперед", "назад"?

Вот ваши слова из одного из комментария выше.


3n+1 – это развернутая в обратном направлении рекурсия от рекурсии

Вот вперед — это ваш шаг рекурсии. А назад — это "в обратном направлении"

Но когда мы говорим о движении рекурсии, мы не можем так рассуждать, что рекурсия одновременно идет и вперед, и назад.

У рекурсии есть направление. Мы можем отследить, что происходит вперед, и мы можем отследить, что происходит назад.


Вот как начали с 4. Предыдущее число 2 (потому что есть "шаг рекурсии" из 2 в 4), для 2 предыдущее 1, а для 1 — предыдущее 4. (внезапно, эти шаги назад — это 3n+1, потому что вы рассматриваете развернутый процесс.

Из приведённого текста для себя вынес полезное. Во первых - очень полезно указание на "маскирующий" характер деления на два. Во вторых - если обдумать задачу без упомянутой двойки, становится очевидным переход к использованию давно известных методов, не рассматриваемых в статье, но так же основывающихся на исследовании последовательностей, определяемых реккурентным соотношением. Ну и в третьих - подсказка про конкретный вид последовательности (3n+1) сократила необходимые затраты времени для обдумывания (которое вообще могло не состояться из-за неумения автора последовательно излагать доказательство).

Автору желаю освоить "программирование", то есть написать для себя такую программу, которая бы не прощала ошибок. На обычном компьютере программа с ошибками каким-либо образом об это сообщает, причём довольно наглядно, а вот в ходе доказательства логические ошибки, или ещё хуже - неполнота, никак о себе не заявляют. Вот потому и нужна автору программа, которая научит его писать доказательства без ошибок и пробелов. Пока же он этим умением не обладает - вряд ли кто-то возьмёт на себя труд изучить авторский текст достаточно подробно, что бы аргументированно опровергнуть сделанное заявление.

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

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

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

У автора вообще всё плохо с изложением материала. Он не умеет изъясняться.

Но справедливости ради, замечу, что «murkin-kot» говорит о рекуррентном соотношении в математике. Это рекурсия в теории алгоритмов.

Примерно раз-два в год на Хабре появляются статьи про доказательство (или какие-то личные мысли) гипотезы Коллатца. Отличаются они только степенью апломба авторов. Но всех их объединяет одно: они абсолютно игнорируют текущий прогресс в работах лучших математиков, абсолютно никак его не затрагивая, и начиная рассуждения с чистого листа, приводя примеры какого то программного кода. Хотя проблема эта сугубо математическая, а с точки зрения программ она уже давно показана прямым перебором до черти знает какого числа. И понятно дело, почему никто из журналов это не берет, но почему берет Хабр?

они абсолютно игнорируют текущий прогресс в работах лучших математиков, абсолютно никак его не затрагивая.

Наверное, потому, что во всех работах лучшие математики мира приходят к своим выводам, что не могут доказать великую гипотезу Коллатца.

То, на что вы в последний раз ссылались (60 страниц формул), показывает сходимость рядов к единице с вероятностью 99%. Но не отвечает на самый главный вопрос. Почему так происходит?

Что значит "почему так происходит?". Что Вы имеете ввиду? Сформулирована гипотеза, сформулирована четко в математическом смысле. Далее ее можно лишь доказать (ответом будет "сходится к единице"), либо опровергнуть.

Вы привели работу уважаемого математика, господина Тао, который показал, что 99% последовательностей Коллатца сходятся к единице, а 1% науке не известен.

Когда вы сослались на эту работу, что вы имели ввиду?

Знаете, я тут написал длинный коммент, но потом увидел один из ваших:
"Всё, что я сделал, это отказался от гипотезы Коллатца и перешел к задаче, из которой следует гипотеза Коллатца."

Так что все, что я писал, не имеет смысла. Теперь стало ясно, что вы, по сути, выдумали какую-то свою задачу, которую (наверно, проверить это сложно из-за отсутствия строгих математических рассуждений) и доказали. Так что единственная претензия - к заголовку статьи и и преамбуле: "Эта первая статья из цикла «Доказательство гипотезы Коллатца»". Гипотезу вы на самом деле не доказываете.

Спасибо вам, за понимание. Да, так и есть. Я доказываю не гипотезу Коллатца, а задачу из которой следует гипотеза Коллатца.

Если всё, что я написал, верно (я сейчас работаю над третьей частью публикации), то из этого следует, что гипотеза Коллатца доказана, потому что она – это простое умножение на 2, той задачи, которую я рассматриваю.

Ну, пока смысл и корректность всего этого понимаете вы один :) И оно так и останется, если вы не уйдете от вольных формулировок, частных примеров и программного кода.

Судя по тому, что автор ссылается на книгу Клини, формулировки должны быть корректными. Я просмотрел эту книгу, ее уровень высок. Так что, скорее всего, многие здесь просто не понимают изложенного. Насколько я понимаю, автор нашёл структуру, которая покрывает гипотезу Коллатца со всей полнотой.

Судя по тому, что автор ссылается на книгу Клини, формулировки должны быть корректными. Я просмотрел эту книгу, ее уровень высок. Так что, скорее всего, многие здесь просто не понимают изложенного. Насколько я понимаю, автор нашёл структуру, которая покрывает гипотезу Коллатца со всей полнотой.

Офигеть, вы сейчас такую глупость сказали! Стыдно должно быть. Вы или не читали статью, или не читали книгу. Или вы виртуал автора? Или вас просто по дружески попросили похвалить?


Просто упоминуть какую-то книгу не дает вообще ничего.


Автор придумывает какие-то свои термины, а терминами из книги бросается как умными словами ни к месту.


Книга упомянута в прошлой статье:


Во-первых, такой вид рекурсии в математике называется возвратная рекурсия или рекурсия пробега (см. книгу С.Клини, Введение в метаматематику, [гл. IX, §46]).

Вот, что написано в книге:


Аналогичная ситуация возникает при определении по индукции. Пусть значение функции f(0) задано, а значение f(y') выражается в терминах y и одного или нескольких предыдущих значений f(s), s<=y. Такая рекурсия называется "возвратной рекурсией" или "рекурсией пробега".

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


Ну и напоследок, процесс автора использует только одно текущее число, чтобы получить следующее. Ему не нужны "одно или несколько" предыдущих чисел. Поэтому термин "возвратная рекурсия" тут вообще никаким местом не натягивается.

Я просто стараюсь найти зерно истины :) А чтобы убедиться в правоте автора во всей полноте, требуется проделать примерно то, что проделал автор. Не спорю, доказать полноту не просто. В статье лишь готовые выжимки. А по поводу программирования и математики - да, требуется согласование терминологии. Это тоже не просто...

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

wataru, по поводу возвратной рекурсии мысль была простая:
– чтобы доказать, что любое число на любом шаге рекурсии вышло из единицы, мы должны помнить, что все предыдущие действия вышли из единицы.

Т.е. мы должны помнить всё дерево целиком.
Но вот нужно ли оно нам, это знание, это дерево, его структура, его ветви и прочее?
Возможно, что нет.

Возможно, что наши представления о рекурсии расходятся с самой сутью рекурсии.

В третьей части я попытаюсь свести всё воедино.

мы должны помнить, что все предыдущие действия вышли из единицы.

Нет, не должны. Вы должны только знать что одно предыдущее для заданного число вышло из 1.


Более того, индукцию вы по дереву коллатца использовать не можете, пока не докажете, что там нет циклов, а вы тут утверждаете, что используете индукцию, чтобы доказать, что циклов нет. Хотя и индукцию вы формально нигде не расписали и даже нигде не намекали на нее.


В итоге у вас получается доказательство "если допустить, что циклов нет, то циклов нет".

sci_nov, я скоро опубликую третью часть работы. Осталось немного.

На данный момент нет смысла вообще тут с кем-то что-то обсуждать.

Это будет конечная работа в рамках теории алгоритмов и математики по гипотезе Коллатца.

То, что пишет, wataru - он делает всё правильно. В математике принято цепляться за любое слово, запятую, фразу.

К сожалению, на данный момент, никто из читателей не сможет увидеть всей полноты моей работы. Т.к. он не знаком с другими моими публикациями, и моей перепиской с математиками на других форумах и по почте.

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

Ну, это так. Быть первопроходцем невыносимо тяжело. Вся полнота проделанной мною работы откроется в третьей части. Осталось немного.

Ребят, подскажите, что это значит? В профиле написано:
– У вас низкая карма. Вы можете публиковать свои статьи только раз в неделю. Следующая дата 10 мая.

И там же в профиле написано:
– Вы можете обнулить свою карму.

Нашел. Вопрос отпал.

Видимо, многие решили не тратить силы и не спорить с вами. И просто ставят минус в карму, потому что не хотят, чтобы вы и дальше писали эти свои статьи на хабр. Как всякие патентные бюро и научные журналы банят авторов вечных двигателей, или как вас уже забанили по, вашим же словам, на всяких математических формах.

Безобразие, с этим надо что-то делать. Я буду жаловаться. :)

Я думаю нужно решать эту задачу через теорию вероятностей с привлечением подходов, которые предложил Тао.

https://arxiv.org/abs/1909.03562

Да, мы можем, например, доказать, что гипотеза Коллатца верна на 99%.
Но это не доказательство. Т.к. останется 1%. Моя статья посвящена как раз доказательству.

Что я могу вам сказать? Как уже здесь отмечали многие, ваше доказательство слишком тривиальное.
Миллионы математиков делали то же самое. Вы согласны с этим? Все они пришли к выводу о недоказуемости гипотезы Коллатца. О чем это говорит?

О чём? Да, интересно...

О том, что вы неправы. Нужно искать ошибку. Попробуйте мыслить по-другому. Это очевидно.
Вы ушли от изначальных формулировок задачи и перешли к "рекурсиям", которые никому, кроме вас, непонятны.

Кстати, деление на 3 в принципе требует больше всего итераций. Это если применить некоторый итеративный алгоритм деления, который реализован через другие операции.

И ещё. Рекурсия с разделением на остатки от деления на 3 есть в Википедии, но на немецком языке:) Найдите гипотезу Коллатца, но на Deutsche

Collatz-Vermutung?

Да, примерно так

Можно подробнее, вы это имеете в виду?

g(n) = \begin{cases} \frac{2}{3}n, & n ≡ 0 \; mod \; (3) \\ \frac{4}{3}n-\frac{1}{3}, & n ≡ 1 \; mod \; (3) \\ \frac{4}{3}n+\frac{1}{3}, & n ≡ 2 \; mod \; (3) \end{cases}

Да.

Deutsche:
Collatz die folgende Permutation der positiven ganzen Zahlen betrachtet:
Diese Permutation besitzt den Fixpunkt 1 und außerdem zumindest die Zyklen (2, 3), (4, 5, 7, 9, 6). In dem zitierten Notizbucheintrag stellt Collatz die auch heute noch offene Frage, ob die mit 8 beginnende g-Trajektorie zyklisch wird oder gegen unendlich divergiert.

Перевод:
Коллатц также рассматривал функцию g().
Она начинается с 1, но имеет циклы (2, 3, 4, 5, 6, 7, 9). Коллатц пытался понять, что будет, если запустить функцию g() с числа 8? Будет ли снова цикл или нет?

Я вас не понял... Я просто дал ссылку, на всякий случай, не для обсуждений.

К сожалению, функция g() не имеет отношения к гипотезе Коллатца.

В немецкой Википедии её приводят в дань уважения к самому Коллатцу, т.к. он с ней игрался в 1932 году, и пытался понять, чем она так кардинально отличается от 3n+1.

Но вы правы! То, что Коллатц пытался развернуть процесс с единицы – поражает.

Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

Публикации

Истории