Не кинокритик. Не палеонтолог. (plakhov) wrote,
Не кинокритик. Не палеонтолог.
plakhov

Categories:

"Простенькие" задачки

._winnie  в комментариях рассказал мне о (3n+1)-проблеме, а dfyz  (чей ник я только что по ошибке расшифровал) дал ссылку на ее описание: http://en.wikipedia.org/wiki/Collatz_conjecture

Вкратце: для всех ли натуральных n останавливается эта программа?
  while (n != 1)
n = n%2 ? n*3+1 : n/2
Несмотря на тривиальность формулировки, ответ до сих пор не известен.

_winnie  : Я придумал объяснение "на пальцах" почему завершается: если принять "вероятность" того что 3n+1 для нечётных n делится на 4 с вероятностью 1/2, то n будет чаще уменьшаться, чем увеличиваться, пока не упадёт в первую сотню, для которой можно тупо проверить что всегда превращается в 1. Понятно, что это совсем не доказательство, но зато снимается налёт "мистики".

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

Сама по себе такая постановка вопроса не является бессмысленной, несмотря на то, что "сложность" кажется очень антропным понятием. Например, теорема Разборова-Рудича утверждает (если пересказывать ее сильно упрощенно), что если P != NP, это все равно нельзя доказать простым образом. Более подробно о ней пишут здесь (ссылка via ygam).

Пара результатов вычислительных экспериментов вчера вечером.
  • Первое число, для которого статус не может быть очевидным образом вычислен (конкретнее, в процессе вычислений промежуточный результат перестает укладываться в 64-битный long) - это 8 528 817 511.
  • Статус числа 2 788 008 987 становится ясен только через 729 шагов (в этот момент промежуточный результат впервые оказывается меньше исходного числа, а значит, процесс таки сходится).
  • Пляски вокруг вычислений в Zn ни к чему хорошему не приводят. На пальцах легко объяснить, что "плохие" числа имет смысл искать только в виде 4k + 3 (остальные за один-два шага уменьшаются в размере, что позволяет применить к ним матиндукцию). Подобное "доказательство" легко формализовать и проводить автоматически, на компьютере. Выясняется, например, что при делении на 64 "плохое" число должно давать один из остатков 7, 15, 27, 31, 39, 47, 59, 63. При аналогичных вычислениях по модулю 230 (чуть больше миллиарда) "плохих" остатков оказывается больше двенадцати миллионов, т.е больше 1%. Что с этим делать - непонятно.
Tags: math
Subscribe
  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 6 comments