Число Улама

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

Определение

Стандартная последовательность Улама (или (1, 2)-числа Улама) начинается с U₁ = 1 и U₂ = 2. При n > 2, U_n определяется, как наименьшее целое число большее U_n-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, ... последовательность A002858 в OEIS.

Первые числа Улама, которые также являются простыми числами:

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

Существует бесконечно много чисел Улама, поскольку после добавления первых n членов всегда можно добавить еще один элемент: U_{n − 1} + U_n , который будет однозначно определен, как сумма двух элементов меньше него и мы можем получить еще меньшие элементы используя подобный метод, поэтому следующий элемент можно определить, как наименьший среди этих однозначно определяемых вариантов.

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

Скрытая структура

Было замечено , что первые 10 миллионов чисел Улама удовлетворяют свойству: $\cos {(2.5714474995a_{n})}<0$ кроме 4 элементов $\left\{2,3,47,69\right\}$ (и это продолжается и далее, как известно, до $n=10^{9}$). Неравенства такого типа обычно верны для последовательностей, обладающих некоторой формой периодичности, но последовательность Улама, как известно, не является периодической, и явление не было объяснено. Его можно использовать для быстрого вычисления последовательности Улама (см. внешние ссылки).

Вариации и обобщения

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

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

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

Литература

• Cassaigne, Julien; Finch, Steven R. (1995), "A class of 1-additive sequences and quadratic recurrences", Experimental Mathematics, 4 (1): 49—60, doi:10.1080/10586458.1995.10504307, MR 1359417 Архивная копия от 4 марта 2016 на Wayback Machine
• Finch, Steven R. (1992), "On the regularity of certain 1-additive sequences", Journal of Combinatorial Theory, Series A, 60 (1): 123—130, doi:10.1016/0097-3165(92)90042-S, MR 1156652
• Guy, Richard (2004), Unsolved Problems in Number Theory (3rd ed.), Springer-Verlag, pp. 166—167, ISBN 0-387-20860-7
• Queneau, Raymond (1972), "Sur les suites s-additives", Journal of Combinatorial Theory, Series A (фр.), 12 (1): 31—71, doi:10.1016/0097-3165(72)90083-0, MR 0302597
• Recaman, Bernardo (1973), "Questions on a sequence of Ulam", American Mathematical Monthly, 80 (8): 919—920, doi:10.2307/2319404, JSTOR 2319404, MR 1537172
• Schmerl, James; Spiegel, Eugene (1994), "The regularity of some 1-additive sequences", Journal of Combinatorial Theory, Series A, 66 (1): 172—175, doi:10.1016/0097-3165(94)90058-2, MR 1273299
• Ulam, Stanislaw (1964a), "Combinatorial analysis in infinite sets and some physical theories", SIAM Review, 6: 343—355, doi:10.1137/1006090, JSTOR 2027963, MR 0170832
• Ulam, Stanislaw (1964b), Problems in Modern Mathematics, New York: John Wiley & Sons, Inc, p. xi, MR 0280310
• Steinerberger, Stefan (2015), A Hidden Signal in the Ulam sequence, Experimental Mathematics, arXiv:1507.00267

Внешние ссылки

• 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