Число Улама

Число Улама — это член целочисленной последовательности, придуманной и названной в свою честь Станиславом Уламом, в 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 , который будет однозначно определен, как сумма двух элементов меньше него и мы можем получить еще меньшие элементы используя подобный метод, поэтому следующий элемент можно определить, как наименьший среди этих однозначно определяемых вариантов.^[1]

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

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

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

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

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

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

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

Примечания

↑ Recaman (1973) использует похожий аргумент, сформулированный как доказательство от противного. Он утверждает, что если бы было конечное число чисел Улама, то сумма последних двух также была бы числом Улама - противоречие. Однако, хотя сумма последних двух чисел в этом случае имеет единственное представление в виде суммы двух чисел Улама, она не обязательно является наименьшим числом с единственным представлением.
↑ Утверждение, что Улам предполагал это находится в OEIS A002858, но Улам не пытался дать оценку своей последовательности в Ulam (1964a), а в Ulam (1964b) он упоминал проблему асимптотической плотности этого множества, но также не пытался оценить ее. Recaman (1973) повторяет вопрос из Ulam (1964b) об асимптотической плотности, снова не выдвигая предположения о ее значении.
↑ OEIS A002858
↑ Steinerberger (2015)
↑ Queneau (1972) впервые заметил закономерность для u = 2 и v = 7 или v = 9. Finch (1992) первым выдвинул гипотезу о нечетном v больше трех, и она была доказана Schmerl & Spiegel (1994). Периодичность (4, v)-чисел Улама была доказана Cassaigne & Finch (1995).
↑ Queneau (1972).
↑ Finch (1992).

Литература

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, <http://www.emis.ams.org/journals/EM/restricted/4/4.1/finch.ps> Архивная копия от 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
Guy, Richard (2004), Unsolved Problems in Number Theory (3rd ed.), Springer-Verlag, с. 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
Recaman, Bernardo (1973), Questions on a sequence of Ulam, American Mathematical Monthly Т. 80 (8): 919–920, DOI 10.2307/2319404
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
Ulam, Stanislaw (1964a), Combinatorial analysis in infinite sets and some physical theories, SIAM Review Т. 6: 343–355, DOI 10.1137/1006090
Ulam, Stanislaw (1964b), Problems in Modern Mathematics, New York: John Wiley & Sons, Inc, с. xi
Steinerberger, Stefan (2015), A Hidden Signal in the Ulam sequence, Experimental Mathematics

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

[1] Recaman (1973) использует похожий аргумент, сформулированный как доказательство от противного. Он утверждает, что если бы было конечное число чисел Улама, то сумма последних двух также была бы числом Улама - противоречие. Однако, хотя сумма последних двух чисел в этом случае имеет единственное представление в виде суммы двух чисел Улама, она не обязательно является наименьшим числом с единственным представлением.

[2] Утверждение, что Улам предполагал это находится в OEIS A002858, но Улам не пытался дать оценку своей последовательности в Ulam (1964a), а в Ulam (1964b) он упоминал проблему асимптотической плотности этого множества, но также не пытался оценить ее. Recaman (1973) повторяет вопрос из Ulam (1964b) об асимптотической плотности, снова не выдвигая предположения о ее значении.

[3] OEIS A002858

[4] Steinerberger (2015)

[5] Queneau (1972) впервые заметил закономерность для u = 2 и v = 7 или v = 9. Finch (1992) первым выдвинул гипотезу о нечетном v больше трех, и она была доказана Schmerl & Spiegel (1994). Периодичность (4, v)-чисел Улама была доказана Cassaigne & Finch (1995).

[6] Queneau (1972).

[7] Finch (1992).

[1]

[2]

[3]

[4]

[5]

[6]

[7]