Комментарии 15
Вот так понятнее. В терминологии, что я писал выше у меня были два варианта C - с1 для 01 и с2 для 10. Для a/b блоков это соответственно длина секвенции.
То есть шаги разделения бинарного представления превращаются в:
заменить все 01 на c,
заменить лидирующую единицу на c
все оставшиеся нули и единицы заменяются а и b.
Хочу обратить внимание автора на работу https://arxiv.org/abs/2007.06979, которая обнаружила интересную связь между гипотезой Коллатца и представлениями чисел в двоичной и троичной системах счисления.
Простите меня, но залезать в такие дебри не видя простого решения это конечно грусно.
1,2 и 4 - это степени двойки.
А четверка откуда? Это вы так финальный цикл обозвали?
Блок нулей, длиной m (a_m)
Блок единиц, длиной n (b_n)
Блок чередующихся нулей и единиц, длиной k (c_k)
Совершенно неочевидно как делить произвольное число на эти запчасти.
1010111100110101001
[10101][111][00][1][10101][00][1] = c-b3-a2-b2-a1-c-b2-a1
[10][10][1111][00][11][01][01][0][01] = c1-c1-b4-a2-b2-c2-c2-b1-c2Вот уже пару вариантов разбиения для одного числа. Кажется сложность сформировать способ подобного разбиения становится эквивалентна необходимости доказать его стремление к тривиальному циклу. Очень не хватает примеров - та же 
это такой с-блок? или 
?
не усложнял ограничение на количество a и b блоков для наглядности
не знаю что в этом наглядного, но даже если начать скармливать это в некоторый regexp движок кажется оно ни разу не наглядно и я не думаю, что они покрывают все кейсы. Лучше б вы примеров разнообразных подобрали для такого разбиения.
в блочных терминах
тут же изобретается какая-то своя терминология, за которой непонятно как следить. Кто куда кого инвертор? Вы хоть бы стейт машину какую нарисовали чтобы понимать кто кого куда и чем инвертировал. Ну или в виде морфизмов как в теоркате делают. В качестве примера.
Совершенно неочевидно как делить произвольное число на эти запчасти.
Поймали) - я не описал нормально правило формирования таких слов-блоков. И стоит начать с источника проблем:
Блок чередующихся нулей и единиц, длиной k (c_k)
Здесь стоит сказать, что для нас интересно чередование вида 01 = С, так как при умножении на 3, 01 превращается в 11 (если с прошлых разрядов не пришла единица) или 00 (если она пришла). С примером 101(5) не С2 (особенно если перед стоит блок с единицей). Но вот число 101 (5) является С2, так как впереди точно стоит ноль (вторая справа единица - последняя).
Стоит ещё акцентировать внимание на том, что изначально мы представляли любое двоичное число как чередующийся блок нулей и единиц (которое наверное стоило описать).
Но мы заметили, что чередующиеся блоки нулей и единиц (каждая длиной 1) при умножении удваивают число единиц: 01 01 0* 11 = 11 11 0 (Как видите 01 чередование нам интереснее, нежели 10)
Вот для этого и ввели c - блок. Он по сути занимает 2 позиции и описывает их поведение после преобразования. А поскольку такой переход можно найти только при переходе с a-блока на b-блок (даже если их длины единичные), но не при переходе с b-блока на a -блок. Надеюсь идея стала более понятна.
не знаю что в этом наглядного, но даже если начать скармливать это в некоторый regexp движок кажется оно ни разу не наглядно ..
Возможно... Соглашусь с первой регуляркой (там надо было исключать пустые a и b блоки, а мне сильно усложнять регулярку не хотелось, поэетому и не является правильной регуляркой), но вот вторая - она правильно захватывает области с корректным представлением. Поскольку всё это базировалось на неоднозначном представлении, то попробую привести пример правильного и неправильное представления одного и того же числа и проверить правильность на регулярке:
Число: 6805
Регулярка: (cb*a*)+
Двоичное представление: 1101010010101.
Неправильное представление: bb ab ca c ab c
Результат регулярки:
Правильное представление: cb c ca c c c (в 1-ой нотации это было бы [c1] [b1] [c2] [a1] [c3] c группами [cb] [c2a] [c3])
Результат регулярки:
Как видим здесь в слове нет ab перехода, а слово начинается с C так как впереди нули находятся, которые мы не записываем.
Теперь про:
то куда кого инвертор? Вы хоть бы стейт машину какую нарисовали чтобы понимать кто кого куда и чем инвертировал.
Для двоичной записи 1 которая переходит на следующий разряд - это такой же по функциональности инвертор (меняет 0 на 1, а 1 на 0), но поскольку он в записи числа в нашей записи косвенно влияет (только на тот разряд, который является предыдущим для данного блока - мы читаем слева направо), то и b-блоком не является (и не должен, потому что является вспомогательным числом).
Вот так понятнее. В терминологии, что я писал выше у меня были два варианта C - с1 для 01 и с2 для 10. Для a/b блоков это соответственно длина секвенции.
То есть шаги разделения бинарного представления превращаются в:
заменить все 01 на c,
заменить лидирующую единицу на c
все оставшиеся нули и единицы заменяются а и b.
тут же изобретается какая-то своя терминология, за которой непонятно как следить
Да, но эта терминология здесь опирается на идеи и действия, которые мы реализуем. Я понимаю, что в математике важен формализм, но точные формулировки усложняют именно восприятие идеи, но зато не имеют иных трактовок. А как мне кажется Хабр - портал с публицистической напрвленностью, в котором эту проблему можно решать с помощью диалога или комментариев для конкретизации того, что хочет донести автор. Надеюсь примерами и обсуждением мы добьемся понимания темы)
но точные формулировки усложняют именно восприятие идеи, но зато не имеют иных трактовок
Да нет, не сильно усложняют. Формальное определение сразу бы позволило подумать про представления по основанию или как граф переходов между блоками. Правда как это позволит доказать убывание пока совершенно не ясно, но это уже вам готовить.
Ну и плюсы формальных определений - они достаточно универсальны, чтобы быть понятыми остальными. Изобретать собственную терминологию нормально, только было бы неплохо не терять совместной базы, что уже есть. Чтобы избежать ситуации как у того медика, который переизобрел интеграл и назвал его методом собственного же имени.
Товарищ, доброго вечера, буду рад обсудить решения гипотезы, хочу пр доставить вариант рассмотрения этой задачки, может будет интересно обсудить.
https://docs.google.com/document/d/1bVO65k2f8qG67EgFUgFCGCeaH98IXKeNub0TgnqYwig/edit?usp=drivesdk
Один вопрос, нах вам эта гипотеза? Есть вон уравнение Новье-Стокса, от вас просят даже не само решение, а показать его существование при каких условиях, это хотя бы полезно для прикладных целей, дошло до того что в квантмехе и суперструнной физикам самим пришлось придумывать матаппарат, пока вы циклы ищите в 3n+1 непонятно для кого и с какой целью
В математике (особенно в теории чисел) вопрос зачем - неактуален (яркий пример с Великой Теоремой Ферма - бесполезная с такой точки зрения задача, но само решение и математические конструкции, которые открыл Эндрю Уайлз оказались намного интереснее и полезнее). Да и мы не знаем где эта задача может встретиться. Зерно проблемы заключается в простоте формулировке - по своей сути школьной задачи, где все упрощают до невозможности конкретными числами и значениями, а вот решить математические лбы до сих пор не могут)
Разработка математическое аппарата, который может лечь в основу прикладного применение, методика то есть.
А может и не лечь, нам не дано предугадать как наше слово отзовется. Но так уже многократно случалось в истории науки.
Не будет ли лучше доказать не уменьшение единиц при умножении на 3, а то, что при этом формируются последовательности с единицами и с нулями? Т е если число было к примеру 11 (1011) , то при умножении имеем 33 (100001) Нули идут один за другим. Прибавим единицу и поделим: 17 (10001) Снова умножаем: 51 (110011). Единиц стало больше, но число поделилось на блоки 11 и 00. Теперь если прибавляем единицу, то получим уже два нуля в конце. После делений имеем 13 (1101) Снова умножаем: 39 (100111) Уже три единицы в конце. Прибавляем и делим: 5 (101) Дальше понятно, что сойдет к одному. Не знаю насколько такая гипотеза правдива, но мне кажется, что умножение на 3 (11) создает последовательности из нулей и единиц, а они в свою очередь схлопываются от прибавления 1 и от деления на 2.
Сиракузская проблема, идея для решения (часть 1)