Число Уляма

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

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

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

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

• Cassaigne, Julien; Finch, Steven R. (1995). A class of 1-additive sequences and quadratic recurrences. Experimental Mathematics 4 (1): 49–60. MR 1359417. doi:10.1080/10586458.1995.10504307.
• Finch, Steven R. (1992). On the regularity of certain 1-additive sequences. Journal of Combinatorial Theory, Series A 60 (1): 123–130. MR 1156652. doi:10.1016/0097-3165(92)90042-S.
• Guy, Richard (2004). Unsolved Problems in Number Theory (вид. 3rd). Springer-Verlag. с. 166–167. ISBN 0-387-20860-7.
• Queneau, Raymond (1972). Sur les suites s-additives. Journal of Combinatorial Theory, Series A (фр.) 12 (1): 31–71. MR 0302597. doi:10.1016/0097-3165(72)90083-0.
• Recaman, Bernardo (1973). Questions on a sequence of Ulam. American Mathematical Monthly 80 (8): 919–920. JSTOR 2319404. MR 1537172. doi:10.2307/2319404.
• Schmerl, James; Spiegel, Eugene (1994). The regularity of some 1-additive sequences. Journal of Combinatorial Theory, Series A 66 (1): 172–175. MR 1273299. doi:10.1016/0097-3165(94)90058-2.
• Ulam, Stanislaw (1964a). Combinatorial analysis in infinite sets and some physical theories. SIAM Review 6: 343–355. JSTOR 2027963. MR 0170832. doi:10.1137/1006090.
• 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