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

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

Видео по этой теме (RU):

Каждый раз под впечатлением от визуализации в этих сериях!)

Определённо результат есть следствие самих правил.

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

В видео по моей ссылке как-раз об этом.

извините за глупый вопрос - зачем нечетное число сначала умножать на 3? При умножении нечетного числа на 3 все равно ведь получим нечетное, затем, чтобы получить четноеЮ прибавляем 1. Вроде бы если просто к исходному нечетному числу прибавить 1 (не умножая его предварительно на 3), получим четное число, а далее идем согласно алгоритму. Результат будет тем же (4 - 2 -1), только придем к нему короче. Можете, пожалуйста, объяснить, в чем смысл умножения на 3?

Подозреваю, чтобы оно точно стало не простым... Если в формулировке задачи было - берем любое непростое число - это чуть чуть сложнее, чем берем любое число и умножаем на 3. Хотя можно по программе проверить - работает ли гипотеза при умножении на 7 например ...

Если просто прибавить 1, то в итоге гарантированно придем к единице, доказать просто. В случае 3*n+1 доказать, что для любого натурального n результат будет единица, пока никому не удалось, т.к. не исключены другие два варианта: результат устремится к бесконечности или результат замкнется в цикле, отличном от 4-2-1.

... или может быть еще один цикл "четное-четное-нечетное", который не 4-2-1

Другого цикла из 3х элементов быть, скорее всего, не может. Доказывается просто
Обозначим последнее число (нечётное) за X. Согласно циклу можно получить последовательность "3x+1, (3x+1)/2, (3x+1)/4", она же "4x, 2x, x". Выводим формулу: (3x+1)/4=x => x=1. Других решений нет

В видео из первого комментария утверждают, что есть пруф на то, что если цикл и существует - он не может включать меньше чем 180 миллиардов чисел.

Тогда,насколько я понял, мы не придем к результату 4-2-1, который будет повторяться бесконечное количество раз

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

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

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

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

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

С Гёделем, если вы про полноту, то там не все так просто. В доказательстве нет ошибок, но он оно построено на законе исключённого третьего. Он кажется логичным, и в большинстве случаев даёт результат, который отражается в мире. Но такие доказательства, построенные от противного - имхо, показывают что не все так радужно. И, возможно, в целом - работает многозначная логика, и тогда часть докозателсьв неприменимы.

Моя позиция сформирована под влиянием книги "Гёдель, Эшер, Бах" Хофштадтера, всячески рекомендую.

вам бы с обычной логикой разобраться

Тут хохма в том, что сам ввод многозначной логики уже означает выделение верных, но недоказуемых утверждений.

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

Согласен. Простое перемалывание чисел до тех пор, пока мы не наткнёмся на очередную степень двойки.

Ну например очевидно, что к примеру ряд f(n)=f(n-1)+1 и f(0)=1 никогда не наткнется на степень двойки. Почему же тут мы уверены что всегда будем натыкаться на степень двойки

Либо это определение арифметической последовательности, либо я туплю...

Все верно. Только там ошибка. Надо f(n)=f(n-1)*2+1 и f(0)=1

ну ряды разные и судить по одному о свойствах другого вряд ли в этом случае поможет

Тут наверное фокус не в степени двойки, а в том, что всё больше становится чётных чисел, которые дают после деления чётное число. таким образом алогоритм сваливается к маленьким числам, где уже достигает степени двойки.
Хотя это всё гипотезы :)

Чётных чисел всегда половина

Не совсем верно. Четных чисел столько же сколько всех чисел (натуральных или целых)

Но не действительных :)

К сожалению, это так. Хотя здравый смысл подсказывает, что во множестве чётных чисел не хватает некоторых чисел, входящих во множество целых)

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

Нет, тут дело не в аксиоме выбора. Парадокс удвоения шара возможен потому что свободная группа с двумя образующими допускает специальное разложение (https://en.wikipedia.org/wiki/Paradoxical_set). Это связано с тем что шар вложен в трёхмерное Евклидово пространство, а на плоскости такой парадокс уже невозможен.

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

Да, пример неудачный, согласен. :)

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

Вы бы что предложили?

Например, Канторово множество, которое имеет меру нуль, но тем не менее его мощность континуум

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

Да. Но почему не может быть так - умножается на 3 (+1) --> делится на 2 --> умножается на 3 --> делится на 2, и так много-много раз? Будет расти, просто потому, что 3 больше, чем 2. А потом, даже если вдруг поделим на 2 больше одного раза - ну уменьшится немного. А потом снова будет вот так же расти?

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

Простое перемалывание чисел до тех пор, пока мы не наткнёмся на очередную степень двойки

Простое, да не совсем. Если изменить условие и вместо +1 сделать -1, то уже с числа 5 мы не выходим на степень двойки. 5-14-7-20-10-5...

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

