Число Уляма — це член цілочисельної послідновності, яку придумав і назвав на свою честь Станіслав Улям у 1964.
Визначення Стандартна послідовність Уляма (або (1, 2)-числа Уляма) починається з U1 = 1 і U2 = 2. При n > 2, Un визначається, як найменше ціле число більше за Un-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, …
Перші числа Уляма, які також є простими числами:
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, … .
Існує нескінченно багато чисел Уляма, оскільки після додавання перших n членів завжди можна додати ще один елемент: Un — 1 + Un, який буде однозначно визначений, як сума двох елементів менших за нього і ми можемо отримати ще менші елементи використовуючи подібний метод, тому наступний елемент можна визначити, як найменший серед цих однозначно визначених варіантів. використовує схожий аргумент, сформульований як доведення від супротивного. Він стверджує, що якби було скінченне число чисел Уляма, то сума останніх двох також була б числом Уляма — суперечність. Однак, хоча сума останніх двох чисел у цьому випадку має єдине подання у вигляді суми двох чисел Уляма, вона не обов'язково є найменшим числом з єдиним поданням. Улям вважав, що числа Уляма мають нульову асимптотичну щільність,Твердження, що Улям припускав це міститься в OEIS , але Улям не намагався дати оцінку своєї послідовності в , а в він згадував проблему асимптотичної щільності цієї множини, але також не намагався оцінити її значення. повторив питання з щодо асимптотичної щільності, знову висуваючи припущення про її величину, але напевно, вона рівна 0.07398.OEIS
Прихована структура Було зауважено, що перші 10 мільйонів чисел Уляма задовольняють властивості: , крім 4 елементів (і це триває далі, як відомо, до ). Нерівності такого типу зазвичай істинні для послідовностей, що мають деяку форму періодичності, але послідовність Уляма, як відомо, не є періодичною, і цього явища не пояснено. Його можна використовувати для швидкого обчислення послідовності Уляма (див. Посилання).
Варіації та узагальнення Ідею можна узагальнити як (u, v)-числа Уляма, вибравши різні початкові значення (u, v). Послідовність чисел (u, v)-чисел Уляма є періодичною, якщо послідовність різниць між послідовними числами в послідовності періодична. Коли v — непарне число більше трьох, послідовність (2, v)-чисел Уляма є періодичною. Коли v збігається з 1 (за модулем 4) і v не менше п'яти, послідовність (4, v)-чисел Уляма знову періодична. Однак стандартні числа Уляма не є періодичними. вперше зауважив закономірність для u = 2 та v = 7 або v = 9. першим висунув гіпотезу про непарне v більше трьох, і її доведено . Періодичність (4, v)-чисел Уляма доведено . Послідовність чисел називається s-адитивною, якщо кожне число в послідовності після початкових 2s членів послідовності має рівно s подань у вигляді суми двох попередніх чисел. Таким чином, числа Уляма і (u, v)-числа Уляма є 1-адитивними послідовностями..
Якщо послідовність формується додаванням найбільшого числа з унікальним поданням у вигляді суми двох попередніх чисел, замість додавання найменшого однозначно поданого числа, то вона являє собою послідовність чисел Фібоначчі..
Примітки
Література
Посилання 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