Последовательность Рекамана

Последовательность Рекамана^[1][2] — это хорошо известная последовательность, определённая рекуррентной формулой. Поскольку элементы последовательности зависят от предыдущих элементов напрямую, они часто определяются с помощью рекурсии.

Последовательность Рекамана была названа Нилом Слоуном, создателем онлайн-энциклопедии целочисленных последовательностей (OEIS), в честь изобретателя последовательности, колумбийского математика Бернардо Рекамана Сантоса.

Последовательность Рекамана ${\displaystyle a_{0},a_{1},a_{2}\dots }$ определяется как:

${\displaystyle a_{n}={\begin{cases}0&&{\text{если }}n=0\\a_{n-1}-n&&{\text{если }}a_{n-1}-n>0{\text{ и число ещё не встречалось }}\\a_{n-1}+n&&{\text{в противном случае}}\end{cases}}}$

Первые члены последовательности^[a]:

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, ... последовательность A005132 в OEIS

Наиболее распространённая визуализация последовательности Рекамана — это просто построение её значений, как показано на рисунке здесь.

14 января 2018 года на YouTube канале Numberphile было опубликовано видео, озаглавленное «Немного жуткая последовательность Рекамана»^[3], показывающая визуализацию с использованием чередующихся полукругов, как показано на рисунке в верхней части этой страницы.

Значения последовательности могут быть связаны с музыкальными нотами, в таком случае ход последовательности может быть связан с исполнением музыкальной мелодии^[6].

Члены последовательности удовлетворяют условиям^[1]:

${\displaystyle a_{n}\geqslant 0}$

${\displaystyle |a_{n}-a_{n-1}|=n}$

Это не перестановка целых чисел — первым повторяющимся членом является ${\displaystyle 42=a_{24}=a_{20}}$^[7]. Другим является ${\displaystyle 43=a_{18}=a_{26}}$.

Нил Слоун высказал предположение, что любое число в конечном счёте в последовательности появляется^[1], но это не доказано. На 2018 год ${\displaystyle 10^{230}}$ членов было вычислено и 852655 является наименьшим натуральным числом, не появившимся в списке^[1].

Помимо своих математических и эстетических свойств, последовательность Рекама может использоваться для сокрытия 2D изображений с помощью стеганографии^[8].

Последовательность является наиболее известной последовательностью, изобретённой Рекаманом. Существует другая, менее известная последовательность, определяемая как:

${\displaystyle a_{1}=1}$

${\displaystyle a_{n+1}={\begin{cases}a_{n}/n&&{\text{если }}n{\text{ делит }}a_{n}\\na_{n}&&{\text{в противном случае}}\end{cases}}}$

Это OEIS последовательность A008336.

• Weisstein, Eric W. Recamán's Sequence (англ.) на сайте Wolfram MathWorld.
• The Slightly Spooky Recamán Sequence. (June 14, 2018) Numberphile
• The Recamán's sequence at Rosetta Code
• The Ultimate Guide to Recamán’s Sequence (visualization, sonification, and animation)