Математики считают гипотезу Коллатца «болотом», и предупреждают друг друга, что от неё стоит оставаться подальше. Однако теперь Теренс Тао достиг большего прогресса, чем кто бы то ни было за несколько десятилетий.
Возьмите любое число. Если оно чётное, поделите его на два. Если нечётное, умножьте на три, прибавьте один. Повторите. Любое ли число в итоге приходит к 1?
Опытные математики советуют новичкам держаться подальше от гипотезы Коллатца. Они называют её песней сирен: попади под её влияние, и можешь уже никогда не добраться до осмысленной работы.
Гипотеза Коллатца, возможно, простейшая из нерешённых задач математики – именно это и делает её такой предательски притягательной.
«Это очень опасная задача. Люди становятся одержимыми ею, при том, что она совершенно невозможна», — сказал Джеффри Лагариас, математик из Мичиганского университета, эксперт по гипотезе Коллатца.
Но в 2019 году один из лучших математиков мира осмелился подступиться к ней, и получил самый значимый из всех результатов, что были достигнуты за несколько десятилетий.
8 сентября 2019 Теренс Тао опубликовал доказательство, где показано, что гипотеза Коллатца, по меньшей мере, «почти» верна «почти» для всех чисел. И хотя результат Тао не является полным доказательством гипотезы, это очень серьёзный прорыв для задачи, не так-то легко раскрывающей все свои секреты.
«Я не ожидал решить задачу полностью, — сказал Тао, математик из Калифорнийского университета в Лос-Анджелесе. – Но у меня получилось сделать больше, чем я ожидал».
Головоломка Коллатца
Лотар Коллатц, вероятно, высказал одноимённую гипотезу в 1930-х годах. Задача звучит, как фокус для вечеринок. Возьмите любое число. Если оно чётное, поделите его на два. Если нечётное, умножьте на три, прибавьте один. Получится новое число. Примените те же правила для него. Гипотеза говорит о том, что произойдёт, если настойчиво повторять этот процесс.
Интуиция подсказывает, что начальный номер влияет на конечный результат. Возможно, некоторые числа в итоге будут уменьшаться до 1. Возможно, другие числа будут увеличиваться до бесконечности.
Однако Коллатц предсказал, что это не так. Он предположил, что если вы начнёте с положительного целого числа, и достаточно долго будете повторять указанную последовательность, то с любого начального числа придёте к 1. А придя к единице, правила гипотезы поймают вас в бесконечную петлю: 1, 4, 2, 1, 4, 2, 1, и так далее, до бесконечности.
С годами многих любителей задач притягивала привлекательная простота гипотезы Коллатца, или «задачи 3х+1», как её ещё называют. Математики проверили уже квинтиллион примеров (это число с 18 нулями), не найдя ни единого исключения из предсказания Коллатца. Вы и сами можете попытаться проверить несколько примеров с любым из множества имеющихся в интернете "калькуляторов Коллатца". В интернете полно необоснованных любительских доказательств гипотезы, авторы которых утверждают, что им удалось её доказать или опровергнуть.
«Вам нужно только уметь умножать на 3 и делить на 2, и вы уже можете начать играться с ней. И это очень заманчиво», — сказал Марк Чамберленд, математик из Колледжа Гриннела, записавший популярное на YouTube видео об этой задаче под названием «Простейшая из невозможных задач».
А вот истинных доказательств немного.
В 1970-х математики показали, что почти все последовательности Коллатца – список чисел, которые вы получаете при повторении процесса – в итоге приходят к числу меньшему, чем начальное. Это было слабое свидетельство того, что почти все последовательности Коллатца приводят к 1, но тем не менее, оно было. И с 1994 года до полученного в 2019 году результата Тао, рекорд по демонстрации минимального значения удерживал Иван Корец. Другие работы сходным образом пытались атаковать задачу, не приближаясь к её главной цели.
«Мы, на самом деле, не понимаем вопроса Коллатца достаточно хорошо, поэтому значительных работ по этому вопросу не было», — сказал Каннан Саундарараджан, математик из Стэнфордского университета, работавший над этой гипотезой.
Тщетность этих попыток привела многих математиков к заключению, что эта гипотеза просто недоступна при текущем уровне знаний, и что им лучше тратить своё время на другие исследования.
«Задача Коллатца известна своей сложностью – настолько, что математики обычно предваряют каждое её обсуждение предупреждением не тратить на неё время», — сказал Джошуа Купер из университета Южной Каролины.
Неожиданный совет
Впервые Лагариас заинтересовался этой гипотезой, будучи студентом, не менее 40 лет назад. Десятилетиями он был неофициальным куратором всего, что с ней связано. Он набрал целую библиотеку связанных с нею работ, и в 2010 опубликовал некоторые из них в виде книги под названием: "Решающий вызов: задача 3х +1".
«Теперь я гораздо больше знаю об этой задаче, и всё равно могу сказать, что решить её невозможно», — сказал Лагариас.
Обычно Тао не тратит своё время на невозможные задачи. В 2006 году он получил Филдсовскую премию, высшую награду по математике, и считается одним из лучших математиков своего поколения. Он привык решать задачи, а не гоняться за воздушными замками.
«Это риски, связанные с профессией математика, — сказал он. – Можно стать одержимым одной из больших известных задач, находящихся за пределами возможностей любого человека, и потерять кучу времени».
Однако у Тао не всегда получается противостоять искушениям из этой области. Каждый год он тратит один-два дня на самые известные из нерешённых задач по математике. С годами он делал несколько подходов и к гипотезе Коллатца, но безуспешно.
Затем в августе анонимный читатель оставил в блоге Тао комментарий. Он предложил попробовать решить гипотезу Коллатца «почти для всех» чисел, не пытаясь полностью доказать её.
«Я не ответил, однако это заставило меня снова задуматься об этой задаче», — сказал Тао.
И он понял, что гипотеза Коллатца была в некотором роде похожа на особые типы уравнений – дифференциальные уравнения в частных производных – появлявшихся в наиболее значительных результатах, полученных им за время его карьеры.
Входы и выходы
Дифференциальные уравнения в частных производных (ДУЧП) можно использовать для моделирования многих из наиболее фундаментальных физических процессов во Вселенной, вроде эволюции жидкостей или прохождении гравитационных волн сквозь пространство-время. Они появляются в ситуациях, когда будущее положение системы – например, состояние пруда через пять секунд после броска в него камня – зависит от вкладов двух или более факторов, типа вязкости и скорости воды.
Казалось бы, у сложных ДУЧП есть мало что общего с таким простым арифметическим вопросом, как гипотеза Коллатца.
Но Тао понял, что у них есть нечто общее. В ДУЧП можно подставить значения, получить другие значения, повторить процесс – и всё это для понимания будущего состояния системы. Для каждого заданного ДУЧП математикам нужно знать, приведут ли начальные значения на входе к бесконечным значениям на выходе, или же уравнения всегда будут выдавать конечные значения, вне зависимости от начальных.
Теренс Тао, вдохновлённый комментарием в своём блоге, достиг крупнейшего за десятилетия прогресса в изучении гипотезы Коллатца
Для Тао эта цель была того же порядка, как и то, всегда ли вы получите одно и то же значение (1) из процесса Коллатца, вне зависимости от начального значения. В результате он понял, что техники изучения ДУЧП могут подойти для изучения гипотезы Коллатца.
Одна особенно полезная техника использует статистический способ изучения долговременного поведения небольшого количества начальных значений (что-то типа небольшого количества начальных конфигураций воды в пруду) и экстраполирует результат на долгосрочное поведение всех возможных начальных конфигураций пруда.
В контексте гипотезы Коллатца представим, что мы начали с большой выборки чисел. Наша цель – изучить, как эти числа ведут себя, когда мы применяем к ним процесс Коллатца. Если почти 100% чисел в выборке приходят к 1 или очень близко к 1, можно заключить, что почти все числа будут вести себя так же.
Но чтобы это заключение было обоснованным, нужно очень тщательно составить выборку. Эта задача похожа на составление выборки участников голосования на выборах президента США. Для тщательного составления выборки из всей популяции нужно использовать взвешенные пропорции для республиканцев и демократов, мужчин и женщин, и так далее.
У чисел есть собственные «демографические» параметры. Нечётные и чётные числа, числа, делящиеся на 3, и числа, отличающиеся друг от друга ещё более хитрыми способами. Создав выборку чисел, можно сделать так, чтобы в неё входили определённые тип чисел, и не входили другие, по взвешенному принципу – и чем лучше вы выберете веса, тем точнее будут ваши умозаключения по поводу всех чисел в целом.
Взвешенный выбор
Задача Тао была гораздо сложнее, чем просто понять, как нужно создавать изначальную выборку чисел с нужными весами. На каждом шагу процесса Коллатца числа, с которыми вы работаете, меняются. Одно очевидное изменение состоит в том, что почти все числа из выборки уменьшаются.
Другое, возможно, менее очевидное изменение состоит в том, что числа могут начать скапливаться в группы. К примеру, можно начать с красивого равномерного распределения чисел от одного до миллиона. Но через пять итераций числа, скорее всего, сконцентрируются на нескольких небольших интервалах числовой прямой. Иначе говоря, можно начать с хорошей выборки, которая через пять шагов будет безнадёжно искажена.
«Обычно можно ожидать, что распределение после итерации будет полностью отличаться от начального», — сказал Тао. Однако ключевой его идеей было то, как можно создать выборку чисел, по большей части сохраняющих свои оригинальные веса в процессе Коллатца.
К примеру, начальная выборка Тао взвешена так, чтобы в ней не было чисел, делящихся на три, поскольку процесс Коллатца всё равно довольно быстро устраняет такие числа. Некоторые другие веса, выбранные Тао, оказываются сложнее. Он отдаёт предпочтение числам, остаток которых от деления на 3 составляет 1, и отходит от чисел, остаток которых от деления на 3 составляет 2.
В итоге выборка, с которой начинает Тао, сохраняет свой характер даже после начала процесса Коллатца.
«Он обнаружил способ продолжить этот процесс так, чтобы после нескольких шагов всё ещё было понятно, что происходит, — сказал Саундарараджан. – Когда я впервые увидел эту работу, я очень обрадовался и решил, что она потрясающая».
Тао использовал свою технику назначения весов, чтобы доказать, что почти все начальные значения – не менее 99% — в итоге приходят к величине, очень близкой к 1. Это позволило ему сделать вывод о том, Что 99% начальных значений, больших, чем квадриллион, в итоге приходят к величинам, меньшим 200.
Это, возможно, самый сильный результат в долгой истории этой гипотезы.
«Это великолепный прорыв в наших знаниях о том, что происходит с этой задачей, — сказал Лагариас. – Это определённо лучший результат за очень долгое время».
Метод Тао почти наверняка не способен добраться до полного доказательства гипотезы Коллатца. Причина в том, что его начальная выборка всё же немного искажается после каждого шага. Искажение будет минимальным, пока в выборке всё ещё содержатся множество разных значений, далёких от 1. Но в процессе Коллатца все числа в выборке начинают стремиться к одному, и небольшое искажение становится всё больше – так же, как небольшая ошибка в подсчётах результата голосования не имеет большого значения в случае крупной выборки, но сильно влияет на результат, когда выборка мала.
Любое доказательство полной гипотезы, скорее всего, будет основано на другом подходе. В итоге, работа Тао одновременно является и триумфом, и предостережением всем интересующимся: как только вам кажется, что вы загнали задачу в угол, она ускользает.
«К гипотезе Коллатца можно подобраться сколь угодно близко, но она всё равно остаётся недостижимой», — сказал Тао.
Комментарии (249)
rsashka
07.01.2020 11:03Особенно порадовало, что
Опытные математики советуют новичкам держаться подальше от гипотезы Коллатца.
А так как мы не опытные, да и не математики вовсе, то сейчас попробую накидать статью с потенциальным доказательством.
Но даже если я и ошибаюсь, все равно спасибо автору за утреннюю гимнастику для ума!
Очень интересная задачка.
Firsto
07.01.2020 15:30попробую накидать статью с потенциальным доказательством.
Вы всё равно делитесь результатами, даже если они не стоят отдельной публикации.)
tonad
08.01.2020 19:09-1По идее можно попробовать доказать что последовательность приводит к одной из степеней двойки. Понятия не имею только как это делается. Наверное это и есть первая ловушка в задаче…
ideological
07.01.2020 11:47-23Никогда не понимал одержимости математическими доказательствами и профита от них.
Вот в данном случае можно было написать скрипт на языке программирования и проверить на практике. Но математиков это не устроит, так как доказательства должны быть по местным понятиям.
mokhin-denis
07.01.2020 12:23+15А просто скрипт докажет (или опровергнет) гипотезу лишь на некотором конечном множестве, в частном случае. Это подходит там, где это множество конечно или можно от частного перейти к общему. В данном случае мы имеем дело с бесконечным множеством.
chapuza
07.01.2020 18:14+7докажет (или опровергнет) гипотезу лишь на некотором конечном множестве
Эм… Для опровержения достаточно множества мощности 1 :)
ProLimit
09.01.2020 11:21сорри, ошибся стрелочкой, хотел плюс поставить. Но отсутствие опровержения вполне очевидно — тогда бы эту задачу давно вычеркнули из списка нерешенных. И также можно предположить, что начало множества уже все перебрали, насколько позволяет современная вычислительная техник, так что «попробовать скриптом» не прокатит.
ideological
08.01.2020 00:40-3Ну а разве математики доказывают не путём индукции? Типа справедливо для x, x+1, x+2… то справедливо и для остальных целых чисел.
Fenzales
08.01.2020 00:54+3Типа справедливо для x, x+1, x+2… то справедливо и для остальных целых чисел.
Это не метод индукции, это не пойми что :) Нельзя просто взять конечный числовой ряд и назвать его доказательством.ideological
08.01.2020 09:59Ну как тут все уже поняли — я не математик.
Вот кстати на Хабре явно не хватает статьи с методами доказательств на простых примерах. И вообще, ИМХО математика нуждается в популязаторстве.
Конечно я понимаю что это невозможно, нет царских путей и всё такое :)
iago
08.01.2020 11:06Обычно это проходят на первом курсе любого технического ВУЗа, но если вы хотите понятным языком самые основы вышки — могу порекомендовать Дмитрия Письменного, он простым понятным языком изложил стандартный курс любого инженерного ВУЗа
forever_live
08.01.2020 19:57+2А разве не в школе?
iago
09.01.2020 16:03я уже не помню, давно это было :) но на 1 курсе это точно повторялось. Да, вы правы, в школе, как минимум в геометрии точно было четко расписано, что значит доказать теорему и что — опровергнуть доказательство например. А это 7 класс!
greatmelon
08.01.2020 22:22+1как бы это математическая индукция и есть. Докажите верность x(n+1) при условии что для xn утверждение гипотезы верно и будет вам всеобщее признание.
mayorovp
08.01.2020 10:08+2Гипотеза: все нечетные числа — простые. Доказывает физик:
3 — простое, 5 — простое, 7 — простое, 9 -ошибка эксперимента, 11 — простое, 13 — простое...
Это так что ли вы предлагаете делать? Нет, математики так никогда не делают.
ProLimit
09.01.2020 11:41Но если задача слишком сложная, а решить очень хочется — то делают :) Вот данная статья — пример. 1% оставили недоказанным. Если бы она имела практическое значение — это все еще много. Так что в чем смысл и радость от такого «физческого» доказательства, не очень понятно.
mayorovp
09.01.2020 11:43Во-первых, в обсуждаемом тут доказательстве гипотеза доказана для бесконечного множества чисел, а не для конечного.
Во-вторых, всё равно никто не делает финального заключения "то справедливо и для остальных целых чисел".
ProLimit
09.01.2020 11:58Конечно, разница с вашим примером огромная, но и это доказательство «верно для 99% чисел» противоречит духу чистой математики и больше подходит физикам, о чем я и написал.
ganqqwerty
07.01.2020 13:24+14Доказательство доказывает утверждение для абсолютно всех чисел — хоть для числа 5, хоть для сиксилиарда пипсиллионов. А скрипт — нет.
Goodkat
07.01.2020 16:37+8Скрипт тоже, но не сразу — просто подождите пупсилион лет.
red75prim
07.01.2020 17:51+5Это для конкретного большого числа. А для всех чисел — никогда, или, что то же самое, через бесконечное количество времени.
fshp
09.01.2020 02:49Достаточно на каждое следующее число тратить в 2 раза меньше времени на проверку. Тогда получим сходщийся ряд и проверим бесконечное множество за конечное время. Делов то.
red75prim
09.01.2020 07:11Ага. Так даже можно посчитать сумму ряда 1, -1, 1, -1, 1, -1,…
trapwalker
09.01.2020 11:40-1Это же элементарно=)
Складываем все единицы с минус единицами и получаем ноль.red75prim
09.01.2020 12:07Или переупорядочиваем 1, 1, -1, 1, 1, -1, 1, 1, -1,… складываем по 3 и получаем плюс бесконечность в пределе.
Впрочем, это я так — для разминки мозгов. Что получилось бы, если бы гипервычисления были реальностью.
fshp
09.01.2020 12:12Вы не можете переупорядочить элементы. Это уже другой ряд будет.
tmteam
09.01.2020 14:33-1При перемене мест слагаемых — сумма не меняется
fshp
09.01.2020 14:43Это справедливо лишь для абсолютно сходящихся рядов, коим ряд Гранди не является.
trapwalker
10.01.2020 10:25А там не просто перестановка, там именно что предпочтение одних членов последовательности другим. А лишние "-1" вообще " в конец" бесконечного ряда отправлены подождать своей очереди?
red75prim
10.01.2020 10:32Лишние? Мощности множеств единиц и минус единиц в обоих рядах одинаковы и равны алеф-ноль.
Там дело в том, что если определить сумму бесконечного ряда, как предельный переход, то у ряда Гранди никакой суммы не будет. И с таким определением суммы бесконечного ряда ряд уже нельзя рассматривать просто как множество чисел.
Поэтому — да, переупорядочивание, которое я использовал, не обязано давать ту же сумму. Но не потому, что там другое количество единиц и минус единиц. Это действительно просто перестановка.
fshp
09.01.2020 12:14Только по Чезаро сумма этого ряда равна 0.5.
trapwalker
09.01.2020 12:51Ну по Чезаро и сумма натуральных чисел = -1/12.
Вопрос-то стоял не в том, как ещё можно посчитать, а в том, чтобы вообще посчитать как-нибудь. Ведь на самом деле тут нет никакого «на самом деле».
Stas911
07.01.2020 19:03+2Зато может опровергнуть его и дело с концом
snizovtsev
07.01.2020 23:01+7Не с концом, а сразу появится десяток новых вопросов:
- А есть ещё?
- Если это конечный цикл, то есть ли без цикла (и наоборот)?
- Оценка числа таких чисел в промежутке;
- Алгоритмическая сложность получения последовательности таких чисел (если бесконечно);
- А в условии брать не четность, а другие модули;
- …
trapwalker
09.01.2020 11:42Мне кажется если про эту задачу по телеку скажут, то её даже запретить попытаются.
UPD.
Шутки шутками, а прикольно было бы жить в мире, где правительство попыталось бы законодательно запретить какую-то математическую задачу.
ideological
08.01.2020 01:42-4Это доказательство нужно даже если всё очевидно?
Скрипт докажет до определённого целого числа и этого может быть достаточно.
Murmurianez
08.01.2020 08:34А может и не быть — хрен его знает к чему потом эту теорему решат применить. От того что там в бесконечности может зависеть смысл жизни — вдруг 41 окажется после ваших скриптов? И что тогда делать?
MadBambula
08.01.2020 15:10+142
mayorovp
08.01.2020 10:10Если всё очевидно — значит, и доказательство придумать несложно. Так в чём проблема-то?
ideological
08.01.2020 11:12Ну потому что доказать нужно специфичным образом.
Вот например легко представить себе что резиновая сфера без разрезов может превратиться в квадрат или сжаться в точку, а в бублик трансформироваться не сможет. Это здравый смысл.
Но есть гипотеза Пуанкаре и её доказательство, важность которых я не оспариваю. Но хотелось бы понять их практическую значимость.
tundrawolf_kiba
08.01.2020 13:42Ну с фундаментальными науками — никогда не знаешь когда и что выстрелит, как то же электричество, открыли, а потом около 200 лет не знали нафига оно может пригодиться(ну разве что фокусы в цирке показывать). Так и тут — доказательство очередной математической теории может к примеру потребовать создания и исследования нового раздела математики, этот раздел лет через 50 к примеру придумают как применить для того, чтобы рассчитать и понять, что происходит в сингулярности черной дыры, и еще лет через 50 — варп-двигатели клепать не будет только ленивый.
mayorovp
08.01.2020 14:49+1Ну так конкретно для сферы, квадрата (т.е. куба?) и бублика это можно и без гипотезы Пуанкаре доказать.
Гипотеза Пуанкаре вам понадобится в тот момент, когда у вас окажется такое странное многообразие, для которого трансформация в сферу будет неочевидной.
lany
08.01.2020 10:41Как правило, полное доказательство таких гипотез даёт попутный субпродукт — новую разработанную методологию решения математических задач. Она позволит атаковать другие проблемы, которые вполне могут иметь практическую ценность, даже если от самой изначальной гипотезы пользу нет. В математике никогда заранее точно не знаешь, где появится полезное знание, но практика показывает, что это происходит весьма часто. Поэтому надо продолжать копать.
bogolt
08.01.2020 22:08Скрипт увы никак не может.
Доказать нельзя потому что проверить все числа невозможно.
Опровергнуть тоже нельзя — потому что для опровержения даже для одного числа нужно выполнить бесконечное число операций.
Предположим вы нашли число 5**9999 и за первый миллион операций оно не пришло к 1. Может ли скрипт понять что оно никогда к нему не придет?
mafia8
08.01.2020 23:34Можно посмотреть соседние числа, за сколько операций они доходят до единицы.
Посмотреть, как зависит число операций от числа.
Mad__Max
09.01.2020 21:49Кроме расходящейся бесконечности возможно попадание в замкнутый конечный цикл. И его обнаружить легко.
bogolt
09.01.2020 21:56легко если хватит памяти чтобы запомнить все элементы последовательности. А если нет?
ZuOverture
10.01.2020 00:30Только начальный, для сравнения с очередным сгенерированным. Остальные-то зачем хранить при наличии однозначных правил генерации?
bogolt
10.01.2020 00:53зациклиться же можно в любой момент и не дойдя до начального числа. Как узнаем об этом не храня их все?
Mad__Max
10.01.2020 01:07Узнаем когда дойдем при проверке уже до числа с которого начинается этот цикл. Это в худшем случае — если промежуточные значения вообще не храним и сравниваем только с начальным.
ZuOverture
10.01.2020 17:44Насколько я понял, есть хорошая аппроксимация числа шагов до схождения от величины исходного числа. Если проверяемое число сходится существенно дольше ожидаемого, то можно для него отдельно запускать проверку на попадание в цикл с хранением промежуточных. Ниже был вариант как это сделать хоть и за большое время (но не более удвоенной длины цикла), зато с хранением всего лишь двух значений. В крайнем случае (бесконечное расхождение) этот метод позволяет наложить ограничение снизу на длину цикла.
Mad__Max
10.01.2020 01:27Нехватка памяти проблемой быть не должна. Может быть проблема с переполнением разрядности переменных используемых для рассчета — это относится к случаю доказательства (невозможности) ухода ряда на бесконечность чисто численными методами.
На практике ряд либо получится убывающим и сводящимся к единице — как все проверенные до сих пор.
Либо возрастающим и стремящимся к бесконечности — тут проблемой станет быстрое переполнение (слишком большие числа)
Либо неубывающим и не возрастающим, а петляющим в диапазоне чисел не намного выше исходного числа, но тогда должен достаточно быстро попасть на повтор одного из чисел в последовательности и тем самым уход в замкнутый цикл.
Можно конечно чисто теоретически представить неубывающий и не возрастающий ряд, но при этом не имеющий ни одного повтора на длинне выборки в миллионы или даже миллиарды чисел в ряду (все уникальные) которые возможно сохранить в памяти. Но на практике все проверенное сворачивается к единице на тысячах итераций максимум.
И обнаружение любого числа выбивающегося из этого правила само по себе станет открытием. Было бы интересно получить число из которого простой формулой (как в этой гипотезе) можно получить ряд в миллионы неповторяющихся псевдослучайных чисел при этом без выраженой тенденции к их росту.
khim
07.01.2020 17:03+5Если бы вы удосужились прочитать-таки статью, то выяснили бы, что гипотеза проверена для всех «малых» чисел — до квинтиллионов. То есть скрипт-то давно накидали… Вот только он всё равно для всех чисел ничего доказать не сможет…
stalinets
07.01.2020 21:35Помню, лет 9-10 назад несколько месяцев участвовал в распределённых вычислениях, считая видеокартой именно гипотезу Коллатца. А потом появился биткоин, и задача у видеокарты поменялась.
beduin747
07.01.2020 12:31+2Наркота для математиков? =)
Biga
08.01.2020 00:08+4У нас было три построения теории вещественных чисел, 75 пределов последовательностей, два определения предела функции по Коши и по Гейне, комплексные числа, О-символика, наполненная эквивалентными функциями, и целое море различных непрерывностей и равномерностей всех сортов и расцветок, а также запись лекций Теляковского, производные, точки разрыва первого и второго рода и задачник Демидовича. Не то, чтобы это был необходимый запас для подготовки, но раз уж начал готовиться к коллоквиуму, становится трудно остановиться. Единственное, что вызывало у меня опасение — это производные. Ничто в мире не бывает более беспомощным, безответственным и порочным, чем дифференциальные зомби. Я знал, что рано или поздно мы перейдём и на эту дрянь.
Rasato
07.01.2020 12:44+7То есть наткнемся ли мы при бесконечном повторении на какую-либо степень двойки?
ganqqwerty
07.01.2020 13:29Я не понял про конфигурацию воды в пруду.
Biga
08.01.2020 00:50+1Форму поверхности воды можно описать функцией: высота воды от x и y (или от радиальных координат). Законы физики, относящиеся к движению воды можно описать дифференциальным уравнением (например, см. «уравнения мелкой воды»). И тогда первая функция (описывающая поверхность воды) получается как решение этого дифференциального уравнения.
Фишка дифференциальных уравнений в том, что изменение системы целиком и полностью зависит от текущего состояния системы (и граничных условий). Если посмотреть на это с точки зрения дискретных вычислений, то это означает, что каждое следующее состояние вычисляется через предыдущее.
Возьмём простейший пример дифференциального уравнения: x' = k*x, то есть скорость линейно зависит от положения. Если x0 = 1, то x' = k, значит следующее положение объекта будет x1 = x0 + k * dt. И так далее. При более сложном законе будет более сложная формула. Получается этакая последовательность вычислений, похожая на задачу из топика.
Дискретные вычисления для дифференциальных уравнений очень широко применяются в моделировании физических процессов. И там очень важным вопросом является сходимость. Поэтому для определения параметров сходимости разработано огромное множество методик, одну из которых, по всей видимости, и применил Тао.
SteelRat1
07.01.2020 13:59Я правильно понял: раз к единице приводят числа, которые являются степенями двойки, то теория сводится к тому, что существует или не существует некое число, после которого оно, умноженное на 3 и увеличенное на единицу уже никогда не станет числом, которое можно представить как степень двойки?
ZuOverture
07.01.2020 16:12+4Операция 3x+1 над нечетным числом делает число четным, т.е. добавляет делитель 2, который тут же уничтожается операцией x/2. Вопрос в том, каковы оставшиеся новые делители — на своем обывательском уровне не рискну делать никаких предположений по этому поводу, но очевидно меняются радикально. Чем-то похоже на поведение линейного конгруэнтного генератора случайных чисел, где операции над числами тоже крайне простые, а результаты выглядят как хаос.
arheops
07.01.2020 20:38Задача просто хитро сформулирована.
На самом деле, там два действия
1) если четное, то разделить на два 2) если нечетное, то (3x+1)/2. И тут уже очевидность схлопывается, поскольку нельзя ничего сказать о новых делителях этого числа.
ivanrt
07.01.2020 15:03Нужно просто перенумеровать все числа с учётом их расстояния до 1 по этому закону. :)
Sap_ru
07.01.2020 20:24+1Мне кажется, что сейчас минимум пара десятков человек бросилась к компьютеру.
А потом классифицировать и найти закономерность.
gecube
08.01.2020 13:58Ага. Пойти от обратного. Ответить на вопрос — какие числа дают в результате применения этих правил за один шаг числа из множества 1...10 (1...100, 1...1000). Посмотреть. Есть ли дырки. И попробовать растянуть выводы на все множество чисел )
vassabi
07.01.2020 15:17+3давым-давно (еще в прошлом столетии!), студентом катался на юга электричками — до сих пор лежит тетрадка с размышлениями по этой гипотезе в нескольких системах счисления (умножение на 3 и деление на 2 удобнее не в десятичной), которую исписал за это время…
Эхх… видно пришла пора её уже выкидывать :) — чистой математикой я не занимался уже лет 10.
shm-vadim
07.01.2020 15:32У меня такое предположение, например:
Пусть n — любое нечетное натуральное число (четные рассматривать смысла нет), тогда с вероятностью 1/2 после первого и второго действия над ним мы получим 1,5n+0,5, т.е. увеличение чуть более, чем на 50%. С вероятностью 1/4 мы после двух действий еще сможем разделить на 2, т.е. мы получим 0,75n+0,25 — уже уменьшение примерно на 25%. С вероятностью 1/8 мы сможем еще разделить на 2 и т.д. В этом отношении мне кажется, что подсчитав полную вероятность мы получим, что до того момента, как число снова станет нечетным, оно уменьшится относительно изначального n. Но у меня не хватает аппарата это подсчитать.
Если же мое предположение о большей вероятности понижения верно, тогда с удлинением последовательности число будет все уменьшаться до минимального натурального, т.е. до 1.
hahenty
07.01.2020 15:56+1Полная вероятность (того, что мы наткнёмся на степень двойки,) стремится к единице.
1/2 + 1/4 + 1/8 +… + 1/2^x
Какую ещё вероятность поищем?shm-vadim
07.01.2020 16:54Я немного о другом говорил. В моем предположении произвольное нечетное число до попадания в другое нечетное с вероятностью 1/2 увеличивается округленно на 50%, а с вероятностью 1/2 уменьшается, но я так сразу не могу подсчитать на сколько. В этом и весь мой вопрос. Т.к. если оно уменьшается быстрее, чем увеличивается, то рано или поздно мы придем к единице.
Впрочем, получается, я сделал еще одно допущение в том, что 3n+1 — вполне обычное четное число, с вероятностью 1/2 делящееся на 4, 1/4 — на 8, 1/8 — на 16 и т.д. С этим, возможно, тоже надо разбираться.ShadowTheAge
07.01.2020 21:29+1Такое наблюдение позволяет понять почему «возможно» «большинство» чисел становятся в итоге 1
при этом «возможно» здесь потому что только первая такая операция действительно «случайна», а «случайность» последюущих уже вызывает вопросы
а «большинство» здесь потому что даже маленькая вероятность чего-либо не гарантирует отсутствие таких чисел (к примеру если наивно посчитать вероятность того что число будет простым, то кажется как будто они должны будут кончиться)
Вот в этих то «возможно» и «большинство» и загвоздкаshm-vadim
07.01.2020 21:37По мне как раз этот алгоритм должен быть универсален, поскольку мы все время движемся от одного нечетного числа к другому и при этом все время его понижаем. При этом каждое следующее нечетное число будет соответствовать тем же условиям, что и предыдущее, т.е. вероятность всегда будет указывать на дальнейшее понижение.
Можно и по-другому сказать. Если вы с вероятностью 50% делаете шаг назад и с вероятностью 50% делаете 2 шага вперед, то рано или поздно вы достигнете указанную впереди точку, как бы далеко она от вас не была. По-моему, это можно считать доказательством. Осталось только реально эти вероятности посчитать. :)lagranzh
08.01.2020 01:06-1вроде уже выше написали, но я повторюсь.
А. Вероятностное док-во тут не подходит. Так вы можете доказать что «почти все» числа сходятся к 1. А надо доказать что все.
Б. Вероятность 0 не значит что событие не возможно.
Ц. Если я правильно помню, униформного распределения не существует на множествах меньше чем алеф один.
ShadowTheAge
08.01.2020 01:14Рассмотрим вырожденный пример
Если мы попали в число, которое является степенью двойки, умножим на два. А если не является — уменьшим сразу до 1. Все ли числа уменьшатся до 1 в итоге?
Какая вероятность того что большое число N является степенью двойки? Очень маленькая. И если является, то умножив его на 2 получим еще большее число, которое будет с еще меньшим шансом являться степенью двойки, так?
Не так. Потому что тот факт то что число является степенью двойки изменяет вероятности. И если мы умножим степень двойки на 2, то шанс получить степень двойки оказывается вовсе не случайным событием.
Поэтому то, что «каждое следующее нечетное число будет соответствовать тем же условиям, что и предыдущее» не является фактом и это нужно доказывать. (Кроме того, это еще и не является правдой, судя по всему, только перекос наоборот, в сторону уменьшения)
ivanrt
09.01.2020 17:05Попробуй с числом 27 ;)
Я тоже рассматривал по вероятностям, что по идее должно довольно быстро сходиться, но тут получается что оно 41 раз растёт и доходит до >9k
Может исключения из правила очень маловероятны, но есть? ;)
panteleymonov
09.01.2020 17:15Да забавно.
2727 (11011) 41 (100101) 31 (11111) 47 (111101) 71 (1110001) 107 (1101011) 161 (10000101) 121 (1001111) 91 (1101101) 137 (10010001) 103 (1110011) 155 (11011001) 233 (10010111) 175 (11110101) 263 (111000001) 395 (110100011) 593 (1000101001) 445 (101111011) 167 (11100101) 251 (11011111) 377 (100111101) 283 (110110001) 425 (100101011) 319 (111111001) 479 (111110111) 719 (1111001101) 1079 (11101100001) 1619 (11001010011) 2429 (101111101001) 911 (1111000111) 1367 (11101010101) 2051 (110000000001) 3077 (101000000011) 577 (1000001001) 433 (100011011) 325 (101000101) 61 (101111) 23 (11101) 35 (110001) 53 (101011) 5 (101) 1 (1)unC0Rr
09.01.2020 17:33В плане сравнения любопытны 31 и 63, у них совпадение идёт уже с седьмого члена последовательности: 31,47,71,107,161,121,91,… и 63,95,143,215,323,485,91,…
panteleymonov
09.01.2020 17:41Вот в отдельной ветке обсуждения на этом я и построил свои доказательства. Начиная с отсечения четных (k*2), за тем всех k*4+1, затем k*8+3 и тд. остаются только число (да да это одно число) 2^n-1, при n стремящейся к бесконечности.
panteleymonov
09.01.2020 21:24Я могу узнать по бинарному коду числа сколько у него будет итераций (3*n+1)/2 до получения четного. у 27 (11011) два. У 31(11111) пять и тд. Все зависит от количества подряд идущих младших единичных бит. В моих примерах выше последовательность бит перевернута.
dzsysop
09.01.2020 22:08Если вы это можете доказать математически, то думаю это и будет решение.
panteleymonov
10.01.2020 00:27А это из предыдущего комментария следует. И тут нечего доказывать — это просто оптимизация алгоритма вычисления последовательности на несколько шагов вперед. Все k*8+1 — числа которые решаются (3*n+1)/4 и дают нечетное. В бинарном виде это числа nnnnnn001.
Далее k*16+13 только для (3*n+1)/8 дают нечетное (nnnnn1101)
k*32+5 для (3*n+1)/16 (nnnn00101)
k*64+53 для (3*n+1)/32 (nnnn110101)
k*128+21 для (3*n+1)/64 (nnnn0010101)
…
Результат числа n у которого k первых единичных бит можно считать вот по такой формуле.
(3^k*n+3^(k-1)+3^(k-2)*2+… +3^(k-k)*2^(k-1))/2^(k)
Например 39 (100111) имеет 3 итерации результат 134 (10000110)
(3^3*n+3^2+3^1*2+2^2)/2^3 = (27*39+9+6+4)/8 = 1072/8 = 134
Можно считать по упрощенной формуле
6*(3^k-1)*n+6*3^(k-2)+..+6*3^(-1)
Где n — число без первых единичных бит и нуля, для 39 это 2 (10)0111.
6*(9)*2+6*3^(1)+6*3^(0)+6*3^(-1)
(54*2 + 18 + 6 + 2) = 134 (10000110)
edo1h
10.01.2020 05:06Я могу узнать по бинарному коду числа сколько у него будет итераций (3*n+1)/2 до получения четного
и что это даёт? ну да, с 27 через 2 итерации будет падение, но что будет после этого падения же заранее неизвестно — может быть очередной рост, и т.д.
panteleymonov
10.01.2020 05:37Определение зависимости насколько падает и поднимается без итерирования по значению самого числа думаю что то всетаки даст, если дальше копаться. Например числа с чередующимися 01 дают большое падение. Остается только посчитать сколько из них с чередующимися и повторяющимися единицами строиться.
Ну, а если начать с того что я начал, то часть чисел просто убирается из проверки. Из всего числового ряда остается немного — то что требуется действительно проверять.
Например такие числа как 911 дают большой подъем и падение до 577. А другие с 4 итерациями дают только подъем. 35 такое же число, если определить характер этих чисел, то можно по одной формуле вычислить ряд который ведет заведомо к 1.michael_vostrikov
10.01.2020 08:49Например числа с чередующимися 01 дают большое падение.
Это потому что умножение на 310=112, получаются все 1, и потом еще плюс 1.
michael_vostrikov
10.01.2020 09:02Например числа с чередующимися 01 дают большое падение.
Это потому что умножение на 310=112, получаются все 1, и потом еще плюс 1.
muhaa
07.01.2020 16:07Не сильно в этом разбираюсь, но по мои ощущениям подобные задачи сводятся к вопросу о возможности некой заданной недетерминированной МТ (работа которой продемонстрирована на гифке в статье) породить вообще любую последовательность. Т.е. в вопросу об «универсальности» или ограниченности воможностей заданной недетерминированной МТ. Не знаю что об этом говорит математика.
BkmzSpb
07.01.2020 17:43+7В прикрепленном видео довольно любопытный график показан. Интересно посмотреть на аналогичный график в логарифмическом масштабе, например
log2. Для достаточно больших чисел (x >> 1) операция3x + 1в логарифмическом масштабе "практически" экивалентна сдвигу наlog2(3) = 1.58, а операция деления на2— сдвигу на-1.
Log-plot для числа 129
BkmzSpb
07.01.2020 18:34В конце я естественно напсал глупость — отношение количества увеличений к количеству уменьшений должно быть меньше 0.63.
vics001
07.01.2020 23:17А можно такой график для хотя бы 1-10 млн первых чисел
BkmzSpb
08.01.2020 14:06Ну естественно можно, они а) наверное где-то существуют уже, б) для числа 107 я не берусь предсказать, насколько последовательность может вырасти. Соответственно, вычисление одного числа в диапазоне "миллионов" может занимать продолжительное время, а построение последовательностей для нескольких миллионов чисел может оказаться задачей непростой.
В любом случае, эти графики я построил в
Rбуквально используя пару однострочных неоптимизрованных методов иggplot2. Приложив чуть больше усилий к коду, можно я думаю собрать приличную статистику и на домашнем ПК/лэптопе.
iago
08.01.2020 11:11меня всегда пугает, когда математики пишут слово 'очевидно". Обычно это означает, что рядовому инженеру это будет максимально неочевидно
BkmzSpb
08.01.2020 14:13+1Я не согласен. Хоть и существуют книжки и даже анекдоты о том, что самые сложные доказательства всегда скрываются за "очевидно" и "не трудно показать", в большинстве случаев это не так. Да и "рядовой инженер" умеет обращаться с числами.
Касательно моего примера: под "очевидно" я понимаю, что если число увеличивается на 4 единицы, а уменьшается на 2, то если на каждое увеличение (+4) будет приходиться два уменьшения (2 x -2 = -4), конечное значение будет несильно отличаться от исходного сколько бы итераций вы не выполнили бы, и для сохранения этого баланса отношение числа увеличений (1n) к числу уменьшений (2n) должно быть 1n / 2n = 0.5. Если больше — последовательность уйдет на бесконечность, меньше — в 0.
iago
08.01.2020 15:33+1Спасибо за развернутый комментарий (только не в 0 а в 1 в нашем примере), это просто был сарказм. Как в этих мемах
Мемы
BkmzSpb
08.01.2020 16:08В 0 в логарифмической шкале, т.к. цель это единица, а log2(1) = 0 (как и вообще любой логарифм единицы). Это можно увидеть на рисунке 1, в конце последовательности.
Мемы мемами, но при определенной сноровке во многих формулах угадываются стандартные "паттерны" и их комбинации, из-за чего даже гигантское уравнение из "своей" области если и не оказажется сходу очевидным, то хотя бы даст представление о том, что же оно описывает. Но это работает далеко не всегда :)
ЗанудствоХотя в вашем же первом меме просто очень неудачное обозначение. Без знания конкретных операций можно увидеть, что оператор
[., .]антикоммутативен, т.е.[x, y] = -[y, x]. Далее видно, что[x, y] = x * y - y * x, и*очевидно некоммутативно. Дальше просто раскрываете все кадратные скобки используя установленные нами свойства, что-то должно сократиться, видимо*ассоциативно, поэтому группируете обратно, вынося за скобки — вот и результат. При этом мы абсолютно не представляем, что это за операторы/опрации, и что такое множествоD(A), но т.к. они подчиняются общим правилам, мы можем доказать верность утверждения.
trapwalker
09.01.2020 12:02+1А что получается, если гипотеза не верна, то есть некое самое первое число С (назовём его числом Коллатца). Это число не сводится операциями к 1.
Очевидно, что оно нечетно, иначе оно не было бы первым. Оно либо формирует цикл, либо открывает собой некоторую цепочку, бесконечную или где-то тоже зацикленную.
Задача сводится к доказательству несуществования такого числа.
Интересно глянуть какими оптмизированными алгоритмами перебирают эту программно.
neurocore
07.01.2020 17:46-3Самый простой способ войти в историю — накидать скрипт, который берёт огромное случайное число и запускает процесс Коллатца в попытке найти цикл не проходящий через единицу. Тогда вся гипотеза будет опровергнута.
ZuOverture
07.01.2020 17:58+1BOINC@Home этим уже развлекались. Заказчики математики, при вычислениях использовали оптимизации. Величина аудитории, предоставляющей свои компы для вычислений, огромная. Так что способ не такой уж простой.
Mad__Max
07.01.2020 19:42+1Он не простой в том смысле, что проверка верности гипотезы на любом сколько угодно большом множестве чисел не будет принята в качестве «настоящего» доказательства.
Хотя практически ее можно считать доказанной уже сейчас. Но практического применения насколько знаю у нее и нет никакого. А с точки зрения «чистой математики» нужно такое же чистое доказательство в общем виде, а не в частных случаях.
Но она простая в том смысле что первое же найденное исключение (и тут перебор на компах вполне подходит) опровергнет теорему и закроет вопрос.ZuOverture
07.01.2020 23:38+2Нет, он не простой в том смысле, что в силу вероятностного характера такого угадывания в историю вы скорее всего не войдёте, как не вошли 65+ тысяч человек занимавшихся этим ранее.
valergrad
08.01.2020 03:29+2Это настолько же осмысленно, как пытаться отсортировать колоду из 52 карт путем случайного перемешивания.
Скорее всего даже менее осмысленно — карты все же когда-нибудь отсортируются, а вот здесь, вероятно, число не найдется никогда.Mad__Max
08.01.2020 19:39Какое случайное перемешивание? Числа же не из генератора случайных чисел берутся, а последовательно в порядке возрастания проверяются. Одно число проверяется ровно один раз.
vassabi
08.01.2020 01:55+1«цикл, не проходящий через единицу» — это только один из вариантов. Там же еще может быть быть (по крайней мере ЕМНИП это не опровергнуто) и расходящаяся бесконечность. Её-то скриптом не найдешь!
Mad__Max
08.01.2020 19:43Почему не найдешь? Найдешь сразу же по переполнению. Вот доказать что последовательность именно бесконечная (а не просто на много-много порядков вверх уходит от исходного числа прежде чем снова свернуться к единице) численным методом не получится.
Но такое выявленное «аномальное» число можно уже отдать математикам, чтобы они проверили анализ — а что в этом числе такого необычного(например разложить на множители для начала), что оно приводит к такому результату? И попробовать уже аналитически доказать, что последовательность получится именно расходящейся бесконечностью если начать с этого конкретного числа.trapwalker
10.01.2020 10:23Дело в том, что числа могут оказаться очень и очень большими. Также очень большим может оказаться и длинна цепочки. Ну в смысле, что может быть мы и не встретим «аномально» большой цепочки, а просто будем встречать цепочки всё длиннее и длиннее и каждый раз не будем наверняка знать бесконечная она или нет.
Вообще задача не бесполезная. Наверняка там по пути кучу всего изобрести удастся. От всяких оптимизаций до фрактальных каких-нибудь закономерностей полезных.
Вон от множества Мандельброта или от шума Перлина какая польза? А она есть!Mad__Max
11.01.2020 01:43Цепочки то могут быть очень длинными, но чем больше длина цепочки тем выше вероятность, что хотя бы один член ряда в ней повторяется. А единственный повтор нам сразу дает обнаружение замкнутого цикла и опровержение гипотезы.
Исключение — относительно монотонно возрастающие ряды в которых вероятность встретить повтор не растет от длины.
Но в таких рядах(при их наличии) мы в первую очередь не с не хваткой объема памяти для хранения членов ряда столкнемся, а с переполнением разрядности используемых вычислений — быстро появляются слишком большие (длинные) числа не умещающиеся даже в «длинную арифметику».
Тут конечно доказать что такой найденный ряд будет и дальше бесконечно возрастать численными методами не получится — с этим я и не спорил.
sebres
08.01.2020 03:12Дело в том что опровергнуть как раз и не получится, т.к. для этого нужно продолжать цикл бесконечно (просто потому что и числа в неравенстве
fi(x) != 2nмогут расти бесконечно)…
Умолчим про то, что уже какая-нибудь растущая итерация на числах близких к каким то 10108 (что все-еще меньше Гуголплекса, но уже много раз больше чем Гугол), не говоря уже про то чтобы подобраться к следующей границе 2n+1 (если даже 2n не полностью «покрыта»), уже тупо не хватит всех вычислительных ресурсов земли.
Чтобы было представление о чем это вообще — вот тут на коленке «собранный» простейший вычислитель-итератор на питоне, а вот простые примеры:
>>> fci(7) reached 16 == 2**4 after 12 iter(s), max: 52 >>> fci(27) reached 16 == 2**4 after 107 iter(s), max: 9232 >>> fci(2**32-1) reached 16 == 2**4 after 447 iter(s), max: 3706040377703680 >>> fci(2**64-1) reached 16 == 2**4 after 859 iter(s), max: 6867367640585024969315698178560 >>> fci(2**64+1) reached 16 == 2**4 after 479 iter(s), max: 55340232221128654852 >>> fci(2**(10**4)-1) reached 16 == 2**4 after 134400 iter(s), max: 3e4771 (тут как бы 4,5 тысячи нулей) >>> fci(2**(10**5)-1) reached 16 == 2**4 after 1344922 iter(s), max: 2e47712 (тут как бы 45 тысяч нулей)
Особенно предлагаю обратить внимание на последние два результата.
2**(10**8)-1в один поток, да на питоне (да хоть и на C с самой быстрой «длинной» математикой, оптимизированной под алгоритм), можно даже не пробовать…
И я вас уверяю, это всё еще будет не бесконечный цикл. :)chapuza
08.01.2020 07:19Чтобы опровергнуть эту гипотезу, достаточно найти число, которое после некоторого количества итераций превращается в самое себя.
sebres
08.01.2020 07:25Достаточно?!
Т.е. построить lookup таблицу (граф, radix-/patricia-trie, whatever) для бесконечного множества огромных чисел и/или итераций (чтобы собственно найти «самое себя»)?
А памяти хватит? :)chapuza
08.01.2020 07:28Простите, я не понимаю, о чем вы.
Представьте себе, что мне приснилось некое число, скажем первые стопиццот знаков ?, — которое после трех делений на два и умножений на три предыдущего натурального числа превращается в самое себя. Цикл замкнулся, гипотеза опровергнута.
sebres
08.01.2020 07:35Только вот ни «начальное» число, ни собственно «некоторое количество итераций» (т.е. расстояние от начального числа, до превращение его в «самое себя») не известны.
Вывод — на каждой итерации снизу вверх запоминать, а сверху вниз сравнивать.
Что в худшем случае выливается в сравнивать всех со всеми.
Повторюсь, памяти хватит?
А магию типа «приснилось число» и бац на 3-й итераций оно снова «тоже самое» оставьте для пикабу, плз.chapuza
08.01.2020 07:40-1Дело в том что опровергнуть как раз и не получится, т.к. для этого нужно продолжать цикл бесконечно (просто потому что и числа в неравенстве fi(x) != 2n могут расти бесконечно)…
Вот это ваше утверждение — чушь. Никакой цикл никуда бесконечно продолжать не нужно. Так понятнее?
оставьте для пикабу
Обязательно, вот только шнурки выглажу.
sebres
08.01.2020 07:57Если у вас есть единственный замкнутый цикл
1 -> 4 -> 2 -> 1в самом начале (внезапно потому что тут есть «магическое» число1, то это совсем не означает, что какая-то другая последовательность тоже замкнется.
Посмотрите на картинки типа «Iteration (stopping) time for inputs» или веер (треугольник) распределения…
Т.е. расти оно будет всегда (бесконечно или нет, не доказано).
Но что оно замкнется — это нонсенс. Что-то из оперы «А пацаны то не знали».
Так понятнее?chapuza
08.01.2020 08:11-1Ладно, попробую в последний раз.
Рассмотрим вырожденный пример. Гипотеза: «не существует целого числа, в котором после гуголплекса нулей идет гуголплекс единиц». Ни один существующий в мире компьютер не справится решить эту задачу перебором. Тем не менее, очевидно, такое число существует, и не одно. QED.
В математике для опровержения гипотезы достаточно привести один пример. Вы утверждали, что для этого нужно продолжать какой-то цикл бесконечно. Это — неверно.
Предположите, умозрительно, что такое число, замыкающееся в цикл после сравнительно невеликого числа итераций существует. Далее предположите, что некий Васяо решил пособить Тао и наугад проверяет числа в районе Гуголплекса. И через день натыкается на такое число. Вероятность этого события, хоть и чрезвычайно мала, но отлична от нуля. Наткнуться на такое число, чтобы опровергнуть гипотезу, нужно ровно один раз.
А не «нонсенс» и «пацаны» — это вам надо бы на пикабу. Скриптики — это круто, но к математике имеет очень опосредованное отношение.
sebres
08.01.2020 16:01Вы работу то хоть смотрели? Там черным по белому «almost all positive
integers do not lie in a periodic Collatz orbit».
А теперь забудем слово «почти» и всякие вероятностные «logarithmic density» и т.д.
Если (невероятно, но вдруг) какая-то замкнутая последовательность и существует, то минимальная длинна такой цепочки (цикла) будет не сильно отличатся от среднего числа итераций до первого спуска, что практически то же AVG значение до первой найденой степени двух (без учета вырожденных случаев, ака начинаем сразу с 2n).
А это даже для «небольших» чисел (21000, 22000, 24000, ..., 210000) очень длинные цепочки (1K, 10K, 20K, ..., 60K) и рост там очевиден.
Предположите, умозрительно, что такое число, замыкающееся в цикл после сравнительно невеликого числа итераций существует.
Предпологать не надо. Надо анализировать (ну или читать что Tao, Korec и др. про то уже написали).
Васяо решил пособить Тао и наугад проверяет числа в районе Гуголплекса.
Поперхнулся. What?!
Вы хоть раз пробовали умножить что-то в районе Гуголплекса (а это на минуточку 1010100, т.е. число с гугол нулями) хоть даже на 3?
Что-то мне говорит что на это не хватит памяти не то что у вас… Смею предположить, что ее врядли хватит у всех компьютеров человечества и всей известной вселенной, даже если размер бита будет равен размеру атома.
(в видимой части Вселенной порядка 1080 атомов, чтобы записать 1 Гуголплекс вам же нужно порядка 3.3*1099 бит).
Я надеюсь стало чуть понятней почему по моему скромному мнению слово «достаточно» тут не совсем подходит.
unC0Rr
08.01.2020 17:19Нет необходимости запоминать все числа последовательности, чтобы выявить в ней циклы, достаточно идти по ней двумя итераторами, но на одном из них делать шаг в два раза реже. При наличии цикла значения итераторов в какой-то момент времени обязательно совпадут.
sebres
08.01.2020 21:15А черепахозайцем (т.е. сознательно увеличивая количество вычислений в два раза), да на длинной арифметике будет не выгодно совсем. Даже если проверку делать только при двойном спуске, т.е. когда одна итерация по условию когда x из нижеследующего после второго деления гарантированно меньше предыдущего x:
x = 3*x+1 / 2; while not (x & 1) { x = x2 / 2; compare(xhare, xtort) }; repeat
Т.е. только на гарантированном спуске(3*xi+1 / 4 < xi).
Floyd уместен когда сравниваются «готовые» элементы списка, а не когда они будут вычисляться на каждой итерации (т.е. не там где операция вычисления станет дороже операции сравнения).
Кроме того, пока что нет даже подозрения, что какое-то число «влетает» в бесконечный цикл — он пока у всех всегда заканчивался ожидаемо 2n (что есть начало спуска до 1) за какое-то (да иногда долгое, иногда очень, но) конечное время.Mad__Max
09.01.2020 21:57-1На практике по-моему использует простой счетчик делающий +1 на каждой итерации. И если число не сворачивается к уже проверенному множеству за n итераций (и сотни достаточно), то проверять это число отдельно на предмет наличия замкнутого цикла в последовательности. Это будет крайне малая доля от общего количества проверяемых чисел.
А не в основном цикле перебора следить за отсутствием повторяемости в последовательности.sebres
10.01.2020 18:42В «основном цикле» проверяется число 24K-1.
Это число имеет последовательность, в которой допустим до 280 подъемов и спусков, и при этом «бегает» по числам в интервале (22K..24.5K) пока в конце не достигнет уже проверенную группу до 260 или (ожидаемо) гарантированный спуск на каком-то 2N.
При том что хранить все «проверенные» числа вы не хотите, единственная возможность это отсекать интервал (22K..24K-2), последовательно перебирая числа в «основном цикле».
Кроме того если вы посмотрите эту ветку комментариев выше, то возможно заметите что речь тут идет про какое-то «приснившееся» число (т.е. «случайное», для которого числа и менее его могут быть еще не «проверены»).
Вопрос: которое «множество» считать «проверенным», откуда у вас тут «сотня» когда там много-много порядков больше, а главное когда (на каком спуске/подъеме) запускать и главное останавливать того зайца Флойда?
Ну и напомню, что число может забираться сильно вверх, а диапазон (24K..24,5K) у вас не проверен по умолчанию, т.е. вопрос №2: почему вы исключаете что тот «теоретический» замкнутый цикл (aka periodic orbit) не находится где-то в этой области?
edo1h
08.01.2020 13:59так в статье же уже написано, что проверили достаточно много чисел — и подобного не нашли
justhabrauser
07.01.2020 18:26Интересно — сколько тактов CPU уйдет на одну итерацию?
Если использовать ассемблер x86-64 и оперировать в пределах 64 бит.
(могу предположить что порядка 6..10)
Dima_Sharihin
07.01.2020 19:20Если использовать ассемблер x86-64 и оперировать в пределах 64 бит.
Так в этих пределах уже все посчитано, а длинная арифметика медленная ну вообще везде
justhabrauser
07.01.2020 19:30Если верить википедии, то не всё.
Даже вы этих пределах.
PS. у меня пока получилось порядка 30 тактов на итерацию; на C быстренько набросал.
Mad__Max
07.01.2020 19:50+1Вики говорит что уже проверены числа вплоть до 1 152 921 504 606 846 976 по состоянию на конец 2019 года.
Это 2 в 60 степени. Т.е. до пределов быстрой 64 бит арифметики еще довольно далеко — на порядок дальше чем уже успели перебрать.red75prim
07.01.2020 20:19+2Промежуточные результаты могут выходить за пределы 64-х бит
Mad__Max
07.01.2020 22:49Точно, последовательность же может и вверх довольно долго идти перед схождением к 1.
И как раз такие последовательности в первую очередь и интересны и требуют проверки.
Правда большая часть все же почти сразу идет вниз и поэтому по-идее можно продолжать считать на аппаратных 64 бит и только в случае переполнения подключать длинную арифметику. Т.е. просеиваем на 64 бит, отмечаем вызывающие переполнение числа и их уже считаем через библиотеку для длинной арифметики.
justhabrauser
07.01.2020 20:44У меня при 10 млн < n < 100 млн уже вышло за 32 бита.
Не всё так просто.
Mad__Max
07.01.2020 20:01-1Наверно где-то так при ручной оптимизации. Плюс еще можно SIMD задействовать и проверять по несколько чисел параллельно в каждом такте.
Проблема только в том, что среднее число самих интераций с ростом числа растет. После миллиона в среднем по 100+ итераций до сходимости к 1, после миллиарда уже по 200+ и т.д.
В результате чем дальше продвигаемся, тем медленней идет перебор.Dima_Sharihin
07.01.2020 20:06+5Ну зачем так сложно. Если уже доказано, что все числа в диапазоне 1..N удовлетворяют теореме, то достаточно свести число к любому, меньшему или равному N. Зачем передоказывать уже доказанное?
justhabrauser
07.01.2020 21:05SIMD там не сильно поможет.
Считал в 32 бита, последовательно (с небольшой оптимизацией как вот рядом товарищ указал), при этом:
- уже до 100 млн вычисления выходят за 32 бита
- ориентировочно первый миллиард закончится за несколько секунд.
То есть ориентировочно в первые минуты/часы вычислений 64 бит мы выйдем за пределы этих 64 бит, так что SIMD-инструкции всё.
Static_electro
07.01.2020 22:07+1почему минуты/часы? Если наивно считать скорость перебора постоянной, то перебор, который занимает секунду до 2^32, займет 2^32 секунд, чтоб дойти до 2^64, разве нет?
justhabrauser
07.01.2020 22:20Ну как-то так, да. Не меньше, по крайней мере.
Если не учитывать переполнение, которое наступит раньше :-)
Моя оценка — переполнение 64 бита наступит по достижении проверяемым числом 32 бит.
10 минут на моем P4-3GHz
justhabrauser
08.01.2020 05:51Мда… дошел ровно до 2^31 — дальше переполнение 64 бит промежуточным результатом.
А uint128 в мой gcc-9.2.1 не завезли.
Так что на этом лично для себя я теорему доказал :-)
И да — скорость перебора линейна (точнее — постоянна).
В среднем 5 итераций на число и хоть тресни (в пределах 1..2^31).
И еще — максимальное число, достигаемое в расчетах, занимает ровно в 2 раза больше бит, чем тестируемое число. В тех же пределах.lany
08.01.2020 12:44Хм. У меня переполнение наступает позже, на числе 23,035,537,407 (за две минуты доходит до этого числа на джаве). Я оптимизировал следующим образом. Во-первых, уже отметили, что можно рассматривать только нечётные числа. Соответственно будем перебирать не x из исходной постановки задачи, а y = (x-1)/2. То есть x = 2y+1, и тогда следующее число за ним — 3x+1 = 6y+4. Очевидно, оно чётное, сразу делим пополам (3y+2). Далее его делим на два пока делится (то есть обрезаем правые нулевые биты), а потом вычитаем единицу и ещё раз делим на два, чтобы получить новый y (то есть обрезаем ещё один единичный бит). По сути надо сдвинуть результат вправо на numberOfTrailingZeros+1. NumberOfTrailingZeros — это инструкция TZCNT, быстро работает. С помощью этих оптимизаций мы также отыгрываем один битик от числа, то есть можем работать с 65-битным промежуточным результатом.
Код на Javapublic class Collatz { public static void main(String[] args) { long limit = Long.divideUnsigned(-1L, 3) - 2; for (long num = 1; ; num++) { for (long next = update(num); next >= num; next = update(next)) { if (next == num || next > limit) { System.out.println((next == num ? "Found: " : "Overflow at: ") + (num * 2 + 1)); return; } } } } private static long update(long value) { value = value * 3 + 2; return value >>> (Long.numberOfTrailingZeros(value) + 1); } }edo1h
08.01.2020 12:59А uint128 в мой gcc-9.2.1 не завезли.
как это так?!? или система 32-битная?
justhabrauser
08.01.2020 15:4832 бита да.
Да итак 5 минут уходит на это дело.
Дальше — линейно.
То есть до переполнения 128 бит у меня уйдет примерно 40 килолет.
А завтра на работу...
rogoz
08.01.2020 16:13Всё есть
godbolt.org/z/XUHReJ
Правда учитывая10 минут на моем P4-3GHz
64 бита может не быть.
justhabrauser
07.01.2020 22:09+1Сам спросил — сам ответил.
Накатал быстренько на C, посчитал первый миллиард (1..1000000000):
- уходит от 30 до 70 тактов на итерацию (зависит от кол-ва проверок и оптимизаций)
- среднее кол-во итераций дошло до ~200/число (без оптимизации, и медленно растет) или 5/число (с оптимизацией, и не меняется (!)).
- максимальное число при вычислениях — 1414236446719942480 (прописью: полтора дохреллиарда), то есть на… в два порядка выше максимального проверяемого числа.
Stas911
07.01.2020 23:35Плотность распределения количества итераций как выглядит?
justhabrauser
07.01.2020 23:42+1Я не копал так глубоко — потыкал 10^n при n=[1..9] и всё.
Среднее значение итераций ровно нарастает от 1 до 200. Без оптимизации.
С оптимизацией стоит на ровно 5.
Могу сырцы заслать, потыкаете. Мне времени было жаль :-)valergrad
08.01.2020 03:32Прям ровно 5? Не наведет ли это на какие-нибудь мысли Теренса Тао… Хотя он вероятно знает это и так.
justhabrauser
08.01.2020 03:55Смотрим:
bash-5.0$ for i in 10 100 1000 10000 100000 1000000 10000000 100000000; do ./collatz64 $i; done Max: 10, iters: 28 (2 iters/digit); Greatest digit: 52 Max: 100, iters: 803 (8 iters/digit); Greatest digit: 9232 Max: 1000, iters: 5379 (5 iters/digit); Greatest digit: 250504 Max: 10000, iters: 51838 (5 iters/digit); Greatest digit: 27114424 Max: 100000, iters: 520911 (5 iters/digit); Greatest digit: 1570824736 Max: 1000000, iters: 5226260 (5 iters/digit); Greatest digit: 56991483520 Max: 10000000, iters: 52359351 (5 iters/digit); Greatest digit: 60342610919632 Max: 100000000, iters: 523898496 (5 iters/digit); Greatest digit: 2185143829170100
(iters — это сумма всех итераций по всем числам в диапазоне)
Разумеется не ровно 5.0, а целое.
Но где-то так, да.
PS. после оптимизации естественно выпадают все четные числа, например.
edo1h
08.01.2020 12:54а не пробовали поиграться множителем? выше предполагали, что может не только с 3 работать
justhabrauser
08.01.2020 15:44К этому времени задача потеряла всякий смысл (которого и не было).
Так что поигратьсясо шрифтамиc множителями — можете продолжить :-)
DEM_dwg
07.01.2020 21:28А что если посмотреть на эту задачу, с в другой системе исчисления.
Например в двоичной.
Dr_Sigmund
07.01.2020 21:35+2В университетские годы тоже ломал над этим голову. Единственное мало-мальски осмысленное заключение, которое получилось сделать, было следующим: если существует N, не сходящееся к 1, то не сходиться оно может двумя способами: либо генерирует цикл конечной длины, либо порождает стремящуюся к бесконечности последовательность.
Исходя из этого, я пытался доказать, например, что циклы невозможны в принципе — это было бы уже что-то, но не преуспел.
Wesha
07.01.2020 22:13+1«Я не ожидал решить задачу полностью, — сказал Тао, математик из Калифорнийского университета в Лос-Анджелесе. – Но у меня получилось сделать больше, чем я ожидал».
НапомнилоМинут двадцать спустя Маккиш снова остановил космокатер. В этих
— Владимир Малов. НА КУБОК КЛАРЕНСА
соревнованиях неминуемо настает момент, когда все начинает казаться
бессмысленным. Пробиться к поверхности планеты невозможно, об этом
нечего и думать. Да и зачем? Что могло ждать человека на этой плоской
равнине, даже если он найдет ход? Только сознание того, что в памяти
компьютера теперь будет маршрут, по которому добраться сюда сможет
каждый желающий. Нелепыми были бесконечные шатания космокатера
взад-вперед, вверх-вниз, вправо-влево, нелепым был Кубок Кларенса,
нелепой была и сама открытая капитаном планета с атмосферой,
изрезанной каналами. Несуразный природный феномен, только и всего.
Существует он, и ладно, надо было зафиксировать его существование и
тут же об этом забыть.
Маккиш двинулся назад. Правда, совершенно машинально он продолжал
простукивать стенки канала. И довольно скоро открыл новый ход — тот
резко уходил вниз. Мгновение помедлив, пилот повернул космокатер.
Ход свернул вправо, потом влево. Понемногу Маккиш увеличивал
скорость, а ход никак не кончался. Он был самым длинным из всех, по
каким приходилось сегодня двигаться ярко-красной «семерке».
Static_electro
07.01.2020 22:51О, я это когда-то читал :-) но на самом деле я оставил этот комментарий, чтоб сказать редакции хабра, что если последний комментарий содержит объёмный спойлер, то после его разворачивания на телефоне скролл комментариев ломается. Кого надо тегнуть? habr?
DaneSoul
07.01.2020 22:58+2Что 99% начальных значений, больших, чем квадриллион, в итоге приходят к величинам, меньшим 200.
Так все же числа меньше 200 приходят к 1 при продолжении вычисления алгоритма, так?
Так в чем тогда смысл именно такой формулировки?
То есть разве нельзя сказать что «99% начальных значений, больших, чем квадриллион» приходят к 1?
А если учесть, что до квадриллиона уже было доказано что все приходят к 1, то и еще более обобщить: «99% всех значений приходят к 1».gremlin244
08.01.2020 02:33+1Вот тоже не понял. И зачем вообще такая точность, «к числам меньшим 200». Ведь если уже проверено что точно сходятся к единице числа вплоть до 2^60, как писали выше, то достаточно того, что 99% сходятся к числам меньшим 2^60, а там уже все посчитано.
Я так, с дивана, не математик ни разу. Просто чисто интуитивно кажется, что чем шире достаточное условие (а к 2^60 всяко шире чем к 200), тем должно быть попроще. С другой стороны труъ математикам вообще наверное фиолетово какой там порядок чисел, должно же работать «почти для всех», а на фоне каких-нибудь совсем безумных чисел что одно, что другое крохи.
edo1h
08.01.2020 12:53очевидно, это это кривой перевод. предположу, что имелось в виду "возможно не более 200 различных исходов".
SingularityUrBrain
07.01.2020 23:43-1По-моему, стоило бы также учитывать простоту числа: они сходятся дольше.
Интересено еще то, что если взять простые числа 7, 11, 13, то у 7 будет самая большая последовательность до 1, а у 13 самая маленькая, хотя 7 и 13 имеют в остатке 1 при делении на 3, а 11 имеет 2. Однако было бы неразумным не брать в выборку 11, но взять 13.michael_vostrikov
08.01.2020 16:41Это потому что у 7 все биты в двоичной системе равны 1. У таких чисел самая длинная начальная последовательность из нечетных чисел (до появления первого четного числа). Хотя это не означает самую длинную последовательность в целом, так как такие числа могут появляться в середине последовательности для других чисел.
ivan386
08.01.2020 04:12Походу задача сводится к вопросу: Сможет ли (X — 1)/3 покрыть все нечётные числа?
chapuza
08.01.2020 07:24+2Почему это? Кроме того,
(x - 1) / 3очевидно может покрыть все нечетные числа.
Возьмем нечетное число. Помножим на три. Добавим единицу. Вот вам
xдля этого нечетного числа, пользуйтесь.ivan386
08.01.2020 10:28Логично. В таком случае похоже что условия покрывают все натуральные числа.
Если идти в обратную сторону от единицы (как указанно на гифке).
ВеткаX*2гарантированно даёт бесконечное множество начальных чётных чисел. От неё соответственно бесконечное множество ответвлений разной длинны сочетаний(X — 1)/3иX * 2которое даёт все остальные натуральные числа.chapuza
08.01.2020 10:30Ну, теперь осталось доказать, что мощности множества ответвлений и множества натуральных чисел совпадают (hint: это доказать невозможно), и мы в дамках.
ivan386
08.01.2020 12:01Такой вариант:
X3 + 1 — результат всегда чётное при X нечётном (бесконечное множество)
X/2 — результат чётное и нечётное при X чётном (бесконечное множество)
2^X — чётный лифт к еденице к которому в конечном итоге приведут обе ветки (бесконечное множество входов)
Deepwarrior
08.01.2020 22:22Мощности совпадают, в обоих случаях счётно. Другое дело, что это ничего не гарантирует.
panteleymonov
08.01.2020 05:55-1По мне решение простое. Если представить числа в бинарном виде и посмотреть их изменения. То умножение на 3 будет банальной обманкой. Суть в том что прибавление Единицы каждый раз, убирает единичный бит (несколько) из бинарной последовательности, сводя таким образом число к 100000...000. Которое несомненно при делении на 2 или сдвиге в право, в конечном итоге даст единицу. Умножение на 3 в некотором роде путает это стремление к одному единичному биту, но не аннулирует его.
То есть единственное бинарное число n, которое генерирует само себя после (n+n+n+1) в циклической последовательности, это единица. Могло бы быть любое, если бы это было (n+n+n+n). Но нет, именно это выражение (3n+1) сводит все к одному единичному биту в числе.
Я бы даже расширил эту задачу до (k*n+1), где k — любое нечетное.mayorovp
08.01.2020 10:25Умножение на 3 в некотором роде путает это стремление к одному единичному биту, но не аннулирует его.
А доказать можете? :-)
chapuza
08.01.2020 10:32+1По-моему, заглавная фраза «По мне решение простое» из предыдущего комментария полностью отвечает на ваш вопрос :)
panteleymonov
08.01.2020 13:58-1«Ха ха». Не так важен ответ, сколько стеб над ним. В таком случае, есть ли смысл объяснять? Еще одно доказательство — троли рулят ресурсом.
panteleymonov
08.01.2020 11:54Что именно доказывать? Что c+1 на определенном шаге даст 2^m — которое сократиться и станет единицей, с=3*n. Вопрос сводиться к правилам объясняющим что такое четное и нечетное и их свойствам.
Из задачи в принципе можно выкинуть условия, введя функцию n=n/pow(2,first_bit(n))
Выражение (3*n+1) всегда дает четное. что означает минимум одно последующее деления на 2. То есть first_bit(n) всегда больше нуля. Соответственно, итерация всей задачи описывается как:
n=(3*n+1) // генератор псевдослучайной последовательности
n=n/pow(2,first_bit(n)) // нормализация мантиссы
Ключевой момент в том, что по правилам сумматора вычисления можно разбить на тетрады с переносом единицы в старшую часть, где закономерность последовательностей вычислений, сводимых к единицы, повторяются. То есть, тестируя большие числа, мы просто делаем вычисления над большим количеством тетрад, ожидая переноса единицы из младшей тетрады (триады и тд).
Иначе говоря задача поиска ответа превращается в вычитание единицы из бесконечности, до тех пор пока не получим единицу. Или наоборот прибавлением единицы до получения бесконечности. Ответ очевиден, а действия поиска бессмыслены.michael_vostrikov
08.01.2020 14:29+1Соответственно, итерация всей задачи описывается как:
генератор псевдослучайной последовательности
нормализация мантиссыАга, только проблема в том, что если деление на 2 только одно, то получающееся нечетное число больше предыдущего.
panteleymonov
08.01.2020 14:47Да, на этом, на самом деле, можно построить доказательство.
Представим что мы последовательно проверяем числа от 0 до бесконечности.
Каждое четное I нам дает число меньше его самого. Но так как мы уже проверили все числа меньше I, то и последовательность с текущем числом приводит к единице.
Остаются нечетные, которые могут дать только одно деление на 2. Если взглянуть на первую итерацию нечетных I, с выражением (3*n+1)/2 то получим:
3 -> 5
5 -> 8
7 -> 11
9 -> 14
11 -> 17 ..
Если будем продолжать, то заметим что каждая второе нечетное I на первой итерации дает четное число, которое можно поделить еще раз на 2.
Таким образом, из не решенных нечетных чисел, от каждого k*2+1, мы пришли к каждому k*4+3. Если проверить следующую итерацию каждого k*4+3, то также получим чередование четных и нечетных уже на второй итерации. То есть количество не решенных последовательностей будет сводиться к каждой k*(2^p)+(2^p-1).
Ну и при «p» стремящейся к бесконечности, число не решенных последовательностей стремиться к нулю.mayorovp
08.01.2020 14:57+1Если проверить следующую итерацию каждого k*4+3, то также получим чередование четных и нечетных уже на второй итерации.
Вы забыли про тот факт, что 1,52 > 2, так что однократное дополнительное деление на 2 вас уже не "спасёт", чтобы получить число, меньшее исходного, вам понадобится поделить уже на 4.
В итоге, на втором шаге у вас "вылетает" уже не половина чисел, а всего лишь четверть; ну а оставшиеся 3/4 разбиваются на две группы, обладающие разными свойствами.
panteleymonov
08.01.2020 15:02Вы забыли про тот факт, что 1,52 > 2, так что однократное дополнительное деление на 2 вас уже не «спасёт», чтобы получить число, меньшее исходного, вам понадобится поделить уже на 4.
Я ничего не забыл и как раз таки отсек все числа которые можно поделить на 4. А те которые делятся только на 2, на второй и далее итерациях, становиться меньше.
Мы уже условились что все четные имеют решение, так что не важно меньше они или больше, также не важно на какой итерации они получены, после первого деления на 2, если мы имеем четное то последовательность кончается единицей.
3 -> (10/2)5, (16/2)8
7 -> (22/2)11, (34/2)17
11 -> (34/2)17, (52/2)26
...
В итоге, на втором шаге у вас «вылетает» уже не половина чисел
Половина чисел от оставшейся половины, То есть в остатке имеем четверть, далее восьмую. И так до 1/бесконечность.
оставшиеся 3/4 разбиваются на две группы
Мы уже на первом этапе убрали половину (четные), откуда взялись обратно эти самые 2/4 или 1/2?Wesha
08.01.2020 15:29+1Половина чисел от оставшейся половины,
Всё ясно!mayorovp
08.01.2020 22:59Мы уже условились что все четные имеют решение
Нет, так "уславливаться" нельзя.
Если мы по индукции доказываем утверждение "для любого N все числа K<N имеют решение", то любое чётное N и правда можно выкинуть в силу очевидности доказательства для этого случая. Но нельзя выкинуть чётное K>N, потому что для чисел больших чем N мы ещё ничего не доказали.
panteleymonov
08.01.2020 23:31Нет, так «уславливаться» нельзя.
Еще как можно.
Но нельзя выкинуть чётное K>N, потому что для чисел больших чем N мы ещё ничего не доказали.
Следуя из того, что все четные N дают заведомо меньший результат в два раза на следующей итерации, и все из них всегда дают нечетное значение после постоянного уменьшения на два. То все что нам нужно это искать ответы для нечетных чисел. Останавливая последовательность итеративного поиска единицы на появлении четного. Которое опять таки приводит нас к расчету нечетного числа.
Например мы не выкидываем число 112 при К=2.
Но для 112 последовательность приводит к 7, которую мы в любом случае не пропустим. И это действительно для все четных. А следовательно четные считать ненужно.
То есть для четного K>N, нормализованного k=k/pow(2,first_bit(k)) — это всегда некое нечетное из нечетного ряда. Мы просто не считаем четные числа за ненадобностью на первом этапе.
Тут больше смысл не найти решения, а найти нерешаемый K элемент ряда. То есть бесконечный ряд. Он появляется если взять число 2^m-1 (это единичные биты), при этом количество непрерывных итераций (3*n+1)/2 с нечетным результатом всегда равно m, плюс некое k итераций которое состоит из последовательностей четных и нечетных результатов. При этом получается k>m.mayorovp
09.01.2020 06:24То есть для четного K>N, нормализованного k=k/pow(2,first_bit(k)) — это всегда некое нечетное из нечетного ряда. Мы просто не считаем четные числа за ненадобностью на первом этапе.
Вот только k тоже > N.
panteleymonov
09.01.2020 14:31Также как для 7, 11. И что дальше?
Самое главное что теперь нет четных.
Но каждый K=k*4+1 всегда решается как (3*n+1)/4.
А также главное что каждое k*4+1 не выдает на итерации ни какое число из того же ряда. (также как четные всегда приводят к нечетным)
То есть остаются только k*4+3 элементы, точно также как отсекаются четные, также отсекаются все k*4+1 элементы. Тоже самое повторяется для k*8+3 элементов. Так ряд нерешенных K>N сужается до бесконечности.
Числа которые остаются нерешенными это k*(2^n)-1, где n — стремиться к бесконечности. Но количество таких чисел стремиться к нулю.mayorovp
09.01.2020 15:24Ряд вы рассматриваете для N, не для K.
panteleymonov
09.01.2020 15:43С какой стати? После утверждения что K>N, а К это не решенные числа, то я как раз рассматриваю K. И потом в рамках условия, что четные ссылаются на нечетные, а те в свою очередь на другую часть нечетных, понятие решенных K<N и нерешенных K>N становиться второстепенным.
Или вам опять нужно доказывать что все четные — это нечетные числа умноженные на 2^n? Не надо доводить до абсурда свое опровержение.mayorovp
09.01.2020 16:05У вас шаг индукции выглядит как "предположим, все числа <N уже сходятся, рассмотрим N". Не "все больше N", а одно единственное N.
Теперь вы, в какой-то момент рассуждений, рассматриваете K = f(N), в которое ваше N превратилось. И должны доказать, что через сколько-то шагов оно окажется меньше N.
panteleymonov
09.01.2020 16:22Выглядит для вас? А на то как оно на самом деле выглядит, вы понять не утруждались? «Может оно зеленое?» Че за бред?
Я всего лишь указал что есть некоторый ряд нерешенных K. Для которого изначально все это описывал. А не то что вы указали. И не про каких «меньше N» далее я не заикался, все рассуждения идут параллельно утверждению «меньше N». Неоднократно утверждая, что это критерий тут не играет существенной роли.mayorovp
09.01.2020 17:16Ну тогда я вообще не вижу смысла во всех ваших доказательствах. Как и связи с двоичной системой счисления, кстати.
Так что с тем, что решение у вас простое, вы явно погорячились.
panteleymonov
09.01.2020 17:22А кроме как «мне кажется», у вас есть действительные основания для вашего опровержения?
Все доказательство свелось к тому что числа <N не являются ключевым решением и поэтому (по вашему) это доказательство не имеет смысла?mayorovp
09.01.2020 17:24Для этого сначала требуется понятное доказательство.
panteleymonov
09.01.2020 17:27То есть опять возвращаемся к тому, что начинаем доказывать, что «все четные это нечетные числа умноженные на 2^n.» так? Поскольку это и является ключем, а вы я так полагаю этого так и не поняли.
michael_vostrikov
10.01.2020 09:01Самое главное что теперь нет четных.
У вас нет четных, но нечетные на следующих итерациях все равно больше исходного числа.
11 -> (34/2)17, (52/2)26, (26/2)13
13 больше 11.
Ну и надо еще отсутствие циклов доказать.
panteleymonov
10.01.2020 17:47Пока вы кичились утверждениями что «нельзя избавиться от четных». Ряд для 11, простым алгебраическим преобразованием стал выглядеть так:
11 (1011) 13 (1101) 5 (101) 1 (1)
А те числа которые здесь отсутствуют были выброшены за ненадобностью, как и четные.
rextester.com/CVV6933
И тем более стало возможным увидеть длинные ряды своими глазами, а не полагаться на якобы недоказанную теорию.
10000011000001 (11110100001001000001) 750001 (10110111000110110001) 562501 (10001001010101000101) 105469 (11001101111111101) 39551 (1001101001111111) 337891 (1010010011111100011) 11879 (10111001100111) 20047 (100111001001111) 25373 (110001100011101) 9515 (10010100101011) 10705 (10100111010001) 8029 (1111101011101) 3011 (101111000011) 847 (1101001111) 1073 (10000110001) 805 (1100100101) 151 (10010111) 1 (1)michael_vostrikov
11.01.2020 00:36Я не говорил ничего про то, что нельзя избавиться от четных.
Ряд для 11, простым алгебраическим преобразованием стал выглядеть так
И что это доказывает? Вы просчитали последовательность до конца и убедились, что она сходится к 1. Как и остальные проверенные числа, эка невидаль)
Что доказывает длинный ряд, я тоже не понял, извините. Для числа 327 он длиннее.
panteleymonov
09.01.2020 00:04+1Короче, все четные это нечетные числа умноженные на 2^n. Так что нет смысла их считать.
edo1h
08.01.2020 14:10Я бы даже расширил эту задачу до (k*n+1), где k — любое нечетное.
проверил, похоже кроме 1 и 3 ничего не работает
panteleymonov
08.01.2020 14:21Согласен, поспешил, но неплохо было бы результаты тестов увидеть.
Например при к=5
i=5 -> 26, 13, 66, 33, 166, 83, 416, 208, 104, 52, 26, 13… бесконечно зациклено.
Но все таки, если работает с тройкой, то и с числами 3*(2^m) вполне работает. Но это бессмысленно.
DrGluck07
08.01.2020 22:07Сейчас будет дурацкое предположение. Операция (n * 3 + 1) / 2 всегда добавляет максимум 1 бит в наше число (честно, я проверял). Но мы регулярно будет получать дополнительные нули справа, которые уменьшают наше число как последовательность нулей и единиц. И возможно неважно какой длины последовательность нулей и единиц слева, важно, что расти она может только на 1 бит за операцию, но регулярно будет сокращаться на некоторое количество нулей справа. Бездна начинает смотреть на меня и я боюсь дальше думать об этом. Если вы найдёте эти записки, заклинаю всеми богами, не повторяйте моей ошиб…
panteleymonov
08.01.2020 22:40Я уже это проверил выше и пол дня назад все описал, получается сокращение всех проверяемых чисел на 2. Но есть также загвоздка. Есть брать числа 2^n-1 то количество итераций (n * 3 + 1) / 2 увеличивающих результат на 1 бит, дающее нечетное, будет равно n, плюс еще большее количество итераций которое его сократит до 1. Это очень много если брать бесконечность, то эта последовательность преобразований ни когда не кончиться.
unC0Rr
09.01.2020 10:42Поглядел на последовательности разных чисел, и у меня появилось такое предположение: количество единиц в двоичной записи чисел в последовательности всегда меньше либо равно двоичному логарифму начального числа. Если это верно, то довольно очевидно, что искать имеет смысл только циклы, а уходящих в бесконечность последовательностей не бывает.
Edit: это не так, нашёл опровержение.unC0Rr
09.01.2020 13:12Но у меня есть более слабая гипотеза: количество единиц в двоичной записи чисел в последовательности всегда меньше либо равно удвоенному двоичному логарифму начального числа. Для первых ста миллионов чисел условие выполняется, а следствие то же самое: уходящих в бесконечность последовательностей не бывает.
DrGluck07
09.01.2020 15:39Сейчас ещё кто-нибудь сделает какой-то вывод из этого. И вот так Хабр внезапно решит сложную математическую проблему современности )
panteleymonov
09.01.2020 16:14Это интересное замечание, поскольку в моих поисках я нашел закономерность, что как раз самые большие ряды с наибольшим скачком для чисел 2^n-1.
Если это 3, то максимальный скачек не больше 8. Напомню что это для (3*n+1)/2.
То есть для чисел [2^n… 2^(n+1)-1], ряды получаются с числами не больше 2^(n+2).unC0Rr
09.01.2020 16:43Это утверждение касается только количества единиц в двоичной записи, нулей может быть намного больше (но не слишком много, иначе количество единиц будет радикально увеличиваться при последующих умножениях на 3) и порядок, соответственно, намного выше. В качестве примера: для стартового числа 31 в последовательности встречается число 3077.
michael_vostrikov
08.01.2020 11:01-1Тут как-то связано с конечной записью числа, не могу сформулировать математически. Любое число можно представить в виде
2xили2x+1, само числоxтоже можно представить в таком виде, и т.д., числа в этих выражениях это биты в двоичной записи числа. И в конце этой цепочки всегда находится 0, это четное число. Мне кажется, надо отсюда идти.michael_vostrikov
08.01.2020 18:34Разверну немного мысль. Для чисел вида 2n-1, у которых все биты равны единице, длина последовательности до первого четного числа равна количеству бит.
7, 11, 17 -> 26 63, 95, 143, 215, 323, 485 -> 728 127, 191, 287, 431, 647, 971, 1457 -> 2186
Поэтому тут явно есть какая-то связь.
staticlab
08.01.2020 19:513*7+1 = 22
michael_vostrikov
08.01.2020 20:09После 3x+1 результат всегда четный, поэтому я сразу делил на 2.
То есть в стандартной формулировке тут получается первое число, когда можно поделить на 4 и получить результат меньше предыдущего.
abkjcjd
08.01.2020 13:22А если подойти к решению с другой стороны? :)
Четные числа не рассматриваем, с ними и так понятно.
Обозначим искомое число x, тогда a = 3x+1, отсюда x = (a — 1)/3, уравнение имеет смысл для всех а >= 4. Получаем:
a=4 x=1
a=5 x=4/3
a=6 x=5/3
a=7 x=2
a=8 x=7/3
a=9 x=8/3
a=10 x=3
…
a=13 x=4
…
a=16 x=5
…
a=19 x=6
…
a=22 x=7
…
a=25 x=8
a=28 x=9
a=31 x=10
a=34 x=11
a=37 x=12
a=40 x=13
Как видим, x — любое число от 1 и больше, число "а" не любое, начинается с 4… a+3.
Таким образом нужно доказать что в ряду чисел "а" всегда встретится четное число, при любом начальном значении "а". Это элементарно: сложение двух нечетных чисел дает четное число, сложение четного и нечетного (в данном случае 3) дает нечетное, таким образом в данном ряду чередуются четные и нечетные числа. Таким образом гипотеза верна. ;)
Amor-roma
08.01.2020 13:57-1Достаточно доказать что простые числа сходятся к 1 по условиям задачи.
Задача о том имеются ли локальные карманы в которых возможен цикл (не включающий 1).
Понимаю что не возможен но доказать не могу)
Сколько будет 0.5 + 0.5
Нутром чую литра, но доказать не могу ©
ZuOverture
08.01.2020 16:02Дочитав до этого места, вы могли убедиться, что математики не зря считают гипотезу Коллатца «болотом», и предупреждают, что от неё стоит оставаться подальше.
vics001
08.01.2020 20:30+1Возможно — глупый вариант.
Достаточно, доказать, что для любого числа найдется через N > 0 шагов число, меньшее этого числа. Тогда можно выстроить бесконечно строго убывающую последовательность — противоречие.
1) Для четных чисел, очевидно следующее уже строго меньше из-за деления на 2.
2) Для чисел c остатком 1 по модулю 4, число через 1 равно (3a + 1 ) / 4 < a (если a > 1).
3) Для чисел с остатком 3 (от 4), надо продолжить поиск…vics001
08.01.2020 21:17+1В принципе, можно проверять только числа с остатком 7, 11 и 15 по mod 16. Как только, число становится меньше себя, проверку можно останавливать. Написав простейший скрипт, я получил максимальную длину умножений (=37) на 3 у числа 27, дальше это число умножений не превышает даже 16.
Если подходить формально к доказательству, то надо просматривать все остатки от деления на 2^N. Если мы нашли для 16 остатки (7, 11, 15), то можно посмотреть 32 и отсеять что-то из (7, 11, 15, 23, 28, 31). Очевидно, что при длине умножений 30, надо рассматривать все остатки от деления на 2^30.
Darth_Biomech
09.01.2020 06:12Я бесконечно далек от математики, поэтому не понимаю одной вещи — как можно доказать такую задачу? Ведь для любого количества проверенных числел х всегда будет вероятность что x+1 — опровергнет. Т.е. сколько бы ты не проверил, впереди ещё бесконечность числел среди которых может быть опровергающее. Она никогда не будет доказана.
mayorovp
09.01.2020 06:26Как как, математически её доказать можно. Вывести следствие из известных аксиом.
Deosis
09.01.2020 09:47Доказательства в основном делятся на 2 типа:
- По индукции: доказывается, что верно для небольших чисел (база), а потом доказывается, что если верно для первых х чисел, то верно и для х+1 (шаг)
- От противного: Предположим, что существует х, для которого гипотеза не выполняется, и через несколько верных утверждений приходим к противоречию.
Доказательства других видов встречаются реже.
MaxxONE
Впечатляюще!
virtualtoy
Ну он же математик, ему можно
igninus
Чак Норрис от мира математики.
Stas911
И он неплохо выглядит в свои 85
lain8dono
Особенно для человека, родившегося в 1975 году.
gozhiy
Википедия говорит о дате рождения 17 июля 1975 года. Т.е. ему 44 года.
iago
я конечно понимаю, что он гений, но в 4 года быть студентом… я только читать научился
antonkrechetov
В треде выше речь идет о Теренсе Тао, авторе доказательства, а не о Джефри Лагариасе.
gozhiy
Мы говорим о разных людях. Это Теренс Тао 1975 года. А Джеффри Легариас — 1949-го.
MaxVetrov
Это он, уже должно быть, в физику пространства и времени залез.
v1000
Doctor Strange?
MaxVetrov
Доктор Кто?
ivan386
Гугл перовочик говорит что: "Доктор странный".
MaxVetrov
Doctor Who .)
Darth_Biomech
Возможно. Но кто мы такие чтобы судить?
Chosen_One
Один день тратит, два в уме :)
eugenius_nsk
Один день реальный, два мнимых