Комментарии 265
Каждый день он тратит один-два дня на самые известные из нерешённых задач по математике.
Впечатляюще!
Опытные математики советуют новичкам держаться подальше от гипотезы Коллатца.А так как мы не опытные, да и не математики вовсе, то сейчас попробую накидать статью с потенциальным доказательством.
Но даже если я и ошибаюсь, все равно спасибо автору за утреннюю гимнастику для ума!
Очень интересная задачка.
Никогда не понимал одержимости математическими доказательствами и профита от них.
Вот в данном случае можно было написать скрипт на языке программирования и проверить на практике. Но математиков это не устроит, так как доказательства должны быть по местным понятиям.
А просто скрипт докажет (или опровергнет) гипотезу лишь на некотором конечном множестве, в частном случае. Это подходит там, где это множество конечно или можно от частного перейти к общему. В данном случае мы имеем дело с бесконечным множеством.
докажет (или опровергнет) гипотезу лишь на некотором конечном множестве
Эм… Для опровержения достаточно множества мощности 1 :)
Ну а разве математики доказывают не путём индукции? Типа справедливо для x, x+1, x+2… то справедливо и для остальных целых чисел.
Типа справедливо для x, x+1, x+2… то справедливо и для остальных целых чисел.Это не метод индукции, это не пойми что :) Нельзя просто взять конечный числовой ряд и назвать его доказательством.
Ну как тут все уже поняли — я не математик.
Вот кстати на Хабре явно не хватает статьи с методами доказательств на простых примерах. И вообще, ИМХО математика нуждается в популязаторстве.
Конечно я понимаю что это невозможно, нет царских путей и всё такое :)
Гипотеза: все нечетные числа — простые. Доказывает физик:
3 — простое, 5 — простое, 7 — простое, 9 -ошибка эксперимента, 11 — простое, 13 — простое...
Это так что ли вы предлагаете делать? Нет, математики так никогда не делают.
Скрипт тоже, но не сразу — просто подождите пупсилион лет.
Это для конкретного большого числа. А для всех чисел — никогда, или, что то же самое, через бесконечное количество времени.
Достаточно на каждое следующее число тратить в 2 раза меньше времени на проверку. Тогда получим сходщийся ряд и проверим бесконечное множество за конечное время. Делов то.
Ага. Так даже можно посчитать сумму ряда 1, -1, 1, -1, 1, -1,…
Складываем все единицы с минус единицами и получаем ноль.
Или переупорядочиваем 1, 1, -1, 1, 1, -1, 1, 1, -1,… складываем по 3 и получаем плюс бесконечность в пределе.
Впрочем, это я так — для разминки мозгов. Что получилось бы, если бы гипервычисления были реальностью.
Вы не можете переупорядочить элементы. Это уже другой ряд будет.
Это справедливо лишь для абсолютно сходящихся рядов, коим ряд Гранди не является.
Лишние? Мощности множеств единиц и минус единиц в обоих рядах одинаковы и равны алеф-ноль.
Там дело в том, что если определить сумму бесконечного ряда, как предельный переход, то у ряда Гранди никакой суммы не будет. И с таким определением суммы бесконечного ряда ряд уже нельзя рассматривать просто как множество чисел.
Поэтому — да, переупорядочивание, которое я использовал, не обязано давать ту же сумму. Но не потому, что там другое количество единиц и минус единиц. Это действительно просто перестановка.
Только по Чезаро сумма этого ряда равна 0.5.
Не с концом, а сразу появится десяток новых вопросов:
- А есть ещё?
- Если это конечный цикл, то есть ли без цикла (и наоборот)?
- Оценка числа таких чисел в промежутке;
- Алгоритмическая сложность получения последовательности таких чисел (если бесконечно);
- А в условии брать не четность, а другие модули;
- …
UPD.
Шутки шутками, а прикольно было бы жить в мире, где правительство попыталось бы законодательно запретить какую-то математическую задачу.
Это доказательство нужно даже если всё очевидно?
Скрипт докажет до определённого целого числа и этого может быть достаточно.
Если всё очевидно — значит, и доказательство придумать несложно. Так в чём проблема-то?
Ну потому что доказать нужно специфичным образом.
Вот например легко представить себе что резиновая сфера без разрезов может превратиться в квадрат или сжаться в точку, а в бублик трансформироваться не сможет. Это здравый смысл.
Но есть гипотеза Пуанкаре и её доказательство, важность которых я не оспариваю. Но хотелось бы понять их практическую значимость.
Ну так конкретно для сферы, квадрата (т.е. куба?) и бублика это можно и без гипотезы Пуанкаре доказать.
Гипотеза Пуанкаре вам понадобится в тот момент, когда у вас окажется такое странное многообразие, для которого трансформация в сферу будет неочевидной.
Как правило, полное доказательство таких гипотез даёт попутный субпродукт — новую разработанную методологию решения математических задач. Она позволит атаковать другие проблемы, которые вполне могут иметь практическую ценность, даже если от самой изначальной гипотезы пользу нет. В математике никогда заранее точно не знаешь, где появится полезное знание, но практика показывает, что это происходит весьма часто. Поэтому надо продолжать копать.
Доказать нельзя потому что проверить все числа невозможно.
Опровергнуть тоже нельзя — потому что для опровержения даже для одного числа нужно выполнить бесконечное число операций.
Предположим вы нашли число 5**9999 и за первый миллион операций оно не пришло к 1. Может ли скрипт понять что оно никогда к нему не придет?
Посмотреть, как зависит число операций от числа.
Только начальный, для сравнения с очередным сгенерированным. Остальные-то зачем хранить при наличии однозначных правил генерации?
Насколько я понял, есть хорошая аппроксимация числа шагов до схождения от величины исходного числа. Если проверяемое число сходится существенно дольше ожидаемого, то можно для него отдельно запускать проверку на попадание в цикл с хранением промежуточных. Ниже был вариант как это сделать хоть и за большое время (но не более удвоенной длины цикла), зато с хранением всего лишь двух значений. В крайнем случае (бесконечное расхождение) этот метод позволяет наложить ограничение снизу на длину цикла.
На практике ряд либо получится убывающим и сводящимся к единице — как все проверенные до сих пор.
Либо возрастающим и стремящимся к бесконечности — тут проблемой станет быстрое переполнение (слишком большие числа)
Либо неубывающим и не возрастающим, а петляющим в диапазоне чисел не намного выше исходного числа, но тогда должен достаточно быстро попасть на повтор одного из чисел в последовательности и тем самым уход в замкнутый цикл.
Можно конечно чисто теоретически представить неубывающий и не возрастающий ряд, но при этом не имеющий ни одного повтора на длинне выборки в миллионы или даже миллиарды чисел в ряду (все уникальные) которые возможно сохранить в памяти. Но на практике все проверенное сворачивается к единице на тысячах итераций максимум.
И обнаружение любого числа выбивающегося из этого правила само по себе станет открытием. Было бы интересно получить число из которого простой формулой (как в этой гипотезе) можно получить ряд в миллионы неповторяющихся псевдослучайных чисел при этом без выраженой тенденции к их росту.
У нас было три построения теории вещественных чисел, 75 пределов последовательностей, два определения предела функции по Коши и по Гейне, комплексные числа, О-символика, наполненная эквивалентными функциями, и целое море различных непрерывностей и равномерностей всех сортов и расцветок, а также запись лекций Теляковского, производные, точки разрыва первого и второго рода и задачник Демидовича. Не то, чтобы это был необходимый запас для подготовки, но раз уж начал готовиться к коллоквиуму, становится трудно остановиться. Единственное, что вызывало у меня опасение — это производные. Ничто в мире не бывает более беспомощным, безответственным и порочным, чем дифференциальные зомби. Я знал, что рано или поздно мы перейдём и на эту дрянь.
Фишка дифференциальных уравнений в том, что изменение системы целиком и полностью зависит от текущего состояния системы (и граничных условий). Если посмотреть на это с точки зрения дискретных вычислений, то это означает, что каждое следующее состояние вычисляется через предыдущее.
Возьмём простейший пример дифференциального уравнения: x' = k*x, то есть скорость линейно зависит от положения. Если x0 = 1, то x' = k, значит следующее положение объекта будет x1 = x0 + k * dt. И так далее. При более сложном законе будет более сложная формула. Получается этакая последовательность вычислений, похожая на задачу из топика.
Дискретные вычисления для дифференциальных уравнений очень широко применяются в моделировании физических процессов. И там очень важным вопросом является сходимость. Поэтому для определения параметров сходимости разработано огромное множество методик, одну из которых, по всей видимости, и применил Тао.
Операция 3x+1 над нечетным числом делает число четным, т.е. добавляет делитель 2, который тут же уничтожается операцией x/2. Вопрос в том, каковы оставшиеся новые делители — на своем обывательском уровне не рискну делать никаких предположений по этому поводу, но очевидно меняются радикально. Чем-то похоже на поведение линейного конгруэнтного генератора случайных чисел, где операции над числами тоже крайне простые, а результаты выглядят как хаос.
На самом деле, там два действия
1) если четное, то разделить на два 2) если нечетное, то (3x+1)/2. И тут уже очевидность схлопывается, поскольку нельзя ничего сказать о новых делителях этого числа.
Мне кажется, что сейчас минимум пара десятков человек бросилась к компьютеру.
А потом классифицировать и найти закономерность.
Ага. Пойти от обратного. Ответить на вопрос — какие числа дают в результате применения этих правил за один шаг числа из множества 1...10 (1...100, 1...1000). Посмотреть. Есть ли дырки. И попробовать растянуть выводы на все множество чисел )
Эхх… видно пришла пора её уже выкидывать :) — чистой математикой я не занимался уже лет 10.
Пусть n — любое нечетное натуральное число (четные рассматривать смысла нет), тогда с вероятностью 1/2 после первого и второго действия над ним мы получим 1,5n+0,5, т.е. увеличение чуть более, чем на 50%. С вероятностью 1/4 мы после двух действий еще сможем разделить на 2, т.е. мы получим 0,75n+0,25 — уже уменьшение примерно на 25%. С вероятностью 1/8 мы сможем еще разделить на 2 и т.д. В этом отношении мне кажется, что подсчитав полную вероятность мы получим, что до того момента, как число снова станет нечетным, оно уменьшится относительно изначального n. Но у меня не хватает аппарата это подсчитать.
Если же мое предположение о большей вероятности понижения верно, тогда с удлинением последовательности число будет все уменьшаться до минимального натурального, т.е. до 1.
1/2 + 1/4 + 1/8 +… + 1/2^x
Какую ещё вероятность поищем?
Впрочем, получается, я сделал еще одно допущение в том, что 3n+1 — вполне обычное четное число, с вероятностью 1/2 делящееся на 4, 1/4 — на 8, 1/8 — на 16 и т.д. С этим, возможно, тоже надо разбираться.
при этом «возможно» здесь потому что только первая такая операция действительно «случайна», а «случайность» последюущих уже вызывает вопросы
а «большинство» здесь потому что даже маленькая вероятность чего-либо не гарантирует отсутствие таких чисел (к примеру если наивно посчитать вероятность того что число будет простым, то кажется как будто они должны будут кончиться)
Вот в этих то «возможно» и «большинство» и загвоздка
Можно и по-другому сказать. Если вы с вероятностью 50% делаете шаг назад и с вероятностью 50% делаете 2 шага вперед, то рано или поздно вы достигнете указанную впереди точку, как бы далеко она от вас не была. По-моему, это можно считать доказательством. Осталось только реально эти вероятности посчитать. :)
Если мы попали в число, которое является степенью двойки, умножим на два. А если не является — уменьшим сразу до 1. Все ли числа уменьшатся до 1 в итоге?
Какая вероятность того что большое число N является степенью двойки? Очень маленькая. И если является, то умножив его на 2 получим еще большее число, которое будет с еще меньшим шансом являться степенью двойки, так?
Не так. Потому что тот факт то что число является степенью двойки изменяет вероятности. И если мы умножим степень двойки на 2, то шанс получить степень двойки оказывается вовсе не случайным событием.
Поэтому то, что «каждое следующее нечетное число будет соответствовать тем же условиям, что и предыдущее» не является фактом и это нужно доказывать. (Кроме того, это еще и не является правдой, судя по всему, только перекос наоборот, в сторону уменьшения)
Я тоже рассматривал по вероятностям, что по идее должно довольно быстро сходиться, но тут получается что оно 41 раз растёт и доходит до >9k
Может исключения из правила очень маловероятны, но есть? ;)
Разница лишь в том что, 27 на первых этапах дает снижение. А 2^n-1 дают максимальную последовательность из постоянно повышающихся чисел.
Я бы обратил внимание на то что все они заканчиваются на очень знакомые ветви.
3077 (101000000011) 577 (1000001001) 433 (100011011) 325 (101000101) 61 (101111) 23 (11101) 35 (110001) 53 (101011) 5 (101) 1 (1)
1457 (10001101101) 1093 (10100010001) 205 (10110011) 77 (1011001) 29 (10111) 11 (1101) 17 (10001) 13 (1011) 5 (101) 1 (1)
Далее 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)
Я могу узнать по бинарному коду числа сколько у него будет итераций (3*n+1)/2 до получения четного
и что это даёт? ну да, с 27 через 2 итерации будет падение, но что будет после этого падения же заранее неизвестно — может быть очередной рост, и т.д.
Ну, а если начать с того что я начал, то часть чисел просто убирается из проверки. Из всего числового ряда остается немного — то что требуется действительно проверять.
Например такие числа как 911 дают большой подъем и падение до 577. А другие с 4 итерациями дают только подъем. 35 такое же число, если определить характер этих чисел, то можно по одной формуле вычислить ряд который ведет заведомо к 1.
В прикрепленном видео довольно любопытный график показан. Интересно посмотреть на аналогичный график в логарифмическом масштабе, например log2. Для достаточно больших чисел (x >> 1) операция 3x + 1 в логарифмическом масштабе "практически" экивалентна сдвигу на log2(3) = 1.58, а операция деления на 2 — сдвигу на -1.
С учетом того, что после умножения на 3 и добавления 1 число всегда будет четным, это дает нам одно гарантированное деление на 2. Таким образом, в логарифмическом масштабе число будет расти не быстрее чем на 0.58 на каждые две операции. Для того, чтобы число достигло 1, нужно доказать, что количество делений на 2 всегда превосходит количество умножений в определенное количество раз. Очевидно, что чтобы число "в среднем" не менялось, нужно, чтобы на каждое увелечение на 1.58 (за счет 3x + 1) приходилось 1.58 уменьшений на 1 (за счет деления). Теоретический верхний предел отношения это 1, когда ни одно из четных чисел последовательности не содержит в качестве множителя больше одной двойки (т.е. при первом же делении мы снова попадаем на нечетное число). Теоретический и практический нижний предел отношения это 0. Эта ситуация возникает когда исходное число это просто степень двойки.
Таким образом, нужно показать, что для любого числа отношение количества уменьшений к количеству увеличений меньше чем 1 / 1.58 = 0.63. Я взял первые 10к положительных целых чисел и посмотрел на распределение этого отношения. Похоже, что это отношение всегда меньше 0.6.
Интересно что столбец в нуле автоматически дает количество степеней двойки в выборке.
Собственно, это ничего не доказывает, просто я люблю строить графики.
В конце я естественно напсал глупость — отношение количества увеличений к количеству уменьшений должно быть меньше 0.63.
А можно такой график для хотя бы 1-10 млн первых чисел
Ну естественно можно, они а) наверное где-то существуют уже, б) для числа 107 я не берусь предсказать, насколько последовательность может вырасти. Соответственно, вычисление одного числа в диапазоне "миллионов" может занимать продолжительное время, а построение последовательностей для нескольких миллионов чисел может оказаться задачей непростой.
В любом случае, эти графики я построил в R буквально используя пару однострочных неоптимизрованных методов и ggplot2. Приложив чуть больше усилий к коду, можно я думаю собрать приличную статистику и на домашнем ПК/лэптопе.
Я не согласен. Хоть и существуют книжки и даже анекдоты о том, что самые сложные доказательства всегда скрываются за "очевидно" и "не трудно показать", в большинстве случаев это не так. Да и "рядовой инженер" умеет обращаться с числами.
Касательно моего примера: под "очевидно" я понимаю, что если число увеличивается на 4 единицы, а уменьшается на 2, то если на каждое увеличение (+4) будет приходиться два уменьшения (2 x -2 = -4), конечное значение будет несильно отличаться от исходного сколько бы итераций вы не выполнили бы, и для сохранения этого баланса отношение числа увеличений (1n) к числу уменьшений (2n) должно быть 1n / 2n = 0.5. Если больше — последовательность уйдет на бесконечность, меньше — в 0.
В 0 в логарифмической шкале, т.к. цель это единица, а log2(1) = 0 (как и вообще любой логарифм единицы). Это можно увидеть на рисунке 1, в конце последовательности.
Мемы мемами, но при определенной сноровке во многих формулах угадываются стандартные "паттерны" и их комбинации, из-за чего даже гигантское уравнение из "своей" области если и не оказажется сходу очевидным, то хотя бы даст представление о том, что же оно описывает. Но это работает далеко не всегда :)
Хотя в вашем же первом меме просто очень неудачное обозначение. Без знания конкретных операций можно увидеть, что оператор [., .] антикоммутативен, т.е. [x, y] = -[y, x]. Далее видно, что [x, y] = x * y - y * x, и * очевидно некоммутативно. Дальше просто раскрываете все кадратные скобки используя установленные нами свойства, что-то должно сократиться, видимо * ассоциативно, поэтому группируете обратно, вынося за скобки — вот и результат. При этом мы абсолютно не представляем, что это за операторы/опрации, и что такое множество D(A), но т.к. они подчиняются общим правилам, мы можем доказать верность утверждения.
Очевидно, что оно нечетно, иначе оно не было бы первым. Оно либо формирует цикл, либо открывает собой некоторую цепочку, бесконечную или где-то тоже зацикленную.
Задача сводится к доказательству несуществования такого числа.
Интересно глянуть какими оптмизированными алгоритмами перебирают эту программно.
BOINC@Home этим уже развлекались. Заказчики математики, при вычислениях использовали оптимизации. Величина аудитории, предоставляющей свои компы для вычислений, огромная. Так что способ не такой уж простой.
Хотя практически ее можно считать доказанной уже сейчас. Но практического применения насколько знаю у нее и нет никакого. А с точки зрения «чистой математики» нужно такое же чистое доказательство в общем виде, а не в частных случаях.
Но она простая в том смысле что первое же найденное исключение (и тут перебор на компах вполне подходит) опровергнет теорему и закроет вопрос.
Нет, он не простой в том смысле, что в силу вероятностного характера такого угадывания в историю вы скорее всего не войдёте, как не вошли 65+ тысяч человек занимавшихся этим ранее.
Скорее всего даже менее осмысленно — карты все же когда-нибудь отсортируются, а вот здесь, вероятно, число не найдется никогда.
Но такое выявленное «аномальное» число можно уже отдать математикам, чтобы они проверили анализ — а что в этом числе такого необычного(например разложить на множители для начала), что оно приводит к такому результату? И попробовать уже аналитически доказать, что последовательность получится именно расходящейся бесконечностью если начать с этого конкретного числа.
Вообще задача не бесполезная. Наверняка там по пути кучу всего изобрести удастся. От всяких оптимизаций до фрактальных каких-нибудь закономерностей полезных.
Вон от множества Мандельброта или от шума Перлина какая польза? А она есть!
Исключение — относительно монотонно возрастающие ряды в которых вероятность встретить повтор не растет от длины.
Но в таких рядах(при их наличии) мы в первую очередь не с не хваткой объема памяти для хранения членов ряда столкнемся, а с переполнением разрядности используемых вычислений — быстро появляются слишком большие (длинные) числа не умещающиеся даже в «длинную арифметику».
Тут конечно доказать что такой найденный ряд будет и дальше бесконечно возрастать численными методами не получится — с этим я и не спорил.
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 с самой быстрой «длинной» математикой, оптимизированной под алгоритм), можно даже не пробовать…И я вас уверяю, это всё еще будет не бесконечный цикл. :)
Чтобы опровергнуть эту гипотезу, достаточно найти число, которое после некоторого количества итераций превращается в самое себя.
Т.е. построить lookup таблицу (граф, radix-/patricia-trie, whatever) для бесконечного множества огромных чисел и/или итераций (чтобы собственно найти «самое себя»)?
А памяти хватит? :)
Простите, я не понимаю, о чем вы.
Представьте себе, что мне приснилось некое число, скажем первые стопиццот знаков π, — которое после трех делений на два и умножений на три предыдущего натурального числа превращается в самое себя. Цикл замкнулся, гипотеза опровергнута.
Вывод — на каждой итерации снизу вверх запоминать, а сверху вниз сравнивать.
Что в худшем случае выливается в сравнивать всех со всеми.
Повторюсь, памяти хватит?
А магию типа «приснилось число» и бац на 3-й итераций оно снова «тоже самое» оставьте для пикабу, плз.
Дело в том что опровергнуть как раз и не получится, т.к. для этого нужно продолжать цикл бесконечно (просто потому что и числа в неравенстве fi(x) != 2n могут расти бесконечно)…
Вот это ваше утверждение — чушь. Никакой цикл никуда бесконечно продолжать не нужно. Так понятнее?
оставьте для пикабу
Обязательно, вот только шнурки выглажу.
1 -> 4 -> 2 -> 1 в самом начале (внезапно потому что тут есть «магическое» число 1, то это совсем не означает, что какая-то другая последовательность тоже замкнется.Посмотрите на картинки типа «Iteration (stopping) time for inputs» или веер (треугольник) распределения…
Т.е. расти оно будет всегда (бесконечно или нет, не доказано).
Но что оно замкнется — это нонсенс. Что-то из оперы «А пацаны то не знали».
Так понятнее?
Ладно, попробую в последний раз.
Рассмотрим вырожденный пример. Гипотеза: «не существует целого числа, в котором после гуголплекса нулей идет гуголплекс единиц». Ни один существующий в мире компьютер не справится решить эту задачу перебором. Тем не менее, очевидно, такое число существует, и не одно. QED.
В математике для опровержения гипотезы достаточно привести один пример. Вы утверждали, что для этого нужно продолжать какой-то цикл бесконечно. Это — неверно.
Предположите, умозрительно, что такое число, замыкающееся в цикл после сравнительно невеликого числа итераций существует. Далее предположите, что некий Васяо решил пособить Тао и наугад проверяет числа в районе Гуголплекса. И через день натыкается на такое число. Вероятность этого события, хоть и чрезвычайно мала, но отлична от нуля. Наткнуться на такое число, чтобы опровергнуть гипотезу, нужно ровно один раз.
А не «нонсенс» и «пацаны» — это вам надо бы на пикабу. Скриптики — это круто, но к математике имеет очень опосредованное отношение.
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 бит).
Я надеюсь стало чуть понятней почему по моему скромному мнению слово «достаточно» тут не совсем подходит.
x = 3*x+1 / 2; while not (x & 1) { x = x2 / 2; compare(xhare, xtort) }; repeat Т.е. только на гарантированном спуске
(3*xi+1 / 4 < xi).Floyd уместен когда сравниваются «готовые» элементы списка, а не когда они будут вычисляться на каждой итерации (т.е. не там где операция вычисления станет дороже операции сравнения).
Кроме того, пока что нет даже подозрения, что какое-то число «влетает» в бесконечный цикл — он пока у всех всегда заканчивался ожидаемо 2n (что есть начало спуска до 1) за какое-то (да иногда долгое, иногда очень, но) конечное время.
А не в основном цикле перебора следить за отсутствием повторяемости в последовательности.
Это число имеет последовательность, в которой допустим до 280 подъемов и спусков, и при этом «бегает» по числам в интервале (22K..24.5K) пока в конце не достигнет уже проверенную группу до 260 или (ожидаемо) гарантированный спуск на каком-то 2N.
При том что хранить все «проверенные» числа вы не хотите, единственная возможность это отсекать интервал (22K..24K-2), последовательно перебирая числа в «основном цикле».
Кроме того если вы посмотрите эту ветку комментариев выше, то возможно заметите что речь тут идет про какое-то «приснившееся» число (т.е. «случайное», для которого числа и менее его могут быть еще не «проверены»).
Вопрос: которое «множество» считать «проверенным», откуда у вас тут «сотня» когда там много-много порядков больше, а главное когда (на каком спуске/подъеме) запускать и главное останавливать того зайца Флойда?
Ну и напомню, что число может забираться сильно вверх, а диапазон (24K..24,5K) у вас не проверен по умолчанию, т.е. вопрос №2: почему вы исключаете что тот «теоретический» замкнутый цикл (aka periodic orbit) не находится где-то в этой области?
так в статье же уже написано, что проверили достаточно много чисел — и подобного не нашли
Интересно — сколько тактов CPU уйдет на одну итерацию?
Если использовать ассемблер x86-64 и оперировать в пределах 64 бит.
(могу предположить что порядка 6..10)
Если использовать ассемблер x86-64 и оперировать в пределах 64 бит.
Так в этих пределах уже все посчитано, а длинная арифметика медленная ну вообще везде
Если верить википедии, то не всё.
Даже вы этих пределах.
PS. у меня пока получилось порядка 30 тактов на итерацию; на C быстренько набросал.
Это 2 в 60 степени. Т.е. до пределов быстрой 64 бит арифметики еще довольно далеко — на порядок дальше чем уже успели перебрать.
Промежуточные результаты могут выходить за пределы 64-х бит
И как раз такие последовательности в первую очередь и интересны и требуют проверки.
Правда большая часть все же почти сразу идет вниз и поэтому по-идее можно продолжать считать на аппаратных 64 бит и только в случае переполнения подключать длинную арифметику. Т.е. просеиваем на 64 бит, отмечаем вызывающие переполнение числа и их уже считаем через библиотеку для длинной арифметики.
У меня при 10 млн < n < 100 млн уже вышло за 32 бита.
Не всё так просто.
Проблема только в том, что среднее число самих интераций с ростом числа растет. После миллиона в среднем по 100+ итераций до сходимости к 1, после миллиарда уже по 200+ и т.д.
В результате чем дальше продвигаемся, тем медленней идет перебор.
Ну зачем так сложно. Если уже доказано, что все числа в диапазоне 1..N удовлетворяют теореме, то достаточно свести число к любому, меньшему или равному N. Зачем передоказывать уже доказанное?
SIMD там не сильно поможет.
Считал в 32 бита, последовательно (с небольшой оптимизацией как вот рядом товарищ указал), при этом:
- уже до 100 млн вычисления выходят за 32 бита
- ориентировочно первый миллиард закончится за несколько секунд.
То есть ориентировочно в первые минуты/часы вычислений 64 бит мы выйдем за пределы этих 64 бит, так что SIMD-инструкции всё.
почему минуты/часы? Если наивно считать скорость перебора постоянной, то перебор, который занимает секунду до 2^32, займет 2^32 секунд, чтоб дойти до 2^64, разве нет?
Ну как-то так, да. Не меньше, по крайней мере.
Если не учитывать переполнение, которое наступит раньше :-)
Моя оценка — переполнение 64 бита наступит по достижении проверяемым числом 32 бит.
10 минут на моем P4-3GHz
Мда… дошел ровно до 2^31 — дальше переполнение 64 бит промежуточным результатом.
А uint128 в мой gcc-9.2.1 не завезли.
Так что на этом лично для себя я теорему доказал :-)
И да — скорость перебора линейна (точнее — постоянна).
В среднем 5 итераций на число и хоть тресни (в пределах 1..2^31).
И еще — максимальное число, достигаемое в расчетах, занимает ровно в 2 раза больше бит, чем тестируемое число. В тех же пределах.
Хм. У меня переполнение наступает позже, на числе 23,035,537,407 (за две минуты доходит до этого числа на джаве). Я оптимизировал следующим образом. Во-первых, уже отметили, что можно рассматривать только нечётные числа. Соответственно будем перебирать не x из исходной постановки задачи, а y = (x-1)/2. То есть x = 2y+1, и тогда следующее число за ним — 3x+1 = 6y+4. Очевидно, оно чётное, сразу делим пополам (3y+2). Далее его делим на два пока делится (то есть обрезаем правые нулевые биты), а потом вычитаем единицу и ещё раз делим на два, чтобы получить новый y (то есть обрезаем ещё один единичный бит). По сути надо сдвинуть результат вправо на numberOfTrailingZeros+1. NumberOfTrailingZeros — это инструкция TZCNT, быстро работает. С помощью этих оптимизаций мы также отыгрываем один битик от числа, то есть можем работать с 65-битным промежуточным результатом.
public 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);
}
}В Java нет типа unsigned long, но это никому не мешает. Сложение и умножение для signed и unsigned работает одинаково, есть операция беззнакового битового сдвига >>>, а для деления есть специальный метод divideUnsigned.
А uint128 в мой gcc-9.2.1 не завезли.
как это так?!? или система 32-битная?
Сам спросил — сам ответил.
Накатал быстренько на C, посчитал первый миллиард (1..1000000000):
- уходит от 30 до 70 тактов на итерацию (зависит от кол-ва проверок и оптимизаций)
- среднее кол-во итераций дошло до ~200/число (без оптимизации, и медленно растет) или 5/число (с оптимизацией, и не меняется (!)).
- максимальное число при вычислениях — 1414236446719942480 (прописью: полтора дохреллиарда), то есть на… в два порядка выше максимального проверяемого числа.
Я не копал так глубоко — потыкал 10^n при n=[1..9] и всё.
Среднее значение итераций ровно нарастает от 1 до 200. Без оптимизации.
С оптимизацией стоит на ровно 5.
Могу сырцы заслать, потыкаете. Мне времени было жаль :-)
Смотрим:
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. после оптимизации естественно выпадают все четные числа, например.
Например в двоичной.
И чем этот взгляд принципиально отличается?
Числа другие получатся?
Скорее другие коэффициенты рассматривать.
Тоже подумал ( хоть и не математик ) а что если уменьшить систему счисления до , какое там максимальное число - 3. Вот в ней ( 4-ной ) все и посчитать, может легче пойдет, а потом усложнить до 10-ричной.
Исходя из этого, я пытался доказать, например, что циклы невозможны в принципе — это было бы уже что-то, но не преуспел.
«Я не ожидал решить задачу полностью, — сказал Тао, математик из Калифорнийского университета в Лос-Анджелесе. – Но у меня получилось сделать больше, чем я ожидал».
Минут двадцать спустя Маккиш снова остановил космокатер. В этих— Владимир Малов. НА КУБОК КЛАРЕНСА
соревнованиях неминуемо настает момент, когда все начинает казаться
бессмысленным. Пробиться к поверхности планеты невозможно, об этом
нечего и думать. Да и зачем? Что могло ждать человека на этой плоской
равнине, даже если он найдет ход? Только сознание того, что в памяти
компьютера теперь будет маршрут, по которому добраться сюда сможет
каждый желающий. Нелепыми были бесконечные шатания космокатера
взад-вперед, вверх-вниз, вправо-влево, нелепым был Кубок Кларенса,
нелепой была и сама открытая капитаном планета с атмосферой,
изрезанной каналами. Несуразный природный феномен, только и всего.
Существует он, и ладно, надо было зафиксировать его существование и
тут же об этом забыть.
Маккиш двинулся назад. Правда, совершенно машинально он продолжал
простукивать стенки канала. И довольно скоро открыл новый ход — тот
резко уходил вниз. Мгновение помедлив, пилот повернул космокатер.
Ход свернул вправо, потом влево. Понемногу Маккиш увеличивал
скорость, а ход никак не кончался. Он был самым длинным из всех, по
каким приходилось сегодня двигаться ярко-красной «семерке».
О, я это когда-то читал :-) но на самом деле я оставил этот комментарий, чтоб сказать редакции хабра, что если последний комментарий содержит объёмный спойлер, то после его разворачивания на телефоне скролл комментариев ломается. Кого надо тегнуть? habr?
Что 99% начальных значений, больших, чем квадриллион, в итоге приходят к величинам, меньшим 200.Так все же числа меньше 200 приходят к 1 при продолжении вычисления алгоритма, так?
Так в чем тогда смысл именно такой формулировки?
То есть разве нельзя сказать что «99% начальных значений, больших, чем квадриллион» приходят к 1?
А если учесть, что до квадриллиона уже было доказано что все приходят к 1, то и еще более обобщить: «99% всех значений приходят к 1».
Я так, с дивана, не математик ни разу. Просто чисто интуитивно кажется, что чем шире достаточное условие (а к 2^60 всяко шире чем к 200), тем должно быть попроще. С другой стороны труъ математикам вообще наверное фиолетово какой там порядок чисел, должно же работать «почти для всех», а на фоне каких-нибудь совсем безумных чисел что одно, что другое крохи.
очевидно, это это кривой перевод. предположу, что имелось в виду "возможно не более 200 различных исходов".
Интересено еще то, что если взять простые числа 7, 11, 13, то у 7 будет самая большая последовательность до 1, а у 13 самая маленькая, хотя 7 и 13 имеют в остатке 1 при делении на 3, а 11 имеет 2. Однако было бы неразумным не брать в выборку 11, но взять 13.
Это потому что у 7 все биты в двоичной системе равны 1. У таких чисел самая длинная начальная последовательность из нечетных чисел (до появления первого четного числа). Хотя это не означает самую длинную последовательность в целом, так как такие числа могут появляться в середине последовательности для других чисел.
Походу задача сводится к вопросу: Сможет ли (X — 1)/3 покрыть все нечётные числа?
Почему это? Кроме того, (x - 1) / 3 очевидно может покрыть все нечетные числа.
Возьмем нечетное число. Помножим на три. Добавим единицу. Вот вам x для этого нечетного числа, пользуйтесь.
Логично. В таком случае похоже что условия покрывают все натуральные числа.
Если идти в обратную сторону от единицы (как указанно на гифке).
Ветка X*2 гарантированно даёт бесконечное множество начальных чётных чисел. От неё соответственно бесконечное множество ответвлений разной длинны сочетаний (X — 1)/3 и X * 2 которое даёт все остальные натуральные числа.
Ну, теперь осталось доказать, что мощности множества ответвлений и множества натуральных чисел совпадают (hint: это доказать невозможно), и мы в дамках.
Такой вариант:
X3 + 1 — результат всегда чётное при X нечётном (бесконечное множество)
X/2 — результат чётное и нечётное при X чётном (бесконечное множество)
2^X — чётный лифт к еденице к которому в конечном итоге приведут обе ветки (бесконечное множество входов)
Мощности совпадают, в обоих случаях счётно. Другое дело, что это ничего не гарантирует.
То есть единственное бинарное число n, которое генерирует само себя после (n+n+n+1) в циклической последовательности, это единица. Могло бы быть любое, если бы это было (n+n+n+n). Но нет, именно это выражение (3n+1) сводит все к одному единичному биту в числе.
Я бы даже расширил эту задачу до (k*n+1), где k — любое нечетное.
Умножение на 3 в некотором роде путает это стремление к одному единичному биту, но не аннулирует его.
А доказать можете? :-)
По-моему, заглавная фраза «По мне решение простое» из предыдущего комментария полностью отвечает на ваш вопрос :)
Из задачи в принципе можно выкинуть условия, введя функцию 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)) // нормализация мантиссыКлючевой момент в том, что по правилам сумматора вычисления можно разбить на тетрады с переносом единицы в старшую часть, где закономерность последовательностей вычислений, сводимых к единицы, повторяются. То есть, тестируя большие числа, мы просто делаем вычисления над большим количеством тетрад, ожидая переноса единицы из младшей тетрады (триады и тд).
Иначе говоря задача поиска ответа превращается в вычитание единицы из бесконечности, до тех пор пока не получим единицу. Или наоборот прибавлением единицы до получения бесконечности. Ответ очевиден, а действия поиска бессмыслены.
Соответственно, итерация всей задачи описывается как:
генератор псевдослучайной последовательности
нормализация мантиссы
Ага, только проблема в том, что если деление на 2 только одно, то получающееся нечетное число больше предыдущего.
Представим что мы последовательно проверяем числа от 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» стремящейся к бесконечности, число не решенных последовательностей стремиться к нулю.
Если проверить следующую итерацию каждого k*4+3, то также получим чередование четных и нечетных уже на второй итерации.
Вы забыли про тот факт, что 1,52 > 2, так что однократное дополнительное деление на 2 вас уже не "спасёт", чтобы получить число, меньшее исходного, вам понадобится поделить уже на 4.
В итоге, на втором шаге у вас "вылетает" уже не половина чисел, а всего лишь четверть; ну а оставшиеся 3/4 разбиваются на две группы, обладающие разными свойствами.
Вы забыли про тот факт, что 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?
Половина чисел от оставшейся половины,
Мы уже условились что все четные имеют решение
Нет, так "уславливаться" нельзя.
Если мы по индукции доказываем утверждение "для любого N все числа K<N имеют решение", то любое чётное N и правда можно выкинуть в силу очевидности доказательства для этого случая. Но нельзя выкинуть чётное K>N, потому что для чисел больших чем N мы ещё ничего не доказали.
Нет, так «уславливаться» нельзя.Еще как можно.
Но нельзя выкинуть чётное 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.
То есть для четного K>N, нормализованного k=k/pow(2,first_bit(k)) — это всегда некое нечетное из нечетного ряда. Мы просто не считаем четные числа за ненадобностью на первом этапе.
Вот только k тоже > N.
Самое главное что теперь нет четных.
Но каждый 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 — стремиться к бесконечности. Но количество таких чисел стремиться к нулю.
Ряд вы рассматриваете для N, не для K.
Или вам опять нужно доказывать что все четные — это нечетные числа умноженные на 2^n? Не надо доводить до абсурда свое опровержение.
У вас шаг индукции выглядит как "предположим, все числа <N уже сходятся, рассмотрим N". Не "все больше N", а одно единственное N.
Теперь вы, в какой-то момент рассуждений, рассматриваете K = f(N), в которое ваше N превратилось. И должны доказать, что через сколько-то шагов оно окажется меньше N.
Я всего лишь указал что есть некоторый ряд нерешенных K. Для которого изначально все это описывал. А не то что вы указали. И не про каких «меньше N» далее я не заикался, все рассуждения идут параллельно утверждению «меньше N». Неоднократно утверждая, что это критерий тут не играет существенной роли.
Ну тогда я вообще не вижу смысла во всех ваших доказательствах. Как и связи с двоичной системой счисления, кстати.
Так что с тем, что решение у вас простое, вы явно погорячились.
Самое главное что теперь нет четных.
У вас нет четных, но нечетные на следующих итерациях все равно больше исходного числа.
11 -> (34/2)17, (52/2)26, (26/2)13
13 больше 11.
Ну и надо еще отсутствие циклов доказать.
11 (1011) 13 (1101) 5 (101) 1 (1)
А те числа которые здесь отсутствуют были выброшены за ненадобностью, как и четные.
rextester.com/CVV6933
И тем более стало возможным увидеть длинные ряды своими глазами, а не полагаться на якобы недоказанную теорию.
Я не говорил ничего про то, что нельзя избавиться от четных.
Ряд для 11, простым алгебраическим преобразованием стал выглядеть так
И что это доказывает? Вы просчитали последовательность до конца и убедились, что она сходится к 1. Как и остальные проверенные числа, эка невидаль)
Что доказывает длинный ряд, я тоже не понял, извините. Для числа 327 он длиннее.
Берём два бесконечных множества: чётные и нечётные числа. Для всех чётных чисел («Мы уже условились что все четные имеют решение») есть решение. Для всех нечётных преобразование 3n+1 перекидывает число в чётное множество, то есть тоже есть решение. Вуаля?
Я бы даже расширил эту задачу до (k*n+1), где k — любое нечетное.
проверил, похоже кроме 1 и 3 ничего не работает
Edit: это не так, нашёл опровержение.
Если это 3, то максимальный скачек не больше 8. Напомню что это для (3*n+1)/2.
То есть для чисел [2^n… 2^(n+1)-1], ряды получаются с числами не больше 2^(n+2).
Тут как-то связано с конечной записью числа, не могу сформулировать математически. Любое число можно представить в виде 2x или 2x+1, само число x тоже можно представить в таком виде, и т.д., числа в этих выражениях это биты в двоичной записи числа. И в конце этой цепочки всегда находится 0, это четное число. Мне кажется, надо отсюда идти.
Разверну немного мысль. Для чисел вида 2n-1, у которых все биты равны единице, длина последовательности до первого четного числа равна количеству бит.
7, 11, 17 -> 26
63, 95, 143, 215, 323, 485 -> 728
127, 191, 287, 431, 647, 971, 1457 -> 2186Поэтому тут явно есть какая-то связь.
В общем, у меня вот так получилось. Это неполное доказательство, но я не математик, может у кого-то лучше получится.
Мы умножаем на 3, это двухзначное двоичное число. В двоичной записи числа могут заканчиваться на .00, .01, .10, .11. Также умножение на 3 это сложение числа с ним же со сдвигом на 1 бит. Перенос будем обозначать знаком '+', просто для информации.
.00 и .10 это четные числа, по условиям мы их делим на 2 и получаем число меньше исходного.
.01 и .11 умножаем на 3 и прибавляем 1.
..01 +
.010
----
..11 +1
.+00Для чисел, заканчивающихся на .01 получается четное число, кратное 4. Умножили на 3, поделили на 4, получаем число меньше исходного.
Для .11 получается перенос, поэтому надо рассмотреть больше знаков. После любого количества единиц всегда будет 0, либо в середине числа, либо после самого старшего разряда, так как запись числа конечная. Обозначим повторяющуюся единицу одним знаком i, чтобы удобнее было считать в столбик. Для всех единиц, кроме первой и последней, действия при сложении одинаковые — сложение самих единиц и перенос из предыдущего разряда, в результате получается единица и перенос в следующий разряд. Также заметим, что ее можно помещать в любое место внутри группы единиц, так как их количество от этого не меняется.
...01i11 +
..011i10
--------
..+01i01 +1
..+01i10 /2
...+01i1В исходном числе была последовательность 01i11, в результате есть последовательность 01i1, то есть число подряд идущих единиц гарантированно становится меньше на один. Это доказывает, что бесконечного применения ветки "3x+1" не будет, в какой-то момент число станет заканчиваться на .01, и будет одно дополнительное деление на 4. Но это не доказывает, что последовательность гарантированно уменьшается.
Можно рассмотреть еще один знак.
...001i11 +
..0011i10
---------
...101i01 +1
...101i10 /2
....101i1...101i11 +
..1011i10
---------
..+001i01 +1
..+001i10 /2
...+001i1Видно, что комбинации переходят друг в друга с уменьшением количества оканчивающих единиц.
Если перед единицами два 0, то перенос единицы при сложении заканчивается на них. Число разбивается на отдельные такие группы, каждую из которых можно представить как отдельное число, для которого справедливы закономерности умножения на 3.
Если один, то перенос единицы при сложении идет дальше, и получается как бы 3x+1 внутри самого числа. Число подряд идущих единиц в другой части числа тоже уменьшается, и после них появляется 0, поэтому и получается снова комбинация с двумя 0. При этом, в силу конечности числа, два 0 гарантированно встретятся в начале записи.
При умножении на 3 первой комбинации количество единиц не увеличивается, просто между ними появляются нули.
При умножении на 3 второй комбинации количество единиц уменьшается, и между ними тоже появляются нули.
Нули при вычислениях сдвигаются к концу записи числа и убираются при делении на 2.
Таким образом, количество единиц гарантированно уменьшится до 1, а количество нулей до 0.
Возможно я чего-то не учел, но с этого хотя бы можно начать.
А если подойти к решению с другой стороны? :)
Четные числа не рассматриваем, с ними и так понятно.
Обозначим искомое число 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) дает нечетное, таким образом в данном ряду чередуются четные и нечетные числа. Таким образом гипотеза верна. ;)
Достаточно доказать что простые числа сходятся к 1 по условиям задачи.
Задача о том имеются ли локальные карманы в которых возможен цикл (не включающий 1).
Понимаю что не возможен но доказать не могу)
Сколько будет 0.5 + 0.5
Нутром чую литра, но доказать не могу ©
Дочитав до этого места, вы могли убедиться, что математики не зря считают гипотезу Коллатца «болотом», и предупреждают, что от неё стоит оставаться подальше.
Достаточно, доказать, что для любого числа найдется через N > 0 шагов число, меньшее этого числа. Тогда можно выстроить бесконечно строго убывающую последовательность — противоречие.
1) Для четных чисел, очевидно следующее уже строго меньше из-за деления на 2.
2) Для чисел c остатком 1 по модулю 4, число через 1 равно (3a + 1 ) / 4 < a (если a > 1).
3) Для чисел с остатком 3 (от 4), надо продолжить поиск…
Если подходить формально к доказательству, то надо просматривать все остатки от деления на 2^N. Если мы нашли для 16 остатки (7, 11, 15), то можно посмотреть 32 и отсеять что-то из (7, 11, 15, 23, 28, 31). Очевидно, что при длине умножений 30, надо рассматривать все остатки от деления на 2^30.
Как как, математически её доказать можно. Вывести следствие из известных аксиом.
Доказательства в основном делятся на 2 типа:
- По индукции: доказывается, что верно для небольших чисел (база), а потом доказывается, что если верно для первых х чисел, то верно и для х+1 (шаг)
- От противного: Предположим, что существует х, для которого гипотеза не выполняется, и через несколько верных утверждений приходим к противоречию.
Доказательства других видов встречаются реже.
В свое время меня вдохновил муравей Ленгтона. Это клеточный автомат, который описывается двумя простейшими правилами:
- На чёрном квадрате — повернуть на 90° влево, изменить цвет квадрата на белый, сделать шаг вперед на следующую клетку.
- На белом квадрате — повернуть на 90° вправо, изменить цвет квадрата на чёрный, сделать шаг вперед на следующую клетку.
При этом работает он очень замысловато: сначала строит хаотичный узор, а затем начинает бесконечную шаблонную последовательность из 104 шагов.
В свою очередь все проверенные числа по гипотезе Коллаца приводят к бесконечному циклу: 1, 4, 2, 1, 4, 2, 1, и так далее, до бесконечности.
Так может гипотеза Коллаца и клеточные автоматы имеют что-то общее и можно выразить одно через другое?
С таким не шутят)
(((((((((((((((((((((((((((((((((((((((((((((27×3+1)/2×3+1)/2/2)×3+1)/2)×3+1)/2×3+1)/2×3)+1)/2×3+1)/2/2×3+1)/2/2×3)+1)/2×3+1)/2/2×3+1)/2×3+1)/2×3+1)/2/2×3+1)/2×3+1)/2×3+1)/2×3+1)/2/2×3+1)/2/2/2×3+1)/2×3+1)/2×3+1)/2/2×3+1)/2×3+1)/2/2×3+1)/2×3+1)/2×3+1)/2×3+1)/2×3+1)/2×3+1)/2/2/2×3+1)/2×3+1)/2×3+1)/2×3+1)/2/2/2/2×3+1)/2/2×3+1)/2/2×3+1)/2/2/2/2×3+1)/2/2/2×3+1)/2×3+1)/2×3+1)/2/2/2/2/2×3+1)/2/2/2/2=1
сейчас посмотрел — простое число 333645655005*(2^35549)-1 (примерно 10К десятичных знаков) даёт пик по количеству итераций в виде 400К вместо 200К у стоящих рядом чисел, но всё также приходит к единице.
но чёт мне кажется. что всё, что можно было побрутфорсить, уже побрутфорсили :-)
всё, что можно было побрутфорсить, уже побрутфорсили
Конечно — математики — они не такие уж ленивые.
Раз задача до сих пор актуальна, значит нужно именно математическое решение и доказательство. Если бы нашли хоть одно исключение — проблему бы сняли с повестки дня.
Это же со всеми теоремами-гипотезами. Та же теорема Ферма именно потому и была всем интересна, что на примерах вроде все так, но уверенности на 100% на всем пространстве чисел — хз.
Математики достигли прорыва в изучении «опасной» задачи