ウラム数

ウラム数（ウラムすう、）とは、（名称の由来でもある）スタニスワフ・ウラムが考案したある整数列の項である。彼はこの数（数列）を1964年に導入した。標準的なウラム数列 ((1, 2)-Ulam  sequence) は U1 = 1, U2 = 2 から始まり、n > 2 に対する Un は
「先行するいずれの項よりも大きく、かつ、先行する相異なる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, ... .

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

ウラムはこの数列の密度（ n 以下のウラム数の個数を u(n) としたときの ）はゼロだと予想したと言われているが、この値は約0.07398のようである。

隠れた構造
最初の一千万個のウラム数は、4つの項  を除けば  を満たすことが見出されていた。現在これは  まで確かめられている。この種の不等式は、普通は数列に何らかの周期性があるときに成り立つものだが、ウラム数列は周期性を持っているようには見えず、この現象は未解明である。

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

数列が
「どの 2s+1 番目の項も、先行する相異なる2項の和としてちょうど s 通りに書ける」
という性質を持つとき、s-additive であると言われる。ウラム数列および (u, v)-ウラム数列は 1-additive である。

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

脚注

参考文献

外部リンク
 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

整数の類
数学に関する記事
数学のエポニム