Число Улама

Число Улама — это член целочисленной последовательности, придуманной и названной в свою честь Станиславом Уламом, в 1964 году.

Определение

Стандартная последовательность Улама  (или (1, 2)-числа Улама) начинается с U1 = 1 и U2 = 2. 
При n > 2, Un определяется, как наименьшее целое число большее Un-1, которое единственным образом разлагается в сумму двух различных более ранних членов последовательности.

Примеры
Из определения вытекает, что 3 это число Улама (1+2); и 4 это число Улама (1+3). (Тут 2+2 не является вторым представлением 4, потому что предыдущие члены должны быть различными.)  Число 5 не является числом Улама, потому что 5 = 1 + 4 = 2 + 3.  Последовательность начинается, как:
1, 2, 3, 4, 6, 8, 11, 13, 16, 18, 26, 28, 36, 38, 47, 48, 53, 57, 62, 69, 72, 77, 82, 87, 97, 99, 102, 106, 114, 126, 131, 138, 145, 148, 155, 175, 177, 180, 182, 189, 197, 206, 209, 219, 221, 236, 238, 241, 243, 253, 258, 260, 273, 282, ... .
Первые числа Улама, которые также являются простыми числами:
2, 3, 11, 13, 47, 53, 97, 131, 197, 241, 409, 431, 607, 673, 739, 751, 983, 991, 1103, 1433, 1489, 1531, 1553, 1709, 1721, 2371, 2393, 2447, 2633, 2789, 2833, 2897, ... .
Существует бесконечно много чисел Улама, поскольку после добавления первых n членов всегда можно добавить еще один элемент:  , который будет однозначно определен, как сумма двух элементов меньше него и мы можем получить еще меньшие элементы используя подобный метод, поэтому следующий элемент можно определить, как наименьший среди этих однозначно определяемых вариантов.

Улам считал, что числа Улама имеют нулевую асимптотическую плотность, однако, по-видимому, она равна 0.07398.

Скрытая структура
Было замечено , что первые 10 миллионов чисел Улама удовлетворяют свойству:  кроме 4 элементов  (и это продолжается и далее, как известно, до ). Неравенства такого типа обычно верны для последовательностей, обладающих некоторой формой периодичности, но последовательность Улама, как известно, не является периодической, и явление не было объяснено. Его можно использовать для быстрого вычисления последовательности Улама (см. внешние ссылки).

Вариации и обобщения
Идею можно обобщить как (u, v)-числа Улама, выбрав разные начальные значения (u, v). Последовательность чисел (u, v)-чисел Улама является периодичной, если последовательность разностей между последовательными числами в последовательности периодическая. Когда v - нечетное число больше трех, последовательность (2, v)-чисел Улама  является периодической. Когда v совпадает с 1 (по модулю 4) и не менее пяти, последовательность (4, v)-чисел Улама снова периодическая. Однако стандартные числа Улама не являются периодическими.

Последовательность чисел называется s-аддитивной, если каждое число в последовательности после начальных 2s-членов последовательности имеет ровно s-представлений в виде суммы двух предыдущих чисел. Таким образом, числа Улама и  (u, v)-числа Улама являются 1-аддитивными последовательностями.

Если последовательность формируется путем добавления наибольшего числа с уникальным представлением в виде суммы двух более ранних чисел, вместо добавления наименьшего однозначно представимого числа, то результирующая последовательность представляет собой последовательность чисел Фибоначчи.

Примечания

Литература

Внешние ссылки
 Ulam Sequence from MathWorld
 Fast computation of the Ulam sequence by Philip Gibbs
 Description of Algorithm by Donald Knuth
 The github page of Daniel Ross

Целочисленные последовательности