Из Википедии, свободной энциклопедии
Перейти к навигации Перейти к поиску

В математике числа Улама представляют собой целочисленную последовательность, разработанную и названную в честь Станислава Улама , который ввел ее в 1964 году. [1] Стандартная последовательность Улама (последовательность (1, 2) -Улам) начинается с U 1  = 1 и U 2  = 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, 243, 253, 258, 260, 273, 282, ... (последовательность A002858 в OEIS ).

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

Улама говорят, высказал предположение , что числа имеют нулевую плотность , [3] , но они , кажется, имеют плотность приблизительно 0.07398. [4]

Свойства [ править ]

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

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

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

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

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

Доказательство: по определению U n = U j + U k, где j < k < n и является наименьшим целым числом, которое является суммой двух различных меньших чисел Улама точно одним способом. Это означает, что для всех U n  с n > 3 наибольшее значение, которое может иметь U j , равно U n −3, а наибольшее значение, которое может иметь U k , - U n −1 . [5] [7]
Следовательно, U n ≤ U n −1 + U n −3 <2 U n −1 и U 1 = 1, U 2 = 2, U 3 = 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 числа Улама. [7]

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

Неравенства [ править ]

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

5/2n −7 ≤ U n ≤ N n +1 для n > 0, [7]

где N n - числа в последовательности коров Нараяны : 1,1,1,2,3,4,6,9,13,19, ... с рекуррентным соотношением N n = N n −1 + N n −3 который начинается с N 0 .

Скрытая структура [ править ]

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

Обобщения [ править ]

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

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

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

Заметки [ править ]

  1. ^ Улама  ( 1964а , 1964b ).
  2. ^ Рекаман (1973) приводит аналогичный аргумент, сформулированный как доказательство от противного . Он утверждает, что если бы было конечное число чисел Улама, то сумма последних двух также была бы числом Улама - противоречие. Однако, хотя сумма двух последних чисел в этом случае будет иметь уникальное представление в виде суммы двух чисел Улама, она не обязательно будет наименьшим числом с уникальным представлением.
  3. ^ Утверждение, что Улам сделал эту гипотезу, содержится в OEIS OEIS :  A002858 , но Улам не рассматривает плотность этой последовательности в Ulam (1964a) , а в Ulam (1964b) он ставит вопрос об определении ее плотности, не предполагая значения для Это. Рекаман (1973) повторяет вопрос Улама (1964b) о плотности этой последовательности, снова не предполагая ее значения.
  4. ^ OEIS OEIS :  A002858
  5. ^ a b Рекаман (1973)
  6. ^ OEIS OEIS :  A330909
  7. ^ a b c Филип Гиббс и Джадсон МакКрэни (2017). «Улам насчитывает до одного триллиона» . п. 1. Введение).
  8. ^ Штайнербергер (2015)
  9. ^ Кено (1972) впервые обнаружил регулярность последовательностей для u  = 2, v  = 7 и v  = 9. Финч (1992) предположил распространение этого результата на все нечетные v больше трех, и эта гипотеза была доказана Шмерлем. И Шпигель (1994) . Регулярностьчисел(4,  v ) -Улама была доказана Cassaigne & Finch (1995) .
  10. ^ Queneau (1972) .
  11. Перейти ↑ Finch (1992) .

Ссылки [ править ]

  • Кассень, Жюльен; Finch, Стивен Р. (1995), "Класс 1-аддитивных последовательностей и квадратичных рецидивов" , Экспериментальная Математика , 4 (1): 49-60, DOI : 10,1080 / 10586458.1995.10504307 , МР  1359417
  • Finch, Стивен Р. (1992), "О регулярности некоторых 1-аддитивных последовательностей", Журнал комбинаторной теории, Series A , 60 (1): 123-130, DOI : 10,1016 / 0097-3165 (92) 90042- S , Руководство по ремонту  1156652
  • Гай, Ричард (2004), Нерешенные проблемы теории чисел (3-е изд.), Springer-Verlag , стр. 166–167, ISBN 0-387-20860-7
  • Кено, Raymond (1972), "Sur Les Suites s -additives", Журнал комбинаторной теории, Серия А (на французском языке), 12 (1): 31-71, DOI : 10,1016 / 0097-3165 (72) 90083-0 , Руководство по ремонту  0302597
  • Recaman, Бернардо (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
  • Улама, Станислав (1964а), "Комбинаторный анализ в бесконечных множеств и некоторых физических теорий", SIAM Обзор , 6 (4): 343-355, DOI : 10,1137 / 1006090 , JSTOR  2027963 , МР  0170832
  • Улам, Станислав (1964b), Проблемы современной математики , Нью-Йорк: John Wiley & Sons, Inc., стр. xi, Руководство MR  0280310
  • Штайнербергер, Стефан (2015), Скрытый сигнал в последовательности Улама , Экспериментальная математика, arXiv : 1507.00267 , Bibcode : 2015arXiv150700267S


Внешние ссылки [ править ]

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