номер блюда

В математике числа Улама представляют собой целочисленную последовательность , разработанную и названную в честь Станислава Улама , который представил ее в 1964 году. Стандартная последовательность Улама (последовательность (1, 2)-Улама) начинается с U ₁ = 1 и U ₂ = 2. Затем для n > 2 U _n определяется как наименьшее целое число , которое представляет собой сумму двух различных ранее термины ровно одним способом и больше, чем все предыдущие термины.

Примеры

Как следствие определения, 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, 253, , 258, 260, 273, 282, ... (последовательность A002858 в OEIS ).

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

Говорят, что Улам предположил , что числа имеют нулевую плотность . но кажется, что они имеют плотность примерно 0,07398.

Свойства

Кроме 1 + 2 = 3, любое последующее число Улама не может быть суммой двух предыдущих последовательных чисел Улама.

Доказательство. Предположим, что для n > 2 U _{n −1} + U _n = U _{n +1} является искомой суммой только одним способом; тогда U _{n −2} + Un _n дает сумму только одним способом, и она находится U _n и Un _{между +1} . Это противоречит условию, что +1 _{Un является} следующим наименьшим числом Улама.

Для n > 2 любые три последовательных числа Улама ( U _{n −1} , U _n , U _{n +1} ) в качестве целых сторон образуют треугольник.

Доказательство. Предыдущее свойство гласит, что для n > 2 U _{n −2} + U _n ≥ U _{n + 1} . Следовательно, U _{n −1} + U _n > U _{n +1} и поскольку U _{n −1} < U _n < U _{n +1,} выполнено неравенство треугольника .

Последовательность чисел Улама образует полную последовательность .

Доказательство: по определению U _n = U _j + U _k , где j < k < n и является наименьшим целым числом, которое является суммой двух различных меньших чисел Улама ровно одним способом. Это означает, что для всех U _n с n > 3 наибольшее значение, которое U _j, может иметь равно U _{n −3} , а наибольшее значение, которое U _k может иметь , — это U _{n −1} .

Следовательно, U _n ⩽ U _{n −1} + U _{n −3} < 2 U _{n −1} и U ₁ = 1, U ₂ = 2, U ₃ = 3. Это достаточное условие для того, чтобы числа Улама были полной последовательностью.

Для каждого целого числа n > 1 всегда существует хотя бы одно число Улама U _j такое, что n ≤ U _j < 2 n .

Доказательство: доказано, что чисел Улама бесконечно много и они начинаются с 1. Следовательно, для любого целого числа n > 1 можно найти j такой, что U _{j −1} ≤ n ≤ U _j . Из приведенного выше доказательства для n > 3 следует, что U _j ≤ U _{j −1} + U _{j −3} < 2 U _{j −1} . Следовательно, n ≤ U _j < 2U _{j −1} ≤ 2 n . Также для n = 2 и 3 это свойство справедливо по расчетам.

В любой последовательности из 5 последовательных положительных целых чисел { i , i + 1,..., i + 4}, i > 4 может быть максимум 2 числа Улама.

Доказательство: предположим, что последовательность { i , i + 1,..., i + 4} имеет свое первое значение i = U _j - число Улама, тогда возможно, что i + 1 является следующим числом Улама U _{j +1} . Теперь рассмотрим i + 2, это не может быть следующее число Улама U _{j +2,} поскольку оно не является уникальной суммой двух предыдущих членов. я + 2 знак равно U _{j +1} + U ₁ знак равно U _j + U ₂ . Аналогичный аргумент существует для i + 3 и i + 4.

Неравенства

Числа Улама псевдослучайны и слишком нерегулярны, чтобы иметь жесткие границы. Тем не менее, исходя из приведенных выше свойств, а именно, что в худшем случае следующее число Улама U _{n +1} ≤ U _n + U _{n −2} и в любых пяти последовательных натуральных числах не более двух могут быть числами Улама, можно утверждать, что

5/2 для +1 n −7 U n _≤ N n _{≤ ,} n > 0

где N _n — номера в последовательности коров Нараяны : 1,1,1,2,3,4,6,9,13,19,... с рекуррентным соотношением N _n = N _{n −1} + N _{n −3} это начинается с N ₀ .

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

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

Обобщения

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

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

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

Ссылки

• Кассень, Жюльен; Финч, Стивен Р. (1995), «Класс 1-аддитивных последовательностей и квадратичных повторений» (PDF) , Experimental Mathematics , 4 (1): 49–60, doi : 10.1080/10586458.1995.10504307 , MR   1359417 , S2CID   9985793
• Финч, Стивен Р. (1992), «О регулярности некоторых 1-аддитивных последовательностей», Журнал комбинаторной теории, серия A , 60 (1): 123–130, doi : 10.1016/0097-3165(92)90042- С , МР   1156652
• Гай, Ричард (2004), Нерешенные проблемы теории чисел (3-е изд.), Springer-Verlag , стр. 166–167, ISBN  0-387-20860-7
• Кено, Раймон (1972), «Sur les suites s -additives», Журнал комбинаторной теории, серия A (на французском языке), 12 (1): 31–71, doi : 10.1016/0097-3165(72)90083-0 , МР   0302597
• Рекаман, Бернардо (1973), «Вопросы о последовательности Улама», American Mathematical Monthly , 80 (8): 919–920, doi : 10.2307/2319404 , JSTOR   2319404 , MR   1537172
• Шмерл, Джеймс; Шпигель, Юджин (1994), «Регулярность некоторых 1-аддитивных последовательностей», Журнал комбинаторной теории, серия A , 66 (1): 172–175, doi : 10.1016/0097-3165(94)90058-2 , MR   1273299
• Улам, Станислав (1964a), «Комбинаторный анализ в бесконечных множествах и некоторые физические теории», SIAM Review , 6 (4): 343–355, Бибкод : 1964SIAMR...6..343U , doi : 10.1137/1006090 , JSTOR   2027963 , МР   0170832
• Улам, Станислав (1964b), Проблемы современной математики , Нью-Йорк: John Wiley & Sons, Inc, стр. xi, МР   0280310
• Штайнербергер, Стефан (2015), Скрытый сигнал в последовательности Улама , Экспериментальная математика, arXiv : 1507.00267 , Bibcode : 2015arXiv150700267S

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

• Последовательность Улама из MathWorld
• Быстрое вычисление последовательности Улама Филипом Гиббсом
• Описание алгоритма Дональда Кнута
• Страница Github Дэниела Росса