ウラム数

ウラム数（ウラムすう、英: Ulam number）とは、（名称の由来でもある）スタニスワフ・ウラムが考案したある整数列の項である。彼はこの数（数列）を1964年に導入した^[1]。標準的なウラム数列 ((1, 2)-Ulam sequence) は U₁ = 1, U₂ = 2 から始まり、n > 2 に対する U_n は

「先行するいずれの項よりも大きく、かつ、先行する相異なる2項の和としてただ一通りに書けるような整数のうち最小のもの」

と定義される。

例

定義により、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.

ウラム数は無数に存在する。なぜなら、ウラム数列の最初の n 項が定まっているとき、 U_{n − 1} + U_n は既存のどの項よりも大きく、かつ相異なる既存の2項の和として一意的に書ける数だが、同じ性質を持つこれ以下の自然数の中で最小のものを選べばそれが第 n+1 項になるからである^[2]。

ウラムはこの数列の密度（ n 以下のウラム数の個数を u(n) としたときの $d(U)=\lim _{n\rightarrow \infty }{\frac {u(n)}{n}}$ ）はゼロだと予想したと言われている^[3]が、この値は約0.07398のようである^[4]。

隠れた構造

最初の一千万個のウラム数は、4つの項 $\left\{2,3,47,69\right\}$ を除けば $\cos {(2.5714474995a_{n})}<0$ を満たすことが見出されていた^[5]。現在これは $n=10^{9}$ まで確かめられている。この種の不等式は、普通は数列に何らかの周期性があるときに成り立つものだが、ウラム数列は周期性を持っているようには見えず、この現象は未解明である。

一般化

最初の2項を別の組 (u, v) に選んで、一般化した (u, v)-ウラム数列を考えることができる。(u, v)-ウラム数列は、階差数列が最終的に周期数列に到るとき、正則（regular）であるという。v が3より大きな奇数のとき (2, v)-ウラム数列は正則である。v が4を法として1と合同であるときも、(4, v)-ウラム数列は正則である^[6]。しかしながら元々のウラム数列は正則でないようである。

数列が

「どの 2s+1 番目の項も、先行する相異なる2項の和としてちょうど s 通りに書ける」

という性質を持つとき、s-additive であると言われる。ウラム数列および (u, v)-ウラム数列は 1-additive である^[7]。

相異なる既存の2項の和として一意的に書けるような「最小」の整数ではなく、「最大」の整数を順次追加していくことで数列を構成すると、フィボナッチ数列が得られる^[8]。

脚注

^ Ulam (1964a, 1964b).
^ Recaman (1973) は背理法を用いて次のような類似した論証を行っている。「もしウラム数が有限個しかなかったら、その中の大きい方から2個をとって作った和もまたウラム数になり、これは矛盾である。」しかしこの場合の和は、既存の2個のウラム数の和として一意的に書けるものの、一意的な表現を持つ数の中で最小とは限らない。
^ ウラムがこの予想を行ったとの記述は OEIS A002858 にある。しかし彼は Ulam (1964a) ではこの数列の密度を取り扱っておらず、Ulam (1964b) では値の予想をすることなしに密度の決定問題を提示している。Recaman (1973) では Ulam (1964b) での密度の問題が再び述べられているが、やはり値の予想はされていない。
^ OEIS A002858
^ Steinerberger (2015)
^ Queneau (1972) は u = 2 で v = 7, v = 9 の場合の正則性を最初に見出した。Finch (1992) は v を3より大きな奇数としたときにもこの結果は拡張されると予想し、この予想は 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, MR1156652
Guy, Richard (2004), Unsolved Problems in Number Theory (3rd ed.), Springer-Verlag, pp. 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, doi:10.1016/0097-3165(72)90083-0, MR0302597
Recaman, Bernardo (1973), “Questions on a sequence of Ulam”, American Mathematical Monthly 80 (8): 919–920, doi:10.2307/2319404, JSTOR 2319404, MR1537172, https://jstor.org/stable/2319404
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, MR1273299
Ulam, Stanislaw (1964a), “Combinatorial analysis in infinite sets and some physical theories”, SIAM Review 6: 343–355, doi:10.1137/1006090, JSTOR 2027963, MR0170832, https://jstor.org/stable/2027963
Ulam, Stanislaw (1964b), Problems in Modern Mathematics, New York: John Wiley & Sons, Inc, p. xi, MR0280310
Steinerberger, Stefan (2015), A Hidden Signal in the Ulam sequence, Experimental Mathematics, arXiv:1507.00267, Bibcode: 2015arXiv150700267S

外部リンク

[1] Ulam (1964a, 1964b).

[2] Recaman (1973) は背理法を用いて次のような類似した論証を行っている。「もしウラム数が有限個しかなかったら、その中の大きい方から2個をとって作った和もまたウラム数になり、これは矛盾である。」しかしこの場合の和は、既存の2個のウラム数の和として一意的に書けるものの、一意的な表現を持つ数の中で最小とは限らない。

[3] ウラムがこの予想を行ったとの記述は OEIS A002858 にある。しかし彼は Ulam (1964a) ではこの数列の密度を取り扱っておらず、Ulam (1964b) では値の予想をすることなしに密度の決定問題を提示している。Recaman (1973) では Ulam (1964b) での密度の問題が再び述べられているが、やはり値の予想はされていない。

[4] OEIS A002858

[5] Steinerberger (2015)

[6] Queneau (1972) は u = 2 で v = 7, v = 9 の場合の正則性を最初に見出した。Finch (1992) は v を3より大きな奇数としたときにもこの結果は拡張されると予想し、この予想は Schmerl & Spiegel (1994) によって証明された。(4, v)-ウラム数列の正則性は Cassaigne & Finch (1995) が証明した。

[7] Queneau (1972).

[8] Finch (1992).

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]