Попробуйте доказать, что следующее число должно делится на степень двойки выше чем 1. Или что средняя степень двойки выше, чем log(3)/log(2). То, что гипотеза кажется рабочей на небольших числах, которые мы можем посчитать, ничего не значит.

Особенно Skewes' number

Гипотеза Пуанкаре тоже в некотором роде перельмановская задачка. :)

А как по научному оформить вариант решения, если он есть, и где публиковать?

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

Не маловато ли девяток?

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

Ландау заказал в университетской типографии 500 бланков со следующим текстом: «Уважаемый …! Благодарю Вас за присланную Вами рукопись с доказательством Великой теоремы Ферма. Первая ошибка находится на стр. … в строке …»

Алексей Савватеев на канале Маткульт-привет! недавно повторил его подвиг в видео. Ничего, так все теоремы без "великих математиков" в Кембридже и Оксфорде докажут. Нашим только крошки с их десктопов упадут.

Да где угодно, главное опубликовать

Оформите решение в системе coq.

Фрактал Коллатца чем то на Мандельброта похож..

const test = x => x%2 === 0 ? x/2 : x*3+1;

const run = x => { if (x!==4) { console.log(x); run(test(x)) }};

Кто хочет в браузере погонять

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

Ожидал что-то поэффектнеее Парадокса Монти Холла, по крайней мере заголовок именно это и обещал.

Не уверен, что сабж является самым крутым фокусом, но, имхо, уж покрупнее Монти-Холла (да и в тервере, кстати, есть более забавные штуки, например нетранзитивные кости или игры с рандомизированной стратегией).

Так себе фокус. По-моему, всё очевидно. Зачем умножать на 3 в условии задачи? Можете сразу прибавлять 1 к выбранному нечетному числу и поворять шаг 1, получите то же самое с той же сутью.

Нет, это совсем другое. В гипотезе Коллатца, например, из 11 переходим в 34, и оттуда в 17. Это гораздо более "рандомная" последовательность, чем +1 и /2. Полная последовательность, начиная с 11, будет выглядеть 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1.

Интуитивно кажется, что вы правы, и 3-ка здесь только для запутывания, так как работа с ней делает последовательность менее очевидной.
Но если задачи эквивалентны, это ещё надо строго доказать… И пока не известно, доказательство чего проще (и правильна ли гипотеза из статьи в принципе).

По-моему, всё очевидно. Зачем умножать на 3 в условии задачи?

Как раз для того чтобы было неочевидно. Навскидку кажется очевидным иное - число чётных и нечетных чисел в случайной выборке равно, четные делятся пополам, нечетные умножаются на 3, таким образом средний результат должен вроде как представлять серию умножений на 3/2, и в результате должен бесконечно возрастать. Однако для любых чисел последовательность с завидным постоянством, немного побрыкавшись, приводит к единице. Парадокс.

Не должен. +1 приводит любое нечетное к четному.

Не, тут всегда известно что сразу после умножения на 3 последует 1 деление на 2.

Таким образом в среднем за (1/2 + 3/2)/2 = 1. Но в случае с умножением нужно брать среднее геометрическое (или перейти к логарифмам), тут уже будет результат sqrt(3)/2~0.86<1.

Парадокса нет, проблема в том что нужно доказать для каждого, а не в "среднем".

Пусть начальное число А чет нечет — как повезет. к — средний коэффициент для следующего шага. Формула для "через 2 шага"


0,5(А:2*к) + 0,5((А*3+1):2)=А*к^2
к =((А(А*49+16))^0,5 + А)/(8А) 

что при больших А стремиться к 1, так что 3/2 тут не пахнет.

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

Для х > 1, x + 1 < 2x - значит наша последовательность будет содержать убывающую подпоследовательность. А т.к. числа натуральные, то эта подпоследовательность будет содержать минимальный элемент - еденицу.

В случае просто приавления 1 задача тривиальна: после +1 получаем чётное число, после деления 0,5n + 0.5, что заведомо меньше изначального (для чисел больше одного). Таким образом мы получаем убывающую последовательность, которая сходится к одному.

С умножением на 3 такой фокус не проходит: т.е. числа упираются в какое-то подобие степеней двойки. Немного контринтуитивно.

Выше привели пример: если делать не +1, а -1, то вроде суть всё ещё та же, но уже на пятёрке вы замкнётесь без достижения единицы. Но суть-то та же?

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

Например, вот такое уравнение:

имеет такие натуральные корни:

Или может оказаться так, что она нерешаема за разумное время (как, например, вычисление TREE(3)), или существование решения практически недоказуемо.

На работе решил отвлечься на Хабр... Зря так сделал. В итоге час просто сам себе пытался доказать эту гипотезу. По-моему, её доказательство достаточно простое (если отталкиваться от чётности-нечётности и если я не обманул сам себя)

