Число Уляма це член цілочисельної послідновності яку придумав і назвав на свою честь Станіслав Улям у 1964 ВизначенняСта

Число Уляма — це член цілочисельної послідновності, яку придумав і назвав на свою честь Станіслав Улям у 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 членів завжди можна додати ще один елемент: Un — 1 + Un, який буде однозначно визначений, як сума двох елементів менших за нього і ми можемо отримати ще менші елементи використовуючи подібний метод, тому наступний елемент можна визначити, як найменший серед цих однозначно визначених варіантів. Улям вважав, що числа Уляма мають нульову асимптотичну щільність,Recaman, (1973) повторив питання з Ulam, (1964b) щодо асимптотичної щільності, знову висуваючи припущення про її величину, але напевно, вона рівна 0.07398.

Прихована структура

Було зауважено, що перші 10 мільйонів чисел Уляма задовольняють властивості: $\cos(2.5714474995a_{n})<0$ , крім 4 елементів $\{2,3,47,69\}$ (і це триває далі, як відомо, до $n=10^{9}$ ). Нерівності такого типу зазвичай істинні для послідовностей, що мають деяку форму періодичності, але послідовність Уляма, як відомо, не є періодичною, і цього явища не пояснено. Його можна використовувати для швидкого обчислення послідовності Уляма (див. Посилання).

Варіації та узагальнення

Ідею можна узагальнити як (u, v)-числа Уляма, вибравши різні початкові значення (u, v). Послідовність чисел (u, v)-чисел Уляма є періодичною, якщо послідовність різниць між послідовними числами в послідовності періодична. Коли v — непарне число більше трьох, послідовність (2, v)-чисел Уляма є періодичною. Коли v збігається з 1 (за модулем 4) і v не менше п'яти, послідовність (4, v)-чисел Уляма знову періодична. Однак стандартні числа Уляма не є періодичними. Послідовність чисел називається s-адитивною, якщо кожне число в послідовності після початкових 2s членів послідовності має рівно s подань у вигляді суми двох попередніх чисел. Таким чином, числа Уляма і (u, v)-числа Уляма є 1-адитивними послідовностями.

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

Примітки

Recaman, (1973) використовує схожий аргумент, сформульований як доведення від супротивного. Він стверджує, що якби було скінченне число чисел Уляма, то сума останніх двох також була б числом Уляма — суперечність. Однак, хоча сума останніх двох чисел у цьому випадку має єдине подання у вигляді суми двох чисел Уляма, вона не обов'язково є найменшим числом з єдиним поданням.
Твердження, що Улям припускав це міститься в OEIS A002858, але Улям не намагався дати оцінку своєї послідовності в Ulam, (1964a), а в 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, MR 1359417
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, MR 1156652
Guy, Richard (2004), Unsolved Problems in Number Theory (вид. 3rd), , с. 166—167, ISBN
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, MR 0302597
Recaman, Bernardo (1973), Questions on a sequence of Ulam, American Mathematical Monthly, 80 (8): 919—920, doi:10.2307/2319404, JSTOR 2319404, MR 1537172
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, MR 1273299
Ulam, Stanislaw (1964a), Combinatorial analysis in infinite sets and some physical theories, SIAM Review, 6: 343—355, doi:10.1137/1006090, JSTOR 2027963, MR 0170832
Ulam, Stanislaw (1964b), Problems in Modern Mathematics, New York: John Wiley & Sons, Inc, с. xi, MR 0280310
Steinerberger, Stefan (2015), A Hidden Signal in the Ulam sequence, Experimental Mathematics, arXiv:1507.00267

Посилання

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

[1] Recaman, (1973) використовує схожий аргумент, сформульований як доведення від супротивного. Він стверджує, що якби було скінченне число чисел Уляма, то сума останніх двох також була б числом Уляма — суперечність. Однак, хоча сума останніх двох чисел у цьому випадку має єдине подання у вигляді суми двох чисел Уляма, вона не обов'язково є найменшим числом з єдиним поданням.

[2] Твердження, що Улям припускав це міститься в OEIS A002858, але Улям не намагався дати оцінку своєї послідовності в Ulam, (1964a), а в 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).