Почему вы исключаете шаг 1->1, мне непонятно. Потому что этот элементарный пример цикла является ярким контрпримером к вашему утверждению?
Нет смысла обсуждать то, что дано нам по условию задачи. Мы можем прописать в рекурсии условие, чтобы она создавала бесконечные циклические ветви для всех , не только для единицы. Это на вас окажет эффект? Нет, конечно. Ничего в задаче не изменится.
Но ответьте, пожалуйста, на следующие вопросы:
...Откуда такие выводы? Давайте по порядку. ...Где вы увидели шаги "увеличивающиеся в любом направлении"? ...Где повторы? Объясните, пожалуйста, ваш ход мысли. ...Как вы собираетесь отмотать рекурсию? Как вы собираетесь получить бесконечность там, где её нельзя получить?
Еще раз, все ваши рассуждения применимы к изначальной "рекурсии".
Простите. Но нет. Еще раз нет. И снова нет. Рекурсия умеет разветвлять числа, а рекурсия 3n+1 - нет, потому что это неполноценный алгоритм (обрубок). В рекурсии мы прописали шаг на разветвление, а в рекурсии 3n+1 мы его убрали. Это разные задачи. Именно поэтому, мыслив категориями 3n+1, вы ограничены в своих суждениях.
Но там ЕСТЬ цикл! 1->2->4->1->
Тогда, я процитирую первую часть публикации:
...Единица не может иметь другого прародителя, кроме самого себя, потому что и дают для единицы – единицу. ...Чётные числа являются ширмой в гипотезе Коллатца. ...Мы выкинули все чётные числа из рекурсии. ...Рекурсию нельзя остановить. Она бесконечна в любую сторону: 1 1 1 1 1 – это также движение.
Поэтому, 1 1 1 – не может быть циклом в рамках того, что мы с вами здесь обсуждаем: a->b->c->a->...
, это вообще не цикл. Это старт рекурсии. Прародитель сам себя создал и продолжает создавать бесконечно много раз.
Не надо мучить единицу. Пожалуйста, оставьте её в покое. Давайте условимся, что первую "прародительскую" итерацию мы не будем называть циклом. И вообще не будем её рассматривать. Иначе, как это уже было, прибежит секта свидетелей нуль-функции и всем нам кирдык (шутка). :)
— увеличивает в обратном направлении. 4x+1 — увеличивает в прямом.
wataru, вот здесь мы с вами уже друг друга не понимаем. Не только мы, но и читатели, наверное, тоже.
Далее, вы пишите:
Теоретически отматывая рекурсию назад можно тоже уйти в бесконечность, если начать с какого-то очень большого числа (недостижимого с 1).
Но как? Как вы собираетесь отмотать рекурсию? Как вы собираетесь получить бесконечность там, где её нельзя получить?
Шаг рекурсии настолько простейший, что всё доказательство гипотезы Коллатца сводится только лишь к нему. Не нужно больше ничего делать. Надо только его осмыслить.
Алгоритм 3n+1 - может двигаться только по тем числам, которые уже были проложены до него рекурсией , других вариантов нет.
Вот тут ошибка. Вы доказали, что нет цикла, в которой что-то входит снизу. Но из него может что-то выходить вверх.
Откуда такие выводы? Давайте по порядку. Статья посвящена полной версии алгоритма , где шаг рекурсии:
для случая n ≡ 2 mod(3),
для случая n ≡ 1 mod(3),
для случая n ≡ 0 mod(3), и постоянное применение к уже полученным числам
Таким образом, числа n ≡ 1 mod(3), n ≡ 2 mod(3) всегда порождают двух потомков. Числа вида n ≡ 0 mod(3) всегда порождают только одного потомка.
Родитель один. Потомков много.
Но если рекурсия породила два одинаковых числа, неважно на каком шаге, и неважно кому и кем они приходятся, то это зацикливание.
С точки зрения рекурсии не существует никаких верхов, низов, последовательностей, и прочей такой вот терминологии. Рекурсия – это шаг рекурсии. Всё, что мы можем, это взять число, которое уже когда-то было получено рекурсией, подставить его в рекурсию, получить новое число, снова его подставить в рекурсию и т.д.
Мы доказали, что этот процесс не подразумевает повторов. Где повторы? Объясните, пожалуйста, ваш ход мысли.
Тут тоже косяк. Почему не может рекурсия из бесконечности уменьшаться, пока не достигнет x, а потом увеличиваться по другим числам в бесконечность? Шаги-то есть увеличивающие в любом направлении.
Извините, но где вы увидели шаги "увеличивающиеся в любом направлении"? Для рекурсии есть только один увеличивающий шаг, это 4x+1. Никакое другое действие не увеличивает рекурсию. Я говорю именно про действие. Не про какие-то конкретные числа, которые, допустим, вы подставляете в рекурсию, и вам кажется, что вот, смотрите, число увеличилось. Нет. Я говорю именно про движение в сторону бесконечности. Оно единственное. Это 4x+1. Нет других движений.
Какое особое свойство у вашего "шага рекурсии" такое поведение запрещает вы не указали.
Указал. Это как раз центральный момент исследования.
Я процитирую:
Как сейчас уже очевидно, возрастание с единицы до бесконечности по алгоритму , основано только лишь на одном правиле 4x+1. Применение же формул , – это просто ветка "вправо-влево", которая ни на что не влияет, потому что каждая такая ветка всегда заканчивается хвостом рекурсии n ≡ 0 mod(3).
Акцентирую. Любое действие в рекурсии всегда заканчивается хвостом рекурсии n ≡ 0 mod(3). И с этим ничего нельзя сделать. На то он и хвост. Уравнение: не имеет целочисленного решения.
Таким образом, у рекурсии нет другого выбора, как расти в бесконечность по правилу 4x+1, потому что вся рекурсия фактически сводится (упрощается) только лишь к применению этого правила.
В общем-то, центральная мысль, которую я отстаиваю больше года:
Любое применение 3n+1 к любому нечетному числу – это уже рекурсия. Если вы согласились так сделать, то вы вошли в рекурсию и уже не сможете из неё выйти.
То, что это дерево покрывает все натуральные числа — нигде не доказано.
Доказательство.
Предположим, такое число есть, которое не покрывается рекурсией. Но, как мы уже доказали, циклов, повторов и зацикливания в рекурсии нет. Из этого следует, что подставив такое число в рекурсию мы получим противоречие. Потому что, прародитель (итерация назад) и рекурсия (итерация вперед) оба должны уйти в бесконечность. Это невозможно.
Если прародитель не идет к единице, и не зацикливается, то у него остается только один вариант – уйти в бесконечность. Но это невозможно. Это противоречит самой сути алгоритма. Нельзя получить две бесконечности из одного и того же алгоритма с тем шагом рекурсии, который мы установили (см. комментарий ниже).
Но ведь может быть изолированный цикл, в который ничто извне не ведет.
Не может быть изолированного цикла. Потому что мы имеем дело с рекурсией. В ваших рассуждениях вы апеллируете термином "отдельная последовательность". Но как вы себе представляете рекурсию? Её вообще-то нельзя остановить. Она бесконечна.
Она бесконечна в любую сторону. 1 1 1 1 1 ... – это также движение по рекурсии.
Акцентирую. Для рекурсии нет такого понятия как отдельно взятая "последовательность" a->b->c->a.
Для рекурсии любое число имеет прародителя и потомков. Рекурсия с чего-то там начинается и куда-то продолжается. Перед а нужно ставить x:
…->x->a->b->c->a->…
Но как мы уже доказали, рекурсия не может так зациклиться. Тогда остается только один вариант: рекурсия уходит в бесконечность и слева, и справа. Но это невозможно, это противоречит нашему алгоритму:
Для движение к бесконечности – это просто формула 4x+1.
Для 3n+1 приземление – это просто формула .
При таком шаге рекурсии, при таком движении, алгоритм не может уйти в бесконечность и слева, и справа.
Алгоритм 3n+1 – это вообще обрубок, которому суждено только приземляться. Он просто следует по дереву, которое для него уже построили.
Потому что мы имеем дело с рекурсией. В ваших рассуждениях вы апеллируете термином "последовательности". Но как вы себе представляете рекурсию? Её вообще-то нельзя остановить. Она бесконечна :)
Она бесконечна в любую сторону: 1 1 1 1 1 ... – это также движение по рекурсии.
Акцентирую. Для рекурсии нет такого понятия как отдельно взятая "последовательность" a->b->c->a.
Для рекурсии любое число имеет прародителя и потомков. Рекурсия с чего-то там начинается и куда-то продолжается. Перед а нужно ставить x:
…->x->a->b->c->a->…
Но как мы уже доказали, рекурсия не может так зациклиться. Тогда остается только один вариант: рекурсия уходит в бесконечность и слева, и справа. Но это невозможно, это противоречит нашему алгоритму:
Для движение к бесконечности – это просто формула 4x+1.
Для 3n+1 приземление – это просто формула .
При таком шаге рекурсии, при таком движении, алгоритм не может уйти в бесконечность и слева, и справа.
Алгоритм 3n+1 – это вообще обрубок, которому суждено только приземляться. Он просто следует по дереву, которое для него уже построили.
Но основной вопрос остался тем же, а вдруг какое-то число из 1 не получается?
Я на него для себя ответил так.
Первое, предположим, такое число есть.
Второе, мы отталкиваемся от того, что повторов, циклов и зацикливания в рекурсии нет.
Третье, подставив такое число в рекурсию мы получим противоречие. Потому что, прародитель (итерация назад) и рекурсия (итерация вперед) оба должны уйти в бесконечность. Смотрите, если прародитель не идет к единице, и не зацикливается, то у него остается только один вариант - уйти в бесконечность. Но это невозможно. Это противоречит самой сути алгоритма. Нельзя получить две бесконечности из одного и того же алгоритма (с тем шагом рекурсии, который мы установили).
wataru, кстати, во второй части публикации, я выложил исходный код программы (для запуска рекурсии из единицы). Если что-то вам надо, может быть, чем-то помочь, какие-то вопросы, пишите.
Смотрите, я не претендую ни на какие доказательства. Если у вас есть идеи – публикуйте, можете здесь в комментариях.
Но, вот, что хочу сказать, рекурсия – это основная сущность. Гипотеза Коллатца - это урезанный алгоритм, и на него не стоит ровняться. 3n+1 – это производная форма от .
Общение в интернете мне дается с трудом. Это правда. Что-то надо с этим делать. При личном общении, на той же кафедре математики с докторами математических наук я веду себя по-другому. Спасибо вам за критику. Я ценю это. Поверьте.
Нет смысла обсуждать то, что дано нам по условию задачи. Мы можем прописать в рекурсии условие, чтобы она создавала бесконечные циклические ветви
для всех 
, не только для единицы. Это на вас окажет эффект? Нет, конечно. Ничего в задаче не изменится.
Но ответьте, пожалуйста, на следующие вопросы:
Ответил вам во второй части публикации.
Да, вы правы, Википедия ссылается на работы S. Kurtz и J. Simon, которые пришли к выводу, что в такой постановке вопроса задача 3n+1 не доказуема.
Но 3n+1 - это алгоритм обрубок. Его в принципе не нужно было исследовать. Нужно было сразу переходить к полной версии алгоритма.
Вы перешли на личности? :(
Простите. Но нет. Еще раз нет. И снова нет.
умеет разветвлять числа, а рекурсия 3n+1 - нет, потому что это неполноценный алгоритм (обрубок).
мы прописали шаг на разветвление, а в рекурсии 3n+1 мы его убрали.
Рекурсия
В рекурсии
Это разные задачи. Именно поэтому, мыслив категориями 3n+1, вы ограничены в своих суждениях.
Тогда,
я процитирую первую часть публикации:
Поэтому, 1
1 
1 
– не может быть циклом в рамках того, что мы с вами здесь обсуждаем: a->b->c->a->...
Не надо мучить единицу. Пожалуйста, оставьте её в покое.
Давайте условимся, что первую "прародительскую" итерацию мы не будем называть циклом. И вообще не будем её рассматривать. Иначе, как это уже было, прибежит секта свидетелей нуль-функции и всем нам кирдык (шутка). :)
wataru, вот здесь мы с вами уже друг друга не понимаем. Не только мы, но и читатели, наверное, тоже.
Далее, вы пишите:
Но как? Как вы собираетесь отмотать рекурсию? Как вы собираетесь получить бесконечность там, где её нельзя получить?
Шаг рекурсии
настолько простейший, что всё доказательство гипотезы Коллатца сводится только лишь к нему. Не нужно больше ничего делать. Надо только его осмыслить.
Алгоритм 3n+1 - может двигаться только по тем числам, которые уже были проложены до него рекурсией
, других вариантов нет.
Доброжелательно.
Спасибо! Вы третий человек, который проверил этот код. Сначала был «Soul Friend», потом я, теперь вы. Так, глядишь, четвертого найдем :)
Откуда такие выводы? Давайте по порядку.
, где шаг рекурсии:
для случая n ≡ 2 mod(3),
для случая n ≡ 1 mod(3),
для случая n ≡ 0 mod(3),
Статья посвящена полной версии алгоритма
и постоянное применение к уже полученным числам
Таким образом, числа n ≡ 1 mod(3), n ≡ 2 mod(3) всегда порождают двух потомков. Числа вида n ≡ 0 mod(3) всегда порождают только одного потомка.
Родитель один. Потомков много.
Но если рекурсия породила два одинаковых числа, неважно на каком шаге, и неважно кому и кем они приходятся, то это зацикливание.
С точки зрения рекурсии не существует никаких верхов, низов, последовательностей, и прочей такой вот терминологии. Рекурсия – это шаг рекурсии. Всё, что мы можем, это взять число, которое уже когда-то было получено рекурсией, подставить его в рекурсию, получить новое число, снова его подставить в рекурсию и т.д.
Мы доказали, что этот процесс не подразумевает повторов. Где повторы? Объясните, пожалуйста, ваш ход мысли.
Извините, но где вы увидели шаги "увеличивающиеся в любом направлении"? Для рекурсии
есть только один увеличивающий шаг, это 4x+1. Никакое другое действие не увеличивает рекурсию. Я говорю именно про действие. Не про какие-то конкретные числа, которые, допустим, вы подставляете в рекурсию, и вам кажется, что вот, смотрите, число увеличилось. Нет. Я говорю именно про движение в сторону бесконечности. Оно единственное. Это 4x+1. Нет других движений.
Указал. Это как раз центральный момент исследования.
Я процитирую:
Акцентирую. Любое действие в рекурсии
всегда заканчивается хвостом рекурсии n ≡ 0 mod(3). И с этим ничего нельзя сделать. На то он и хвост. Уравнение: 
не имеет целочисленного решения.
Таким образом, у рекурсии
нет другого выбора, как расти в бесконечность по правилу 4x+1, потому что вся рекурсия фактически сводится (упрощается) только лишь к применению этого правила.
У автора вообще всё плохо с изложением материала. Он не умеет изъясняться.
Но справедливости ради, замечу, что «murkin-kot» говорит о рекуррентном соотношении в математике. Это рекурсия в теории алгоритмов.
В общем-то, центральная мысль, которую я отстаиваю больше года:
Любое применение 3n+1 к любому нечетному числу – это уже рекурсия. Если вы согласились так сделать, то вы вошли в рекурсию и уже не сможете из неё выйти.
Вот и весь фокус Коллатца.
Доказательство.
Предположим, такое число
есть, которое не покрывается рекурсией.
в рекурсию 
мы получим противоречие. Потому что, прародитель (итерация назад) и рекурсия (итерация вперед) оба должны уйти в бесконечность. Это невозможно.
Но, как мы уже доказали, циклов, повторов и зацикливания в рекурсии нет.
Из этого следует, что подставив такое число
Если прародитель не идет к единице, и не зацикливается, то у него остается только один вариант – уйти в бесконечность. Но это невозможно. Это противоречит самой сути алгоритма. Нельзя получить две бесконечности из одного и того же алгоритма с тем шагом рекурсии, который мы установили (см. комментарий ниже).
Не может быть изолированного цикла. Потому что мы имеем дело с рекурсией. В ваших рассуждениях вы апеллируете термином "отдельная последовательность". Но как вы себе представляете рекурсию? Её вообще-то нельзя остановить. Она бесконечна.
Она бесконечна в любую сторону. 1
1 
1 
1 
1 
... – это также движение по рекурсии.
Акцентирую. Для рекурсии нет такого понятия как отдельно взятая "последовательность" a->b->c->a.
Для рекурсии любое число имеет прародителя и потомков. Рекурсия с чего-то там начинается и куда-то продолжается. Перед а нужно ставить x:
…->x->a->b->c->a->…
Но как мы уже доказали, рекурсия не может так зациклиться. Тогда остается только один вариант: рекурсия уходит в бесконечность и слева, и справа. Но это невозможно, это противоречит нашему алгоритму:
Для
движение к бесконечности – это просто формула 4x+1.
Для 3n+1 приземление – это просто формула
.
При таком шаге рекурсии, при таком движении, алгоритм
не может уйти в бесконечность и слева, и справа.
Алгоритм 3n+1 – это вообще обрубок, которому суждено только приземляться. Он просто следует по дереву, которое для него уже построили.
Потому что мы имеем дело с рекурсией. В ваших рассуждениях вы апеллируете термином "последовательности". Но как вы себе представляете рекурсию? Её вообще-то нельзя остановить. Она бесконечна :)
Она бесконечна в любую сторону: 1
1 
1 
1 
1 
... – это также движение по рекурсии.
Акцентирую. Для рекурсии нет такого понятия как отдельно взятая "последовательность" a->b->c->a.
Для рекурсии любое число имеет прародителя и потомков. Рекурсия с чего-то там начинается и куда-то продолжается. Перед а нужно ставить x:
…->x->a->b->c->a->…
Но как мы уже доказали, рекурсия не может так зациклиться. Тогда остается только один вариант: рекурсия уходит в бесконечность и слева, и справа. Но это невозможно, это противоречит нашему алгоритму:
Для
движение к бесконечности – это просто формула 4x+1.
Для 3n+1 приземление – это просто формула
.
При таком шаге рекурсии, при таком движении, алгоритм
не может уйти в бесконечность и слева, и справа.
Алгоритм 3n+1 – это вообще обрубок, которому суждено только приземляться. Он просто следует по дереву, которое для него уже построили.
Я на него для себя ответил так.
Первое, предположим, такое число
есть.
Второе, мы отталкиваемся от того, что повторов, циклов и зацикливания в рекурсии нет.
Третье, подставив такое число
в рекурсию 
мы получим противоречие. Потому что, прародитель (итерация назад) и рекурсия (итерация вперед) оба должны уйти в бесконечность. Смотрите, если прародитель не идет к единице, и не зацикливается, то у него остается только один вариант - уйти в бесконечность. Но это невозможно. Это противоречит самой сути алгоритма. Нельзя получить две бесконечности из одного и того же алгоритма (с тем шагом рекурсии, который мы установили).
Согласен.
«Soul Friend» сам балбес. Надо было доводить дело до конца, еще 5 лет назад. Кто знает, сколько бы бессонных ночей он бы спас :)
wataru, кстати, во второй части публикации, я выложил исходный код программы (для запуска рекурсии из единицы). Если что-то вам надо, может быть, чем-то помочь, какие-то вопросы, пишите.
Смотрите, я не претендую ни на какие доказательства. Если у вас есть идеи – публикуйте, можете здесь в комментариях.
Но, вот, что хочу сказать, рекурсия
– это основная сущность. Гипотеза Коллатца - это урезанный алгоритм, и на него не стоит ровняться. 3n+1 – это производная форма от 
.
Общение в интернете мне дается с трудом. Это правда. Что-то надо с этим делать. При личном общении, на той же кафедре математики с докторами математических наук я веду себя по-другому. Спасибо вам за критику. Я ценю это. Поверьте.
Вот сюда я выложил код программы. Код рабочий. Отпишитесь, пожалуйста, в личку, если есть какие-то вопросы.
sci_nov, спасибо вам за добрые слова. Доброе слово и кошке приятно!
Мой эмоциональный настрой (и в некоторых случаях агрессивность) - это следствие общения с математиками. Извините, если что не так. :)
Когда я делал перевод этой статьи на английский язык, то я использовал устоявшийся термин:
Может быть, это как-то поможет нам с вам в терминологии.