Сейчас написать своё решение не могу - надо полностью его продумать. Но буду надеяться, что по приезду домой смогу написать мини-статью (или просто большой комментарий) с некоторыми выкладками по этой теории

P.S. Смотрю на свои записи и удивляюсь... Если гипотеза градины до сих пор гипотеза, то мне не верится, что моё доказательство может считаться полноценным - слишком оно лёгкое

Это вольный пересказ записей на полях теоремы Ферма? :)

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

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

Очень интересно! Главное - вовремя остановиться, так как гипотеза Коллатца уже получила дурную славу среди математиков, потративших на неё десятилетия жизни :)

У теоремы Ферма тоже была дурная репутация, но Уайлс смог. :)

Уайлс доказывал не саму теорему Ферма, а более общую гипотезу, так что он знал, что делает.

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

Ну, этот попробует как программист.
С продвижением к бесконечности все больше чисел, в двоичной системе имеющих хвост из нулей — то есть, многократно делимых на 2. Между тем как любое нечетное число после первого же преобразования всегда становится четным и испытывает распространение переноса — более или менее массовый битфлип с образованием хвоста из нулей.


Каждое число на каждой итерации испытывает не более одного увеличения (после которого становится четным) и не менее одного уменьшения (младший бит после умножения на нечетное число и сложения с единицей с вероятностью 100% будет нулевым). Бит 1 с вероятностью 50% окажется равным 0, Бит 2 — 25%, Бит 3 — 12,5%, что дает в пределе 2 (последовательных уменьшения).


Итого, произвольно взятое число, грубо, в среднем умножается на 3 и делится на 4.

Проблема среднего в том, что не учитываются выбросы.

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

Так в данном случае выбросы — это несколько делений подряд, так? Когда мы получаем число вида a*2^n.

Наоборот, выброс - много умножений на 3. Т.е. число вида 2^n-1

Такое число за 2n шагов перейдет в 3^n-1

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

Но возможен каскад пар - `n -> 3n+1 -> (3n+1)/2 -> 3*(3n+1)/2+1 -> (3*(3n+1)/2+1)/2 -> ...`. Если в цепочке нет двух делений подряд, то каждая пара операций будет увеличивать значение числа.

… до тех пор, пока оно не напорется на a*2^n, хвост из нулей.

Так вот в этом и вопрос - оно всегда на такой хвост наткнётся, или только "почти всегда"?

Множество чисел вида a*2^n разве не мощнее множества нечетных чисел, произведениями которых (и не только их) они являются?
Не силен в теории множеств, могу нести чушь )

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

Да, вы правы.

Нет, не мощнее. Они оба - "алеф-0". Между элементами этих множеств легко установить взаимно-однозначное соответствие, по аналогии с тем как это делается для соответствия целых и рациональных.

Спасибо.

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

По мне, так ключевая мысль. Если рассмотреть последовательности подряд чётных чисел, то получится, что единственное целочисленное решение, при котором ряд закольцовывается, получается при двух чётных подряд и число должно быть 1. При больших числах целых чисел нет - там ряд плавно убывает к нулю. ЧТД.

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

Строго говоря, не факт что "простые" пути, в принципе могут существовать.

Пример - последовательность гудстейна.

https://ru.wikipedia.org/wiki/Теорема_Гудстейна

Работает примерно по такому же принципу - берём некое стартовое число, делаем вполне себе алгоритмичную операцию над числом, повторяем до упора. Увы, операция не такая красивая и простая, как в этом примере, но тоже что-то что в две строчки делается на бумаге.

Прикол в том, что доказано, что теорема гудстейна недоказуема в аксиоматике пеано. То есть не получится придумать доказательство по индукции.

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

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

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

Другой похожий пример - это задача о гидре

https://avva.livejournal.com/244874.html?delayedid=

Ну вот у вас есть схема гидры. Вполне себе такая конечная контрукция. Граф. Можно в структурку на любимом языке программирования записать.

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

Обязательно напишите. Даже если ошиблись, то напишите, где. Изучать ошибки тоже интересно.

на любимом Delphi

Точно ли он любимый???

   readln(s);
   num:=strtoint(s);  // Исходное число
 ...
   writeln(inttostr(num));
   readln(num);  // Исходное число
 ...
   writeln(num);

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

Вот так я и познакомился с задачей "3n+1" :)

У кого есть доступ к вычислительным ресурсам и настроение что-то сделать, можно сделать следующее. Эта задача — пусть будет f(3,2). То есть 3n+1, n/2. f(x,y): xn+1, n/y.
Просчитать для разных x и y. И отметить на графике (x,y) точки разного цвета: приходит к 1, уходит в бесконечность, зацикливается.

