Ряд Рекамана

0, 1, 3, 6, 2, 7, 13, 20, 12, 21, 11, 22, 10, 23, 9, 24, 8, 25, 43, 62, 42, 63, 41, 18, 42, 17, 43, 16, 44, 15, 45, 14, 46, 79, 113, 78, 114, 77, 39, 78, 38, 79, 37, 80, 36, 81, 35, 82, 34, 83, 33, 84, 32, 85, 31, 86, 30, 87, 29, 88, 28, 89, 27, 90, 26, 91, 157, 224, 156, 225, 155, ...

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

Рекаман

Бернардо Рекаман

Бернардо Рекаман – это колумбийский математик, который занимается теорией чисел и теорией графов. Так вот, он и является создателем этого ряда. На этом месте хочется упомянуть отличный вебсайт, где можно находить ряды, их создателей, читать историю создания ряда,  график ряда и даже слушать(да) ряд: oeis.org. Информация про этот ряд была взята оттуда.

Ряд Рекамана

Формально, этот ряд записывается так:

что можно описать как отнимай если можно, в другом случае прибавляй. Можно – это когда числа не уходят в отрицательность и не встречались ранее.

Этот ряд состоит из натуральных чисел и начинается с 0, шаг ряда определяется множеством натуральных чисел, то есть порядковым номером элемента в ряде.

Из определения вы могли подумать, что числа никогда не повторяются, но на самом деле это не так. К примеру, \( a_{20}=a_{24}=42 \)Вот диаграмма разброса этого ряда для первых 100 элементов:

Из графика видно, что числа имеют тенденцию образовывать длинные параллельные чередующиеся линии, где верхние числа увеличиваются на 1, а нижнее – уменьшаются. Например, мы можем увидеть первое из них, начиная с 13:

13, 20, 12, 21, 11, 22, 10, 23, 9, 24, 8, 25 …

Это имеет смысл: мы поочередно добавляем n, а затем вычитаем n + 1, затем добавляем n + 2, затем вычитаем n + 3 и т. д. Этот шаблон будет разорван, когда мы попадем на число, которое уже было: в этом случае число после 25 не равно 7, потому что оно уже встречалось, поэтому вместо этого ряд снова переходит на 43. После 43 ряд вскакивает еще один раз (так как число 24 уже встречалось в последовательности), и мы получаем очень короткую параллельную последовательность до того, как она опустится, и начнет новую чередующуюся последовательность 41, 18, 42, 17, 43, 16, ….

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

Это не выглядит шаблонно! И это то, что я нахожу увлекательным в последовательности Рекамана: самоотсылка в ее определении (мы выбираем \( a_ {n-1} – n \), только когда число еще не появлялось) создает хаос в последовательности, поэтому очень сложно найти какие-либо шаблоны или доказать что-то определенное, хотя ряд выглядит все еще очень структурировано. Чтобы понять, что я имею в виду, вот график первых 5000 элементов:

Существует определенная структура – например, все термины, похоже, падают вдоль этих изгибающихся «полос», исходящих из источника. Я предполагаю, что можно даже сказать что-то приблизительно о форме этих кривых. Но все еще очевидно много хаоса – трудно различить любые закономерности.

Самое интересное – это задача, которую до сих пор не решили.

Открытая Задача

Существует догадка, что все натуральные числа, рано или поздно, появляются в этой последовательности. Это и есть задача, которую еще никто не решил, из-за хаоса ряда Рекамана.

Согласно записи OEIS, посмотрев первые ​\( 10 ^ {15} \)​ терминов, наименьшее число, которое не оказалось в ряде, это 852655. Что стремно, 852655 отсутствует, даже когда чекнули первые ​\( 10 ^ {230} \)​ терминов!!! (Это ошеломляюще большое количество терминов, это гораздо больше, чем предполагаемое число атомов во Вселенной.) Есть ли что-то особенное в числе 852655, чтобы оно никогда не появлялось? Или в конце концов оно встретится где-то очень далеко в последовательности? Никто не знает, и, честно говоря, я думаю, что последнее кажется более вероятным.

С 25 января 2018, первые 13 ненайденных чисел это 852655, 930058, 930557, 964420, 966052, 966727, 969194, 971330, 971626, 971866, 972275, 972827, 976367.

Кто ищет, тот всегда найдет.

-Народная Мудрость

МУзон

Обязательно добавьте в свой плейлист ряд Рекамана(скачивайте без регистрации и смс). Уверен это хит летнего сезона, под него можно и задачку эту решить.

ДП материал

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

Поделиться постом
Written by Saydolim
Очень рад, что вы дошли до сюда!
Have your say!
0 0

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>