ウラム数

ウラム数（ウラムすう、英: 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) としたときの ${\displaystyle d(U)=\lim _{n\rightarrow \infty }{\frac {u(n)}{n}}}$）はゼロだと予想したと言われている^[3]が、この値は約0.07398のようである^[4]。

隠れた構造

最初の一千万個のウラム数は、4つの項 ${\displaystyle \left\{2,3,47,69\right\}}$ を除けば ${\displaystyle \cos {(2.5714474995a_{n})}<0}$ を満たすことが見出されていた^[5]。現在これは ${\displaystyle 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]。

脚注

参考文献

• 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, MR1359417, http://www.emis.ams.org/journals/EM/restricted/4/4.1/finch.ps 
• 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 

外部リンク

• 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