Тут вы предполагаете, что f(x,y) будет вести себя одинаково с любым стартовым n.
Но это как раз не доказано даже для f(3,2). Для других тем более, вполне может оказаться функция, ведущая себя очень по разному для разных начальных значений.

На звание самого крутого математического фокуса не тянет. Ожидал что действительно можно будет угадать число. А тут прогностическая способность уровня - возьмите любое положительное целое число и и отнимайте от него по 1. Как бы вы ни старались оно превратится в 1. Уау, правда?

Только неизвестно сколько раз отнимать.

Число Пи тоже содержит все числа от 0 до 9. Тоже можно поугадывать, если не важно где цифра должна стоять и картинок нарисовать, может даже более красивых. Там даже интересней - а вдруг оно содержит ваш номер телефона, и если да, то кому принадлежат соседние номера. Или если поставить в соответствие числам буквы, можно ли там найти ваше имя и фамилию.

А тут получается, надо "просто" найти второе число, которое зациклит алгоритм.

Ожидал что действительно можно будет угадать число. А тут
прогностическая способность уровня - возьмите любое положительное целое
число и и отнимайте от него по 1. Как бы вы ни старались оно превратится
в 1. Уау, правда?

Ну, для того, чтобы доказать, что в вашей задаче число всегда превратиться в единицу нужно секунд 30 и квалификация школьника.

Для того, чтобы доказать, что в задаче 3n+1 число всегда превратиться в единицу пока не хватило 90 лет и квалификации лучших математиков этой планеты.

Хотя, по вашим же словам, сама задача выглядит столь же простой, как и в первом случае.

По-моему, это как минимум любопытно

Число Пи тоже содержит все числа от 0 до 9. Тоже можно поугадывать, если не важно где цифра должна стоять и картинок нарисовать, может даже более красивых. Там даже интересней - а вдруг оно содержит ваш номер телефона, и если да, то кому принадлежат соседние номера. Или если поставить в соответствие числам буквы, можно ли там найти ваше имя и фамилию.

Ну, собственно, да.

Доказать, что какая-то конкретная последовательность не встретится в десятичной записи числа Пи (или доказать, что любая конечная последовательность рано или поздно встретится) - это чертовски интересный результат, который было бы очень интересно рано или поздно увидеть.

Не понимаю вашего сарказма, что не так-то?

Ферматисты скажут: " Тьфу, и это докажем!"

Извините, а ещё больше вы скриншот сделать не могли?

Извините, кажется девятки ушли в апскейлинг

Если число чётное, разделите его на 2. Иначе умножьте его на 3 и прибавьте 1.

(во втором случае можно сразу разделить на 2, так как всегда получается четное число)


Я думал над этой задачей некоторое время, пришел к такому выводу. Если не делить на 2, то прибавлять надо будет не 1, а некоторую степень двойки, которая равна позиции младшей единицы в двоичной записи текущего числа (или что-то вроде того). Тогда получается примерно такая цепочка:


00001xxxxxxx1
0001xxxxxxx10
0001xxxxxx100
001xxxxxx1000

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

Delphi для вас не очень любимый, потому что в коде есть лишние вещи. Например, преобразования типов в тех местах, где они нафиг не нужны. Условие неравности, где надо проверять на "больше", лишние writeln, но отсутствие readln в конце для паузы, раз уж вы сделали консольное приложение.

program collatz;
{$APPTYPE CONSOLE}
var
 iNum, iSteps, iMax: integer;
begin
  readln(iNum);

  iSteps := 0;
  iMax   := iNum;

    while iNum > 1 do begin
      if Odd(iNum) then iNum := iNum * 3 + 1
        else iNum := iNum div 2;

      if iNum > iMax then iMax := iNum;

      inc(iSteps);
      writeln(iNum);
    end;

  write('Steps : ', iSteps, #13#10, 'Max   : ', iMax);
  readln;
end.

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

Как в 1960 г. писал математик Сидзуо Какутани:

For about a month everyone at Yale worked on it, with no result. A similar phenomenon happened when I mentioned it at the University of Chicago. A joke was made that this problem was part of a conspiracy to slow down mathematical research in the U.S.

(Примерный перевод: "Каждый в Йельском университете проработал над этой проблемой в течение месяца. Похожий фенонен наблюдался в Чикагском университете после того, как я упомянул о ней. Ходила шутка, что эта задача была частью заговора, имевшего целью затормозить математические исследования в США.".)

Классные комментарии. Ещё немного и гипотезу Коллатца можно будет переименовывать в теорему Коллатца-Хабра. :)

Любое натуральное число с периода от единицы до ∞ идет в цикл 4, 2, 1. Есил задачу решить, то надо числа в 16 ричную систему счисления перевести и вычислять через бесконечный цикл прибавляя единицу.

Зарегистрируйтесь на Хабре , чтобы оставить комментарий

Публикации

Истории