Номер Улама - Ulam number

An Номер Улама является членом целочисленная последовательность разработан и назван в честь Станислав Улам, который представил его в 1964 году.[1] Стандартная последовательность Улам (последовательность (1, 2) -Улам) начинается с U1 = 1 и U2 = 2. Тогда для п > 2, Uп определяется как наименьший целое число это сумма двух различных более ранних терминов ровно одним способом и больше, чем все предыдущие термины.

Примеры

Как следствие определения, 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 ).

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

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

Характеристики

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

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

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

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

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

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

Для каждого целого числа п > 1 всегда есть хотя бы одно число Улама Uj такой, что п ≤ Uj < 2п.

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

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

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

Неравенства

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

5/2п-7 ≤ Uп ≤ Nп + 1 за п > 0,[7]

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

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

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

Обобщения

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

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

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

Примечания

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

Рекомендации


внешняя ссылка